On the complexity of Minimum Path Cover with Subpath Constraints for multi-assembly

Show simple item record

dc.contributor University of Helsinki, Department of Computer Science en
dc.contributor University of Helsinki, Department of Computer Science en
dc.contributor.author Rizzi, Romeo
dc.contributor.author Tomescu, Alexandru Ioan
dc.contributor.author Mäkinen, Veli
dc.date.accessioned 2016-05-24T09:01:02Z
dc.date.available 2016-05-24T09:01:02Z
dc.date.issued 2014-09-10
dc.identifier.citation Rizzi , R , Tomescu , A I & Mäkinen , V 2014 , ' On the complexity of Minimum Path Cover with Subpath Constraints for multi-assembly ' , BMC Bioinformatics , vol. 15 , no. S9 , pp. S5 . https://doi.org/10.1186/1471-2105-15-S9-S5 en
dc.identifier.issn 1471-2105
dc.identifier.other PURE: 45129502
dc.identifier.other PURE UUID: 2b7bc7c4-cb10-4d4b-aaa9-8465c2d24251
dc.identifier.other WOS: 000345661000005
dc.identifier.other Scopus: 84921800612
dc.identifier.other ORCID: /0000-0003-4454-1493/work/28882741
dc.identifier.other ORCID: /0000-0002-5747-8350/work/32208022
dc.identifier.uri http://hdl.handle.net/10138/162778
dc.description.abstract Background Multi-assembly problems have gathered much attention in the last years, as Next-Generation Sequencing technologies have started being applied to mixed settings, such as reads from the transcriptome (RNA-Seq), or from viral quasi-species. One classical model that has resurfaced in many multi-assembly methods (e.g. in Cufflinks, ShoRAH, BRANCH, CLASS) is the Minimum Path Cover (MPC) Problem, which asks for the minimum number of directed paths that cover all the nodes of a directed acyclic graph. The MPC Problem is highly popular because the acyclicity of the graph ensures its polynomial-time solvability. Results In this paper, we consider two generalizations of it dealing with integrating constraints arising from long reads or paired-end reads; these extensions have also been considered by two recent methods, but not fully solved. More specifically, we study the two problems where also a set of subpaths, or pairs of subpaths, of the graph have to be entirely covered by some path in the MPC. We show that in the case of long reads (subpaths), the generalized problem can be solved in polynomial-time by a reduction to the classical MPC Problem. We also consider the weighted case, and show that it can be solved in polynomial-time by a reduction to a min-cost circulation problem. As a side result, we also improve the time complexity of the classical minimum weight MPC Problem. In the case of paired-end reads (pairs of subpaths), the generalized problem becomes NP-hard, but we show that it is fixed-parameter tractable (FPT) in the total number of constraints. This computational dichotomy between long reads and paired-end reads is also a general insight into multi-assembly problems. en
dc.language.iso eng
dc.relation.ispartof BMC Bioinformatics
dc.relation.uri http://www.biomedcentral.com/1471-2105/15/S9/S5
dc.rights en
dc.subject 113 Computer and information sciences en
dc.title On the complexity of Minimum Path Cover with Subpath Constraints for multi-assembly en
dc.type Article
dc.description.version Peer reviewed
dc.identifier.doi https://doi.org/10.1186/1471-2105-15-S9-S5
dc.type.uri info:eu-repo/semantics/other
dc.type.uri info:eu-repo/semantics/publishedVersion
dc.contributor.pbl
dc.contributor.pbl
dc.contributor.pbl
dc.contributor.pbl
dc.contributor.pbl

Files in this item

Total number of downloads: Loading...

Files Size Format View
art_3A10.1186_2F1471_2105_15_S9_S5.pdf 1.183Mb PDF View/Open

This item appears in the following Collection(s)

Show simple item record