{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,18]],"date-time":"2026-01-18T03:29:17Z","timestamp":1768706957099,"version":"3.49.0"},"reference-count":50,"publisher":"Springer Science and Business Media LLC","issue":"S9","content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["BMC Bioinformatics"],"published-print":{"date-parts":[[2014,9]]},"DOI":"10.1186\/1471-2105-15-s9-s5","type":"journal-article","created":{"date-parts":[[2014,9,10]],"date-time":"2014-09-10T15:04:10Z","timestamp":1410361450000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":25,"title":["On the complexity of Minimum Path Cover with Subpath Constraints for multi-assembly"],"prefix":"10.1186","volume":"15","author":[{"given":"Romeo","family":"Rizzi","sequence":"first","affiliation":[]},{"given":"Alexandru I","family":"Tomescu","sequence":"additional","affiliation":[]},{"given":"Veli","family":"M\u00e4kinen","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2014,9,10]]},"reference":[{"issue":"3","key":"6566_CR1","doi-asserted-by":"publisher","first-page":"426","DOI":"10.1101\/gr.1304504","volume":"14","author":"Y Xing","year":"2004","unstructured":"Xing Y: The multiassembly problem: reconstructing multiple transcript isoforms from EST fragment mixtures. Genome Research. 2004, 14 (3): 426-441. 10.1101\/gr.1304504.","journal-title":"Genome Research"},{"key":"6566_CR2","doi-asserted-by":"publisher","first-page":"621","DOI":"10.1038\/nmeth.1226","volume":"5","author":"A Mortazavi","year":"2008","unstructured":"Mortazavi A: Mapping and quantifying mammalian transcriptomes by RNA-Seq. Nature Methods. 2008, 5: 621-628. 10.1038\/nmeth.1226.","journal-title":"Nature Methods"},{"issue":"11","key":"6566_CR3","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1038\/nmeth.1371","volume":"6","author":"S Pepke","year":"2009","unstructured":"Pepke S, Wold B, Mortazavi A: Computation for ChIP-seq and RNA-seq studies. Nature methods. 2009, 6 (11): 22-32.","journal-title":"Nature methods"},{"issue":"1","key":"6566_CR4","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1016\/j.tig.2007.10.001","volume":"24","author":"E Kim","year":"2008","unstructured":"Kim E, Goren A, Ast G: Insights into the connection between cancer and alternative splicing. Trends in genetics: TIG. 2008, 24 (1): 7-10. 10.1016\/j.tig.2007.10.001.","journal-title":"Trends in genetics: TIG"},{"issue":"9","key":"6566_CR5","doi-asserted-by":"publisher","first-page":"1900","DOI":"10.1016\/j.febslet.2005.02.047","volume":"579","author":"N Lopez-Bigas","year":"2005","unstructured":"Lopez-Bigas N, Audit B, Ouzounis C, Parra G, Guigo R: Are splicing mutations the most frequent cause of hereditary disease?. FEBS Letters. 2005, 579 (9): 1900-1903. 10.1016\/j.febslet.2005.02.047.","journal-title":"FEBS Letters"},{"issue":"1","key":"6566_CR6","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1038\/nrg2484","volume":"10","author":"Z Wang","year":"2009","unstructured":"Wang Z, Gerstein M, Snyder M: RNA-Seq: a revolutionary tool for transcriptomics. Nature Reviews Genetics. 2009, 10 (1): 57-63. 10.1038\/nrg2484.","journal-title":"Nature Reviews Genetics"},{"issue":"7403","key":"6566_CR7","doi-asserted-by":"crossref","first-page":"395","DOI":"10.1038\/nature10933","volume":"486","author":"S Shah","year":"2012","unstructured":"Shah S: The clonal and mutational evolution spectrum of primary triple-negative breast cancers. Nature. 2012, 486 (7403): 395-399.","journal-title":"Nature"},{"key":"6566_CR8","doi-asserted-by":"publisher","first-page":"511","DOI":"10.1038\/nbt.1621","volume":"28","author":"C Trapnell","year":"2010","unstructured":"Trapnell C: Transcript assembly and quantification by RNA-Seq reveals unannotated transcripts and isoform switching during cell differentiation. Nature Biotechnology. 2010, 28: 511-515. 10.1038\/nbt.1621.","journal-title":"Nature Biotechnology"},{"key":"6566_CR9","doi-asserted-by":"publisher","first-page":"138","DOI":"10.1007\/978-3-642-12683-3_10.","volume-title":"Inference of isoforms from short sequence reads. RECOMB - Research in Computational Molecular Biology","author":"J Feng","year":"2010","unstructured":"Feng J: Inference of isoforms from short sequence reads. RECOMB - Research in Computational Molecular Biology. Edited by: Berger, B. 2010, LNCS, 6044: 138-157. 10.1007\/978-3-642-12683-3_10."},{"issue":"11","key":"6566_CR10","doi-asserted-by":"publisher","first-page":"1693","DOI":"10.1089\/cmb.2011.0171","volume":"18","author":"W Li","year":"2011","unstructured":"Li W: IsoLasso: a LASSO regression approach to RNA-Seq based transcriptome assembly. Journal of Computational Biology. 2011, 18 (11): 1693-1707. 10.1089\/cmb.2011.0171.","journal-title":"Journal of Computational Biology"},{"key":"6566_CR11","doi-asserted-by":"publisher","first-page":"178","DOI":"10.1007\/978-3-642-33122-0_14","volume-title":"WABI - 12th Workshop on Algorithms for Bioinformatics","author":"YY Lin","year":"2012","unstructured":"Lin YY: CLIIQ: Accurate Comparative Detection and Quantification of Expressed Isoforms in a Population. WABI - 12th Workshop on Algorithms for Bioinformatics. 2012, LNCS, 7534: 178-189. 10.1007\/978-3-642-33122-0_14."},{"issue":"50","key":"6566_CR12","doi-asserted-by":"publisher","first-page":"19867","DOI":"10.1073\/pnas.1113972108","volume":"108","author":"JJ Li","year":"2011","unstructured":"Li JJ: Sparse linear modeling of next-generation mRNA sequencing (RNA-Seq) data for isoform discovery and abundance estimation. Proceedings National Academy of Sciences. 2011, 108 (50): 19867-19872. 10.1073\/pnas.1113972108.","journal-title":"Proceedings National Academy of Sciences"},{"issue":"5","key":"6566_CR13","doi-asserted-by":"publisher","first-page":"503","DOI":"10.1038\/nbt.1633","volume":"28","author":"M Guttman","year":"2010","unstructured":"Guttman M: Ab initio reconstruction of cell type-specific transcriptomes in mouse reveals the conserved multi-exonic structure of lincRNAs. Nature Biotechnology. 2010, 28 (5): 503-510. 10.1038\/nbt.1633.","journal-title":"Nature Biotechnology"},{"issue":"3","key":"6566_CR14","doi-asserted-by":"publisher","first-page":"519","DOI":"10.1101\/gr.142232.112","volume":"23","author":"AM Mezlini","year":"2012","unstructured":"Mezlini AM: iReckon: Simultaneous isoform discovery and abundance estimation from RNA-seq data. Genome Research. 2012, 23 (3): 519-529.","journal-title":"Genome Research"},{"key":"6566_CR15","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1145\/2382936.2382983","volume-title":"ACM Conference on Bioinformatics, Computational Biology and Biomedical Informatics","author":"S Mangul","year":"2012","unstructured":"Mangul S: An integer programming approach to novel transcript reconstruction from paired-end RNA-Seq reads. ACM Conference on Bioinformatics, Computational Biology and Biomedical Informatics. Edited by: Ranka, S. 2012, ACM, New York, NY, USA, 369-376."},{"issue":"1","key":"6566_CR16","doi-asserted-by":"publisher","first-page":"162","DOI":"10.1186\/1471-2105-12-162","volume":"12","author":"Z Xia","year":"2011","unstructured":"Xia Z: NSMAP: A method for spliced isoforms identification and quantification from RNA-Seq. BMC Bioinformatics. 2011, 12 (1): 162-10.1186\/1471-2105-12-162.","journal-title":"BMC Bioinformatics"},{"key":"6566_CR17","unstructured":"Bernard E: Efficient RNA Isoform Identification and Quantification from RNA-Seq Data with Network Flows. preprint: SU2C-AACR-DT0409; SES-0835531; CCF-0939370."},{"issue":"1","key":"6566_CR18","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s12561-012-9069-2","volume":"5","author":"D Hiller","year":"2013","unstructured":"Hiller D: Simultaneous Isoform Discovery and Quantification from RNA-Seq. Statistics in Biosciences. 2013, 5 (1): 1-19. 10.1007\/s12561-013-9088-7.","journal-title":"Statistics in Biosciences"},{"issue":"S-5","key":"6566_CR19","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1186\/1471-2105-14-S5-S14","volume":"14","author":"L Song","year":"2013","unstructured":"Song L, Florea L: CLASS: constrained transcript assembly of RNA-seq reads. BMC Bioinformatics. 2013, 14 (S-5): 14-Proceedings paper from RECOMB-seq: Third Annual Recomb Satellite Workshop on Massively Parallel Sequencing Beijing, China. 11-12 April 2013","journal-title":"BMC Bioinformatics"},{"issue":"10","key":"6566_CR20","doi-asserted-by":"publisher","first-page":"1250","DOI":"10.1093\/bioinformatics\/btt127","volume":"29","author":"E Bao","year":"2013","unstructured":"Bao E, Jiang T, Girke T: Branch: boosting rna-seq assemblies with partial or related genomic sequences. Bioinformatics. 2013, 29 (10): 1250-1259. 10.1093\/bioinformatics\/btt127.","journal-title":"Bioinformatics"},{"key":"6566_CR21","doi-asserted-by":"publisher","first-page":"329","DOI":"10.3389\/fmicb.2012.00329","volume":"3","author":"N Beerenwinkel","year":"2012","unstructured":"Beerenwinkel N, Gu\u00a8nthard HF, Roth V, Metzner KJ: Challenges and opportunities in estimating viral genetic diversity from next-generation sequencing data. Frontiers in Microbiology. 2012, 3: 329-","journal-title":"Frontiers in Microbiology"},{"key":"6566_CR22","first-page":"94","volume-title":"Bioinformatics and Biomedicine Workshops","author":"N Mancuso","year":"2011","unstructured":"Mancuso N, Tork B, Skums P, Mandoiu II, Zelikovsky A: Viral quasispecies reconstruction from amplicon 454 pyrosequencing reads. Bioinformatics and Biomedicine Workshops. 2011, IEEE, Atlanta, GA, USA, 94-101."},{"issue":"Suppl 2","key":"6566_CR23","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1186\/1471-2164-13-S2-S4","volume":"13","author":"S O'Neil","year":"2012","unstructured":"O'Neil S, Emrich S: Haplotype and minimum-chimerism consensus determination using short sequence data. BMC Genomics. 2012, 13 (Suppl 2): 4-10.1186\/1471-2164-13-S2-S4.","journal-title":"BMC Genomics"},{"key":"6566_CR24","first-page":"130","volume-title":"Bioinformatics and Biomedicine Workshops","author":"A Huang","year":"2011","unstructured":"Huang A, Kantor R, DeLong A, Schreier L, Istrail S: Qcolors: An algorithm for conservative viral quasispecies reconstruction from short and non-contiguous next generation sequencing reads. Bioinformatics and Biomedicine Workshops. 2011, IEEE, Atlanta, GA, USA, 130-136."},{"key":"6566_CR25","doi-asserted-by":"crossref","unstructured":"Eriksson N, Pachter L, Mitsuya Y, Rhee SY, Wang C, Gharizadeh B, Ronaghi M, Shafer RW, Beerenwinkel N: Viral population estimation using pyrosequencing. PLoS Computational Biology. 2008, 4 (5):","DOI":"10.1371\/journal.pcbi.1000074"},{"issue":"1","key":"6566_CR26","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1186\/1471-2105-12-119","volume":"12","author":"O Zagordi","year":"2011","unstructured":"Zagordi O, Bhattacharya A, Eriksson N, Beerenwinkel N: ShoRAH: estimating the genetic diversity of a mixed sample from next-generation sequencing data. BMC Bioinformatics. 2011, 12 (1): 119-10.1186\/1471-2105-12-119.","journal-title":"BMC Bioinformatics"},{"key":"6566_CR27","first-page":"159","volume-title":"ISBRA Lecture Notes in Computer Science","author":"K Westbrooks","year":"2008","unstructured":"Westbrooks K, Astrovskaya I, Campo DS, Khudyakov Y, Berman P, Zelikovsky A: HCV Quasispecies Assembly Using Network Flows. ISBRA Lecture Notes in Computer Science. Edited by: Mandoiu, I.I., Sunderraman, R., Zelikovsky, A. 2008, Springer, Berlin, 4983: 159-170. 10.1007\/978-3-540-79450-9_15."},{"issue":"7221","key":"6566_CR28","doi-asserted-by":"publisher","first-page":"470","DOI":"10.1038\/nature07509","volume":"456","author":"ET Wang","year":"2008","unstructured":"Wang ET, Sandberg R, Luo S, Khrebtukova I, Zhang L, Mayr C, Kingsmore SF, Schroth GP, Burge CB: Alternative isoform regulation in human tissue transcriptomes. Nature. 2008, 456 (7221): 470-476. 10.1038\/nature07509.","journal-title":"Nature"},{"issue":"4","key":"6566_CR29","first-page":"701","volume":"7","author":"DR Fulkerson","year":"1956","unstructured":"Fulkerson DR: Note on dilworth's decomposition theorem for partially ordered sets. Proceedings of the American Mathematical Society. 1956, 7 (4): 701-702.","journal-title":"Proceedings of the American Mathematical Society"},{"issue":"R2","key":"6566_CR30","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1093\/hmg\/ddq416","volume":"19","author":"EE Schadt","year":"2010","unstructured":"Schadt EE, Turner S, Kasarskis A: A window into third-generation sequencing. Human molecular genetics. 2010, 19 (R2): 227-240. 10.1093\/hmg\/ddq416.","journal-title":"Human molecular genetics"},{"issue":"8","key":"6566_CR31","doi-asserted-by":"publisher","first-page":"1000147","DOI":"10.1371\/journal.pcbi.1000147","volume":"4","author":"M Sammeth","year":"2008","unstructured":"Sammeth M, Foissac S, Guig\u00b4o R: A General Definition and Nomenclature for Alternative Splicing Events. PLoS Computational Biology. 2008, 4 (8): 1000147-10.1371\/journal.pcbi.1000147.","journal-title":"PLoS Computational Biology"},{"key":"6566_CR32","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1109\/SFCS.1997.646102","volume-title":"38th Annual Symposium on Foundations of Computer Science (FOCS'97)","author":"M Farach","year":"1997","unstructured":"Farach M: Optimal suffix tree construction with large alphabets. 38th Annual Symposium on Foundations of Computer Science (FOCS'97). 1997, IEEE Computer Society, Washington, DC, USA, 137-143."},{"key":"6566_CR33","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511574931","volume-title":"Algorithms on Strings, Trees, and Sequences - Computer Science and Computational Biology","author":"D Gusfield","year":"1997","unstructured":"Gusfield D: Algorithms on Strings, Trees, and Sequences - Computer Science and Computational Biology. 1997, Cambridge University Press, Cambridge UK"},{"issue":"4","key":"6566_CR34","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1016\/0020-0190(92)90176-V","volume":"41","author":"D Gusfield","year":"1992","unstructured":"Gusfield D, Landau GM, Schieber B: An efficient algorithm for the all pairs suffix-prefix problem. Inf Process Lett. 1992, 41 (4): 181-185. 10.1016\/0020-0190(92)90176-V.","journal-title":"Inf Process Lett"},{"issue":"5","key":"6566_CR35","doi-asserted-by":"publisher","first-page":"1013","DOI":"10.1137\/0218069","volume":"18","author":"HN Gabow","year":"1989","unstructured":"Gabow HN, Tarjan RE: Faster scaling algorithms for network problems. SIAM J Comput. 1989, 18 (5): 1013-1036. 10.1137\/0218069.","journal-title":"SIAM J Comput"},{"key":"6566_CR36","doi-asserted-by":"publisher","first-page":"692645","DOI":"10.1155\/2013\/692645","volume":"2013","author":"W Pijls","year":"2013","unstructured":"Pijls W, Potharst R: Another note on dilworth's decomposition theorem. Journal of Discrete Mathematics. 2013, 2013: 692645-","journal-title":"Journal of Discrete Mathematics"},{"key":"6566_CR37","first-page":"440","volume-title":"WABI 2013 - 13th Workshop on Algorithms for Bioinformatics","author":"AI Tomescu","year":"2013","unstructured":"Tomescu AI, Kuosmanen A, Rizzi R, M\u00a8akinen V: A Novel Combinatorial Method for Estimating Transcript Expression with RNA-Seq: Bounding the Number of Paths. WABI 2013 - 13th Workshop on Algorithms for Bioinformatics. 2013, LNBI, 8126: 440-451."},{"issue":"Suppl 5","key":"6566_CR38","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1186\/1471-2105-14-S5-S15","volume":"14","author":"AI Tomescu","year":"2013","unstructured":"Tomescu AI, Kuosmanen A, Rizzi R, M\u00a8akinen V: A Novel Min-Cost Flow Method for Estimating Transcript Expression with RNA-Seq. BMC Bioinformatics. 2013, 14 (Suppl 5): 15-Proceedings paper from RECOMB-seq: Third Annual Recomb Satellite Workshop on Massively Parallel Sequencing Beijing, China. 11-12 April 2013","journal-title":"BMC Bioinformatics"},{"issue":"S-14","key":"6566_CR39","doi-asserted-by":"publisher","first-page":"8","DOI":"10.1186\/1471-2105-13-S14-S8","volume":"13","author":"F Nadalin","year":"2012","unstructured":"Nadalin F, Vezzi F, Policriti A: GapFiller: a de novo assembly approach to fill the gap within paired reads. BMC Bioinformatics. 2012, 13 (S-14): 8-","journal-title":"BMC Bioinformatics"},{"issue":"6","key":"6566_CR40","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1186\/gb-2012-13-6-r56","volume":"13","author":"M Boetzer","year":"2012","unstructured":"Boetzer M, Pirovano W: Toward almost closed genomes with gapfiller. Genome Biology. 2012, 13 (6): 56-10.1186\/gb-2012-13-6-r56.","journal-title":"Genome Biology"},{"key":"6566_CR41","first-page":"126","volume-title":"Lecture Notes in Computer Science","author":"N Beerenwinkel","year":"2014","unstructured":"Beerenwinkel N, Beretta S, Bonizzoni P, Dondi R, Pirola Y: Covering pairs in directed acyclic graphs. In: Language and Automata Theory and Applications. Lecture Notes in Computer Science. 2014, Springer, Berlin, 8370: 126-137. 10.1007\/978-3-319-04921-2_10."},{"key":"6566_CR42","doi-asserted-by":"crossref","unstructured":"Dilworth RP: A Decomposition Theorem for Partially Ordered Sets. The Annals of Mathematics. 1950, 51 (1):","DOI":"10.2307\/1969503"},{"issue":"4","key":"6566_CR43","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1137\/0202019","volume":"2","author":"JE Hopcroft","year":"1973","unstructured":"Hopcroft JE, Karp RM: An n5\/2 algorithm for maximum matchings in bipartite graphs. SIAM J Comput. 1973, 2 (4): 225-231. 10.1137\/0202019.","journal-title":"SIAM J Comput"},{"issue":"3","key":"6566_CR44","doi-asserted-by":"publisher","first-page":"596","DOI":"10.1145\/28869.28874","volume":"34","author":"ML Fredman","year":"1987","unstructured":"Fredman ML, Tarjan RE: Fibonacci heaps and their uses in improved network optimization algorithms. J ACM. 1987, 34 (3): 596-615. 10.1145\/28869.28874.","journal-title":"J ACM"},{"key":"6566_CR45","volume-title":"Network Flows: Theory, Algorithms, and Applications","author":"RK Ahuja","year":"1993","unstructured":"Ahuja RK, Magnanti TL, Orlin JB: Network Flows: Theory, Algorithms, and Applications. 1993, Prentice-Hall, Inc., Upper Saddle River, NJ, USA"},{"key":"6566_CR46","doi-asserted-by":"publisher","first-page":"765","DOI":"10.1145\/2488608.2488705","volume-title":"STOC '13","author":"JB Orlin","year":"2013","unstructured":"Orlin JB: Max flows in O(nm) time, or better. In: Proceedings of the 45th Annual ACM Symposium on the Theory of Computing. STOC '13. 2013, ACM, New York, NY, USA, 765-774."},{"key":"6566_CR47","volume-title":"Combinatorial Optimization - Polyhedra and Efficiency","author":"A Schrijver","year":"2003","unstructured":"Schrijver A: Combinatorial Optimization - Polyhedra and Efficiency. 2003, Springer, Berlin"},{"key":"6566_CR48","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1007\/BF01585705","volume":"53","author":"RK Ahuja","year":"1992","unstructured":"Ahuja RK, Goldberg AV, Orlin JB, Tarjan RE: Finding minimum-cost flows by double scaling. Mathematical Programming. 1992, 53: 243-266. 10.1007\/BF01585705.","journal-title":"Mathematical Programming"},{"issue":"4","key":"6566_CR49","doi-asserted-by":"publisher","first-page":"815","DOI":"10.1145\/115234.115366","volume":"38","author":"HN Gabow","year":"1991","unstructured":"Gabow HN, Tarjan RE: Faster scaling algorithms for general graph matching problems. J ACM. 1991, 38 (4): 815-853. 10.1145\/115234.115366.","journal-title":"J ACM"},{"key":"6566_CR50","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey MR, Johnson DS: Computers and Intractability: A Guide to the Theory of NP-Completeness. 1979, W. H. Freeman & Co., New York, NY, USA"}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/1471-2105-15-S9-S5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,1,23]],"date-time":"2019-01-23T01:34:02Z","timestamp":1548207242000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/1471-2105-15-S9-S5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,9]]},"references-count":50,"journal-issue":{"issue":"S9","published-print":{"date-parts":[[2014,9]]}},"alternative-id":["6566"],"URL":"https:\/\/doi.org\/10.1186\/1471-2105-15-s9-s5","relation":{},"ISSN":["1471-2105"],"issn-type":[{"value":"1471-2105","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,9]]},"assertion":[{"value":"10 September 2014","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"S5"}}