{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,11]],"date-time":"2026-03-11T23:47:10Z","timestamp":1773272830080,"version":"3.50.1"},"publisher-location":"Cham","reference-count":42,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783031047480","type":"print"},{"value":"9783031047497","type":"electronic"}],"license":[{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022]]},"DOI":"10.1007\/978-3-031-04749-7_11","type":"book-chapter","created":{"date-parts":[[2022,5,11]],"date-time":"2022-05-11T16:13:24Z","timestamp":1652285604000},"page":"177-192","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Safety and\u00a0Completeness in\u00a0Flow Decompositions for\u00a0RNA Assembly"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9352-0088","authenticated-orcid":false,"given":"Shahbaz","family":"Khan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1590-0987","authenticated-orcid":false,"given":"Milla","family":"Kortelainen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0235-6951","authenticated-orcid":false,"given":"Manuel","family":"C\u00e1ceres","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3785-0247","authenticated-orcid":false,"given":"Lucia","family":"Williams","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5747-8350","authenticated-orcid":false,"given":"Alexandru I.","family":"Tomescu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,4,29]]},"reference":[{"key":"11_CR1","doi-asserted-by":"publisher","unstructured":"Acosta, N.O., M\u00e4kinen, V., Tomescu, A.I.: A safe and complete algorithm for metagenomic assembly. Algorithms Mol. Biol. 13(1), 3:1\u20133:12 (2018). https:\/\/doi.org\/10.1186\/s13015-018-0122-7","DOI":"10.1186\/s13015-018-0122-7"},{"issue":"6","key":"11_CR2","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1145\/360825.360855","volume":"18","author":"AV Aho","year":"1975","unstructured":"Aho, A.V., Corasick, M.J.: Efficient string matching: an aid to bibliographic search. Commun. ACM 18(6), 333\u2013340 (1975). https:\/\/doi.org\/10.1145\/360825.360855","journal-title":"Commun. ACM"},{"key":"11_CR3","unstructured":"Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network Flows - Theory, Algorithms and Applications. Prentice Hall, Upper Saddle River (1993)"},{"issue":"24","key":"11_CR4","doi-asserted-by":"publisher","first-page":"5086","DOI":"10.1093\/bioinformatics\/btz443","volume":"35","author":"JA Baaijens","year":"2019","unstructured":"Baaijens, J.A., der Roest, B.V., K\u00f6ster, J., Stougie, L., Sch\u00f6nhuth, A.: Full-length de novo viral quasispecies assembly through variation graph construction. Bioinformatics 35(24), 5086\u20135094 (2019). https:\/\/doi.org\/10.1093\/bioinformatics\/btz443","journal-title":"Bioinformatics"},{"key":"11_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1007\/978-3-030-45257-5_14","volume-title":"Research in Computational Molecular Biology","author":"Jasmijn A. Baaijens","year":"2020","unstructured":"Baaijens, Jasmijn A.., Stougie, Leen, Sch\u00f6nhuth, Alexander: Strain-aware assembly of genomes from\u00a0mixed samples using flow variation\u00a0graphs. In: Schwartz, Russell (ed.) RECOMB 2020. LNCS, vol. 12074, pp. 221\u2013222. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-45257-5_14"},{"key":"11_CR6","doi-asserted-by":"crossref","unstructured":"Caceres, M., et al.: Safety in multi-assembly via paths appearing in all path covers of a DAG. IEEE\/ACM Trans. Comput. Biol. Bioinform. (2021)","DOI":"10.1109\/TCBB.2021.3131203"},{"key":"11_CR7","doi-asserted-by":"publisher","unstructured":"Cairo, M., Medvedev, P., Acosta, N.O., Rizzi, R., Tomescu, A.I.: An optimal O(nm) algorithm for enumerating all walks common to all closed edge-covering walks of a graph. ACM Trans. Algorithms 15(4), 48:1\u201348:17 (2019). https:\/\/doi.org\/10.1145\/3341731","DOI":"10.1145\/3341731"},{"key":"11_CR8","unstructured":"Cairo, M., Rizzi, R., Tomescu, A.I., Zirondelli, E.C.: Genome assembly, from practice to theory: safe, complete and linear-time. In: Bansal, N., Merelli, E., Worrell, J. (eds.) 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, 12\u201316 July 2021, Glasgow, Scotland (Virtual Conference). LIPIcs, vol. 198, pp. 43:1\u201343:18. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2021)"},{"issue":"2\u20133","key":"11_CR9","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1016\/S0166-218X(00)00279-1","volume":"110","author":"K Cechl\u00e1rov\u00e1","year":"2001","unstructured":"Cechl\u00e1rov\u00e1, K., Lacko, V.: Persistency in combinatorial optimization problems on matroids. Discret. Appl. Math. 110(2\u20133), 121\u2013132 (2001). https:\/\/doi.org\/10.1016\/S0166-218X(00)00279-1","journal-title":"Discret. Appl. Math."},{"issue":"3","key":"11_CR10","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1016\/0167-6377(94)90049-3","volume":"15","author":"MC Costa","year":"1994","unstructured":"Costa, M.C.: Persistency in maximum cardinality bipartite matchings. Oper. Res. Lett. 15(3), 143\u2013149 (1994). https:\/\/doi.org\/10.1016\/0167-6377(94)90049-3","journal-title":"Oper. Res. Lett."},{"key":"11_CR11","unstructured":"Ford, D.R., Fulkerson, D.R.: Flows Netw. Princeton University Press, Princeton (2010)"},{"key":"11_CR12","doi-asserted-by":"crossref","unstructured":"Griebel, T., et al.: Modelling and simulating generic RNA-seq experiments with the flux simulator. Nucleic Acids Res. 40(20), 10073\u201310083 (2012)","DOI":"10.1093\/nar\/gks666"},{"key":"11_CR13","doi-asserted-by":"crossref","unstructured":"Hartman, T., Hassidim, A., Kaplan, H., Raz, D., Segalov, M.: How to split a flow? In: 2012 Proceedings IEEE INFOCOM, pp. 828\u2013836. IEEE (2012)","DOI":"10.1109\/INFCOM.2012.6195830"},{"issue":"1\/2","key":"11_CR14","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1007\/BF01188580","volume":"13","author":"JD Kececioglu","year":"1995","unstructured":"Kececioglu, J.D., Myers, E.W.: Combinatorial algorithms for DNA sequence assembly. Algorithmica 13(1\/2), 7\u201351 (1995)","journal-title":"Algorithmica"},{"key":"11_CR15","doi-asserted-by":"crossref","unstructured":"Khan, S., Kortelainen, M., C\u00e1ceres, M., Williams, L., Tomescu, A.I.: Safety and completeness in flow decompositions for RNA assembly. CoRR abs\/2201.10372 (2022)","DOI":"10.1007\/978-3-031-04749-7_11"},{"issue":"1","key":"11_CR16","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1186\/1471-2105-11-21","volume":"11","author":"C Kingsford","year":"2010","unstructured":"Kingsford, C., Schatz, M.C., Pop, M.: Assembly complexity of prokaryotic genomes using short reads. BMC Bioinform. 11(1), 21 (2010)","journal-title":"BMC Bioinform."},{"key":"11_CR17","doi-asserted-by":"crossref","unstructured":"Kloster, K., et al.: A practical fpt algorithm for flow decomposition and transcript assembly. In: 2018 Proceedings of the Twentieth Workshop on Algorithm Engineering and Experiments (ALENEX), pp. 75\u201386. SIAM (2018)","DOI":"10.1137\/1.9781611975055.7"},{"key":"11_CR18","unstructured":"Li, W.: RNASeqReadSimulator: a simple RNA-seq read simulator (2014)"},{"key":"11_CR19","doi-asserted-by":"crossref","unstructured":"Liu, R., Dickerson, J.: Strawberry: fast and accurate genome-guided transcript reconstruction and quantification from RNA-seq. PLoS Comput. Biol. 13(11), e1005851 (2017)","DOI":"10.1371\/journal.pcbi.1005851"},{"key":"11_CR20","doi-asserted-by":"publisher","unstructured":"Ma, C., Zheng, H., Kingsford, C.: Exact transcript quantification over splice graphs. In: Kingsford, C., Pisanti, N. (eds.) 20th International Workshop on Algorithms in Bioinformatics, WABI 2020, 7\u20139 September 2020, Pisa, Italy (Virtual Conference). LIPIcs, vol. 172, pp. 12:1\u201312:18. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2020). https:\/\/doi.org\/10.4230\/LIPIcs.WABI.2020.12","DOI":"10.4230\/LIPIcs.WABI.2020.12"},{"key":"11_CR21","doi-asserted-by":"publisher","unstructured":"Ma, C., Zheng, H., Kingsford, C.: Finding ranges of optimal transcript expression quantification in cases of non-identifiability. bioRxiv (2020). https:\/\/doi.org\/10.1101\/2019.12.13.875625 to appear at RECOMB 2021","DOI":"10.1101\/2019.12.13.875625"},{"key":"11_CR22","doi-asserted-by":"publisher","unstructured":"M\u00e4kinen, V., Belazzougui, D., Cunial, F., Tomescu, A.I.: Genome-Scale Algorithm Design: Biological Sequence Analysis in the Era of High-Throughput Sequencing. Cambridge University Press, London (2015). https:\/\/doi.org\/10.1017\/CBO9781139940023","DOI":"10.1017\/CBO9781139940023"},{"key":"11_CR23","doi-asserted-by":"crossref","unstructured":"Medvedev, P., Georgiou, K., Myers, G., Brudno, M.: Computability of models for sequence assembly. In: WABI, pp. 289\u2013301 (2007)","DOI":"10.1007\/978-3-540-74126-8_27"},{"key":"11_CR24","doi-asserted-by":"crossref","unstructured":"Millani, M.G., Molter, H., Niedermeier, R., Sorge, M.: Efficient algorithms for measuring the funnel-likeness of DAGs. J. Comb. Optim. 39(1), 216\u2013245 (2020)","DOI":"10.1007\/s10878-019-00464-4"},{"key":"11_CR25","doi-asserted-by":"crossref","unstructured":"Nagarajan, N., Pop, M.: Parametric complexity of sequence assembly: theory and applications to next generation sequencing. J. Comput. Biol. 16(7), 897\u2013908 (2009)","DOI":"10.1089\/cmb.2009.0005"},{"key":"11_CR26","doi-asserted-by":"publisher","unstructured":"Olsen, N., Kliewer, N., Wolbeck, L.: A study on flow decomposition methods for scheduling of electric buses in public transport based on aggregated time\u2013space network models. Central Eur. J. Oper. Res. 1\u201337 (2020). https:\/\/doi.org\/10.1007\/s10100-020-00705-6","DOI":"10.1007\/s10100-020-00705-6"},{"key":"11_CR27","unstructured":"Patro, R., Duggal, G., Kingsford, C.: Salmon: accurate, versatile and ultrafast quantification from RNA-seq data using lightweight-alignment. BioRxiv p. 021592 (2015)"},{"key":"11_CR28","doi-asserted-by":"crossref","unstructured":"Pertea, M., Pertea, G.M., Antonescu, C.M., Chang, T.C., Mendell, J.T., Salzberg, S.L.: Stringtie enables improved reconstruction of a transcriptome from RNA-seq reads. Nat. Biotechnol. 33(3), 290\u2013295 (2015)","DOI":"10.1038\/nbt.3122"},{"key":"11_CR29","doi-asserted-by":"crossref","unstructured":"Pevzner, P.A., Tang, H., Waterman, M.S.: An Eulerian path approach to DNA fragment assembly. Proc. Natl. Acad. Sci. 98(17), 9748\u20139753 (2001)","DOI":"10.1073\/pnas.171285098"},{"key":"11_CR30","doi-asserted-by":"crossref","unstructured":"Pie\u0144kosz, K., Ko\u0142ty\u015b, K.: Integral flow decomposition with minimum longest path length. Eur. J. Oper. Res. 247(2), 414\u2013420 (2015)","DOI":"10.1016\/j.ejor.2015.06.012"},{"key":"11_CR31","doi-asserted-by":"crossref","unstructured":"Shao, M., Kingsford, C.: Accurate assembly of transcripts through phase-preserving graph decomposition. Nat. Biotechnol. 35(12), 1167\u20131169 (2017)","DOI":"10.1038\/nbt.4020"},{"key":"11_CR32","doi-asserted-by":"crossref","unstructured":"Shao, M., Kingsford, C.: Theory and a heuristic for the minimum path flow decomposition problem. IEEE\/ACM Trans. Comput. Biol. Bioinform. 16(2), 658\u2013670 (2017)","DOI":"10.1109\/TCBB.2017.2779509"},{"key":"11_CR33","doi-asserted-by":"crossref","unstructured":"Srivastava, A., et al.: Alignment and mapping methodology influence transcript abundance estimation. Genome Biol. 21(1), 1\u201329 (2020)","DOI":"10.1186\/s13059-020-02151-8"},{"issue":"6","key":"11_CR34","doi-asserted-by":"publisher","first-page":"1345","DOI":"10.1109\/TCBB.2015.2418753","volume":"12","author":"AI Tomescu","year":"2015","unstructured":"Tomescu, A.I., Gagie, T., Popa, A., Rizzi, R., Kuosmanen, A., M\u00e4kinen, V.: Explaining a weighted DAG with few paths for solving genome-guided multi-assembly. IEEE ACM Trans. Comput. Biol. Bioinform. 12(6), 1345\u20131354 (2015). https:\/\/doi.org\/10.1109\/TCBB.2015.2418753","journal-title":"IEEE ACM Trans. Comput. Biol. Bioinform."},{"key":"11_CR35","doi-asserted-by":"crossref","unstructured":"Tomescu, A.I., Kuosmanen, A., Rizzi, R., M\u00e4kinen, V.: A novel min-cost flow method for estimating transcript expression with RNA-seq. BMC bioinform. 14(S5), S15 (2013)","DOI":"10.1186\/1471-2105-14-S5-S15"},{"key":"11_CR36","doi-asserted-by":"crossref","unstructured":"Tomescu, A.I., Medvedev, P.: Safe and complete contig assembly through omnitigs. J. Comput. Biol. 24(6), 590\u2013602 (2017), preliminary version appeared in RECOMB 2016","DOI":"10.1089\/cmb.2016.0141"},{"issue":"3","key":"11_CR37","doi-asserted-by":"publisher","first-page":"1390","DOI":"10.1016\/j.ejor.2006.05.043","volume":"185","author":"B Vatinlen","year":"2008","unstructured":"Vatinlen, B., Chauvet, F., Chr\u00e9tienne, P., Mahey, P.: Simple bounds and greedy algorithms for decomposing a flow into a minimal set of paths. European Journal of Operational Research 185(3), 1390\u20131401 (2008)","journal-title":"European Journal of Operational Research"},{"key":"11_CR38","doi-asserted-by":"crossref","unstructured":"Wang, Z., Gerstein, M., Snyder, M.: RNA-Seq: a revolutionary tool for transcriptomics. Nat. Rev. Genet 10(1), 57\u201363 (2009)","DOI":"10.1038\/nrg2484"},{"key":"11_CR39","doi-asserted-by":"publisher","unstructured":"Williams, L.: Reference-sim. e1005851 (2021). https:\/\/doi.org\/10.5281\/zenodo.5646910","DOI":"10.5281\/zenodo.5646910"},{"key":"11_CR40","doi-asserted-by":"crossref","unstructured":"Williams, L., Reynolds, G., Mumey, B.: Rna transcript assembly using inexact flows. In: 2019 IEEE International Conference on Bioinformatics and Biomedicine (BIBM), pp. 1907\u20131914. IEEE (2019)","DOI":"10.1109\/BIBM47256.2019.8983180"},{"key":"11_CR41","unstructured":"Williams, L., Tomescu, A., Mumey, B.M., et al.: Flow decomposition with subpath constraints. In: 21st International Workshop on Algorithms in Bioinformatics (WABI 2021). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik (2021)"},{"key":"11_CR42","doi-asserted-by":"crossref","unstructured":"Yu, T., Mu, Z., Fang, Z., Liu, X., Gao, X., Liu, J.: TransBorrow: genome-guided transcriptome assembly by borrowing assemblies from different assemblers. Genome Res. 30(8), 1181\u20131190 (2020)","DOI":"10.1101\/gr.257766.119"}],"container-title":["Lecture Notes in Computer Science","Research in Computational Molecular Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-04749-7_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,5,11]],"date-time":"2022-05-11T23:05:42Z","timestamp":1652310342000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-04749-7_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"ISBN":["9783031047480","9783031047497"],"references-count":42,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-04749-7_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022]]},"assertion":[{"value":"29 April 2022","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"RECOMB","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Research in Computational Molecular Biology","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"San Diego, CA","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"USA","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2022","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22 May 2022","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"25 May 2022","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"26","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"recomb2022","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/recomb2022.net\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"188","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"17","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"23","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"9% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3.2","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"6.5","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}