{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,30]],"date-time":"2026-03-30T05:12:42Z","timestamp":1774847562035,"version":"3.50.1"},"publisher-location":"Cham","reference-count":40,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319899282","type":"print"},{"value":"9783319899299","type":"electronic"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-319-89929-9_7","type":"book-chapter","created":{"date-parts":[[2018,4,17]],"date-time":"2018-04-17T18:34:13Z","timestamp":1523990053000},"page":"105-121","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":14,"title":["Using Minimum Path Cover to Boost Dynamic Programming on DAGs: Co-linear Chaining Extended"],"prefix":"10.1007","author":[{"given":"Anna","family":"Kuosmanen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Topi","family":"Paavilainen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Travis","family":"Gagie","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rayan","family":"Chikhi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alexandru","family":"Tomescu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Veli","family":"M\u00e4kinen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,4,18]]},"reference":[{"key":"7_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-540-75530-2_1","volume-title":"String Processing and Information Retrieval","author":"M Abouelhoda","year":"2007","unstructured":"Abouelhoda, M.: A chaining algorithm for mapping cdna sequences to multiple genomic sequences. In: Ziviani, N., Baeza-Yates, R. (eds.) SPIRE 2007. LNCS, vol. 4726, pp. 1\u201313. Springer, Heidelberg (2007). https:\/\/doi.org\/10.1007\/978-3-540-75530-2_1"},{"key":"7_CR2","volume-title":"Network Flows: Theory, Algorithms, and Applications","author":"RK Ahuja","year":"1993","unstructured":"Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network Flows: Theory, Algorithms, and Applications. Prentice-Hall Inc, Upper Saddle River (1993)"},{"issue":"1","key":"7_CR3","doi-asserted-by":"publisher","first-page":"82","DOI":"10.1006\/jagm.1999.1063","volume":"35","author":"A Amir","year":"2000","unstructured":"Amir, A., Lewenstein, M., Lewenstein, N.: Pattern matching in hypertext. J. Algorithms 35(1), 82\u201399 (2000)","journal-title":"J. Algorithms"},{"key":"7_CR4","doi-asserted-by":"crossref","unstructured":"Belazzougui, D.: Linear time construction of compressed text indices in compact space. In: Proceedings of the Symposium on Theory of Computing STOC 2014, pp. 148\u2013193. ACM (2014)","DOI":"10.1145\/2591796.2591885"},{"key":"7_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1007\/978-3-642-40450-4_12","volume-title":"Algorithms \u2013 ESA 2013","author":"D Belazzougui","year":"2013","unstructured":"Belazzougui, D., Cunial, F., K\u00e4rkk\u00e4inen, J., M\u00e4kinen, V.: Versatile succinct representations of the bidirectional Burrows-wheeler transform. In: Bodlaender, H.L., Italiano, G.F. (eds.) ESA 2013. LNCS, vol. 8125, pp. 133\u2013144. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-40450-4_12"},{"key":"7_CR6","doi-asserted-by":"crossref","unstructured":"Chen, Y., Chen, Y.: An efficient algorithm for answering graph reachability queries. In: 2008 IEEE 24th International Conference on Data Engineering, pp. 893\u2013902, April 2008","DOI":"10.1109\/ICDE.2008.4497498"},{"key":"7_CR7","doi-asserted-by":"crossref","unstructured":"Chen, Y., Chen, Y.: On the graph decomposition. In: 2014 IEEE Fourth International Conference on Big Data and Cloud Computing, pp. 777\u2013784, Dec 2014","DOI":"10.1109\/BDCloud.2014.118"},{"issue":"1","key":"7_CR8","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1186\/s13059-015-0587-3","volume":"16","author":"DM Church","year":"2015","unstructured":"Church, D.M., Schneider, V.A., Steinberg, K.M., Schatz, M.C., Quinlan, A.R., Chin, C.-S., Kitts, P.A., Aken, B., Marth, G.T., Hoffman, M.M., et al.: Extending reference assembly models. Genome Biol. 16(1), 13 (2015)","journal-title":"Genome Biol."},{"issue":"5","key":"7_CR9","doi-asserted-by":"publisher","first-page":"1338","DOI":"10.1137\/S0097539702403098","volume":"32","author":"E Cohen","year":"2003","unstructured":"Cohen, E., Halperin, E., Kaplan, H., Zwick, U.: Reachability and distance queries via 2-hop labels. SIAM J. Comput. 32(5), 1338\u20131355 (2003)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"7_CR10","doi-asserted-by":"publisher","first-page":"519","DOI":"10.1145\/146637.146650","volume":"39","author":"D Eppstein","year":"1992","unstructured":"Eppstein, D., Galil, Z., Giancarlo, R., Italiano, G.F.: Sparse dynamic programming I: linear cost functions. J. ACM 39(3), 519\u2013545 (1992)","journal-title":"J. ACM"},{"issue":"4","key":"7_CR11","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1023\/B:ORDE.0000034609.99940.fb","volume":"20","author":"S Felsner","year":"2003","unstructured":"Felsner, S., Raghavan, V., Spinrad, J.: Recognition algorithms for orders of small width and graphs of small Dilworth number. Order 20(4), 351\u2013364 (2003)","journal-title":"Order"},{"issue":"4","key":"7_CR12","first-page":"701","volume":"7","author":"DR Fulkerson","year":"1956","unstructured":"Fulkerson, D.R.: Note on Dilworth\u2019s decomposition theorem for partially ordered sets. Proc. Am. Math. Soc. 7(4), 701\u2013702 (1956)","journal-title":"Proc. Am. Math. Soc."},{"key":"7_CR13","doi-asserted-by":"crossref","unstructured":"Gabow, H.N., Bentley, J.L., Tarjan, R.E.: Scaling and related techniques for geometry problems. In: Proceedings of the Sixteenth Annual ACM Symposium on Theory of Computing, STOC 1984, pp. 135\u2013143. ACM, New York (1984)","DOI":"10.1145\/800057.808675"},{"key":"7_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1007\/978-3-319-56970-3_3","volume-title":"Research in Computational Molecular Biology","author":"D Haussler","year":"2017","unstructured":"Haussler, D., Smuga-Otto, M., Paten, B., Novak, A.M., Nikitin, S., Zueva, M., Miagkov, D.: A flow procedure for the linearization of genome sequence graphs. In: Sahinalp, S.C. (ed.) RECOMB 2017. LNCS, vol. 10229, pp. 34\u201349. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-56970-3_3"},{"issue":"Suppl. 1","key":"7_CR15","doi-asserted-by":"publisher","first-page":"S181","DOI":"10.1093\/bioinformatics\/18.suppl_1.S181","volume":"18","author":"S Heber","year":"2002","unstructured":"Heber, S., Alekseyev, M., Sze, S.-H., Tang, H., Pevzner, P.A.: Splicing graphs and EST assembly problem. Bioinformatics 18(Suppl. 1), S181\u2013S188 (2002)","journal-title":"Bioinformatics"},{"issue":"4","key":"7_CR16","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1137\/0202019","volume":"2","author":"JE Hopcroft","year":"1973","unstructured":"Hopcroft, J.E., Karp, R.M.: An $$n^{5\/2}$$ algorithm for maximum matchings in Bipartite graphs. SIAM J. Comput. 2(4), 225\u2013231 (1973)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"7_CR17","doi-asserted-by":"publisher","first-page":"558","DOI":"10.1145\/99935.99944","volume":"15","author":"HV Jagadish","year":"1990","unstructured":"Jagadish, H.V.: A compression technique to materialize transitive closure. ACM Trans. Database Syst. 15(4), 558\u2013598 (1990)","journal-title":"ACM Trans. Database Syst."},{"key":"7_CR18","doi-asserted-by":"crossref","unstructured":"Kuosmanen, A., Norri, T., M\u00e4kinen, V.: Evaluating approaches to find exon chains based on long reads. Brief. Bioinform. bbw137 (2017)","DOI":"10.1093\/bib\/bbw137"},{"key":"7_CR19","doi-asserted-by":"crossref","unstructured":"Kuosmanen, A., Paavilainen, T., Gagie, T., Chikhi, R., Tomescu, A.I., M\u00e4kinen, V.: Using minimum path cover to boost dynamic programming on dags: co-linear chaining extended. CoRR, abs\/1705.08754 (2018)","DOI":"10.1007\/978-3-319-89929-9_7"},{"issue":"1","key":"7_CR20","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1186\/s12859-016-1103-9","volume":"17","author":"A Limasset","year":"2016","unstructured":"Limasset, A., Cazaux, B., Rivals, E., Peterlongo, P.: Read mapping on de Bruijn graphs. BMC Bioinform. 17(1), 237 (2016)","journal-title":"BMC Bioinform."},{"key":"7_CR21","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139940023","volume-title":"Genome-Scale Algorithm Design","author":"V M\u00e4kinen","year":"2015","unstructured":"M\u00e4kinen, V., Belazzougui, D., Cunial, F., Tomescu, A.I.: Genome-Scale Algorithm Design. Cambridge University Press, Cambridge (2015)"},{"key":"7_CR22","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1186\/1471-2105-13-255","volume":"13","author":"V M\u00e4kinen","year":"2012","unstructured":"M\u00e4kinen, V., Salmela, L., Ylinen, J.: Normalized N50 assembly metric using gap-restricted co-linear chaining. BMC Bioinform. 13, 255 (2012)","journal-title":"BMC Bioinform."},{"key":"7_CR23","unstructured":"Myers, G., Miller, W.: Chaining multiple-alignment fragments in sub-quadratic time. In: Clarkson, K.L. (ed.) Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 22\u201324 January 1995, pp. 38\u201347. ACM\/SIAM, San Francisco (1995)"},{"issue":"1\u20132","key":"7_CR24","doi-asserted-by":"publisher","first-page":"455","DOI":"10.1016\/S0304-3975(99)00333-3","volume":"237","author":"G Navarro","year":"2000","unstructured":"Navarro, G.: Improved approximate pattern matching on hypertext. Theor. Comput. Sci. 237(1\u20132), 455\u2013463 (2000)","journal-title":"Theor. Comput. Sci."},{"key":"7_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"246","DOI":"10.1007\/978-3-319-43681-4_20","volume-title":"Algorithms in Bioinformatics","author":"AM Novak","year":"2016","unstructured":"Novak, A.M., Garrison, E., Paten, B.: A graph extension of the positional Burrows-Wheeler transform and its applications. In: Frith, M., Storm Pedersen, C.N. (eds.) WABI 2016. LNCS, vol. 9838, pp. 246\u2013256. Springer, Cham (2016). https:\/\/doi.org\/10.1007\/978-3-319-43681-4_20"},{"issue":"5","key":"7_CR26","doi-asserted-by":"publisher","first-page":"520","DOI":"10.1109\/TSE.1979.234213","volume":"5","author":"SC Ntafos","year":"1979","unstructured":"Ntafos, S.C., Hakimi, S.L.: On path cover problems in digraphs and applications to program testing. IEEE Trans. Softw. Eng. 5(5), 520\u2013529 (1979)","journal-title":"IEEE Trans. Softw. Eng."},{"key":"7_CR27","doi-asserted-by":"crossref","unstructured":"Orlin, J.B.: Max flows in $$O(nm)$$ time, or better. In: Proceedings of the 45th Annual ACM Symposium on the Theory of Computing, STOC 2013, pp. 765\u2013774. ACM, New York (2013)","DOI":"10.1145\/2488608.2488705"},{"key":"7_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"318","DOI":"10.1007\/3-540-60044-2_51","volume-title":"Combinatorial Pattern Matching","author":"K Park","year":"1995","unstructured":"Park, K., Kim, D.K.: String matching in hypertext. In: Galil, Z., Ukkonen, E. (eds.) CPM 1995. LNCS, vol. 937, pp. 318\u2013329. Springer, Heidelberg (1995). https:\/\/doi.org\/10.1007\/3-540-60044-2_51"},{"issue":"4","key":"7_CR29","doi-asserted-by":"publisher","first-page":"417","DOI":"10.1038\/nmeth.4197","volume":"14","author":"R Patro","year":"2017","unstructured":"Patro, R., Duggal, G., Love, M.I., Irizarry, R.A., Kingsford, C.: Salmon provides fast and bias-aware quantification of transcript expression. Nat. Methods 14(4), 417\u2013419 (2017)","journal-title":"Nat. Methods"},{"issue":"S\u20139","key":"7_CR30","doi-asserted-by":"publisher","first-page":"S5","DOI":"10.1186\/1471-2105-15-S9-S5","volume":"15","author":"R Rizzi","year":"2014","unstructured":"Rizzi, R., Tomescu, A.I., M\u00e4kinen, V.: On the complexity of minimum path cover with subpath constraints for multi-assembly. BMC Bioinform. 15(S\u20139), S5 (2014)","journal-title":"BMC Bioinform."},{"issue":"2","key":"7_CR31","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1137\/0207011","volume":"7","author":"C-P Schnorr","year":"1978","unstructured":"Schnorr, C.-P.: An algorithm for transitive closure with linear expected time. SIAM J. Comput. 7(2), 127\u2013133 (1978)","journal-title":"SIAM J. Comput."},{"key":"7_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"462","DOI":"10.1007\/978-3-540-39763-2_33","volume-title":"Algorithms in Bioinformatics","author":"T Shibuya","year":"2003","unstructured":"Shibuya, T., Kurochkin, I.: Match chaining algorithms for cDNA mapping. In: Benson, G., Page, R.D.M. (eds.) WABI 2003. LNCS, vol. 2812, pp. 462\u2013475. Springer, Heidelberg (2003). https:\/\/doi.org\/10.1007\/978-3-540-39763-2_33"},{"key":"7_CR33","doi-asserted-by":"crossref","unstructured":"Sir\u00e9n, J.: Indexing variation graphs. In: 2017 Proceedings of the Ninteenth Workshop on Algorithm Engineering and Experiments (ALENEX), pp. 13\u201327. SIAM (2017)","DOI":"10.1137\/1.9781611974768.2"},{"issue":"2","key":"7_CR34","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1109\/TCBB.2013.2297101","volume":"11","author":"J Sir\u00e9n","year":"2014","unstructured":"Sir\u00e9n, J., V\u00e4lim\u00e4ki, N., M\u00e4kinen, V.: Indexing graphs for path queries with applications in genome research. IEEE\/ACM Trans. Comput. Biol. Bioinf. 11(2), 375\u2013388 (2014)","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinf."},{"issue":"6","key":"7_CR35","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. Bioinf. 12(6), 1345\u20131354 (2015)","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinf."},{"issue":"1","key":"7_CR36","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1186\/s12859-015-0530-3","volume":"16","author":"R Uricaru","year":"2015","unstructured":"Uricaru, R., Michotey, C., Chiapello, H., Rivals, E.: YOC, a new strategy for pairwise alignment of collinear genomes. BMC Bioinform. 16(1), 111 (2015)","journal-title":"BMC Bioinform."},{"key":"7_CR37","volume-title":"Approximation Algorithms","author":"VV Vazirani","year":"2001","unstructured":"Vazirani, V.V.: Approximation Algorithms. Springer, Heidelberg (2001)"},{"issue":"1","key":"7_CR38","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1186\/s12859-015-0533-0","volume":"16","author":"M Vyverman","year":"2015","unstructured":"Vyverman, M., De Baets, B., Fack, V., Dawyndt, P.: A long fragment aligner called ALFALFA. BMC Bioinform. 16(1), 159 (2015)","journal-title":"BMC Bioinform."},{"key":"7_CR39","doi-asserted-by":"crossref","unstructured":"Vyverman, M., De Smedt, D., Lin, Y.-C., Sterck, L., De Baets, B., Fack, V., Dawyndt, P.: Fast and Accurate cDNA mapping and splice site identification. In: Proceedings of the International Conference on Bioinformatics Models, Methods and Algorithms (BIOSTEC 2014), pp. 233\u2013238 (2014)","DOI":"10.5220\/0004903502330238"},{"key":"7_CR40","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1007\/978-3-319-07953-0_20","volume-title":"Algorithms for Computational Biology","author":"S Wandelt","year":"2014","unstructured":"Wandelt, S., Leser, U.: RRCA: ultra-fast multiple in-species genome alignments. In: Dediu, A.-H., Mart\u00edn-Vide, C., Truthe, B. (eds.) AlCoB 2014. LNCS, vol. 8542, pp. 247\u2013261. Springer, Cham (2014). https:\/\/doi.org\/10.1007\/978-3-319-07953-0_20"}],"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-319-89929-9_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,3]],"date-time":"2025-07-03T18:55:38Z","timestamp":1751568938000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-89929-9_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783319899282","9783319899299"],"references-count":40,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-89929-9_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018]]},"assertion":[{"value":"18 April 2018","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":"Paris","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"France","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2018","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21 April 2018","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"24 April 2018","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"recomb2018","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/recomb2018.fr\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}