{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,20]],"date-time":"2026-02-20T02:22:15Z","timestamp":1771554135817,"version":"3.50.1"},"reference-count":54,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2019,2,6]],"date-time":"2019-02-06T00:00:00Z","timestamp":1549411200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100002341","name":"Academy of Finland","doi-asserted-by":"publisher","award":["274977,284598,309048"],"award-info":[{"award-number":["274977,284598,309048"]}],"id":[{"id":"10.13039\/501100002341","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Fondecyt","award":["1171058"],"award-info":[{"award-number":["1171058"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2019,4,30]]},"abstract":"<jats:p>\n            The\n            <jats:italic>minimum path cover<\/jats:italic>\n            problem asks us to find a minimum-cardinality set of paths that cover all the nodes of a\n            <jats:italic>directed acyclic graph<\/jats:italic>\n            (DAG). We study the case when the size\n            <jats:italic>k<\/jats:italic>\n            of a minimum path cover is small, that is, when the DAG has a small\n            <jats:italic>width<\/jats:italic>\n            . This case is motivated by applications in\n            <jats:italic>pan-genomics<\/jats:italic>\n            , where the genomic variation of a population is expressed as a DAG. We observe that classical alignment algorithms exploiting\n            <jats:italic>sparse dynamic programming<\/jats:italic>\n            can be extended to the sequence-against-DAG case by mimicking the algorithm for sequences on each path of a minimum path cover and handling an evaluation order anomaly with\n            <jats:italic>reachability queries<\/jats:italic>\n            .\n          <\/jats:p>\n          <jats:p>\n            Namely, we introduce a general framework for DAG-extensions of sparse dynamic programming. This framework produces algorithms that are slower than their counterparts on sequences only by a factor\n            <jats:italic>k<\/jats:italic>\n            . We illustrate this on two classical problems extended to DAGs:\n            <jats:italic>longest increasing subsequence<\/jats:italic>\n            and\n            <jats:italic>longest common subsequence<\/jats:italic>\n            . For the former, we obtain an algorithm with running time\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>k<\/jats:italic>\n            |\n            <jats:italic>E<\/jats:italic>\n            |log |\n            <jats:italic>V<\/jats:italic>\n            |). This matches the optimal solution to the classical problem variant when the input sequence is modeled as a path. We obtain an analogous result for the longest common subsequence problem. We then apply this technique to the\n            <jats:italic>co-linear chaining<\/jats:italic>\n            problem, which is a generalization of the above two problems. The algorithm for this problem turns out to be more involved, needing further ingredients, such as an FM-index tailored for large alphabets and a two-dimensional range search tree modified to support range maximum queries. We also study a general sequence-to-DAG alignment formulation that allows affine gap costs in the sequence.\n          <\/jats:p>\n          <jats:p>\n            The main ingredient of the proposed framework is a new algorithm for finding a minimum path cover of a DAG (\n            <jats:italic>V<\/jats:italic>\n            ,\n            <jats:italic>E<\/jats:italic>\n            ) in\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>k<\/jats:italic>\n            |\n            <jats:italic>E<\/jats:italic>\n            |log |\n            <jats:italic>V<\/jats:italic>\n            |) time, improving all known time-bounds when\n            <jats:italic>k<\/jats:italic>\n            is small and the DAG is not too dense. In addition to boosting the sparse dynamic programming framework, an immediate consequence of this new minimum path cover algorithm is an improved space\/time tradeoff for reachability queries in arbitrary directed graphs.\n          <\/jats:p>","DOI":"10.1145\/3301312","type":"journal-article","created":{"date-parts":[[2019,2,6]],"date-time":"2019-02-06T19:16:27Z","timestamp":1549480587000},"page":"1-21","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":27,"title":["Sparse Dynamic Programming on DAGs with Small Width"],"prefix":"10.1145","volume":"15","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4454-1493","authenticated-orcid":false,"given":"Veli","family":"M\u00e4kinen","sequence":"first","affiliation":[{"name":"Helsinki Institute for Information Technology, Department of Computer Science, University of Helsinki, Helsinki, Finland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5747-8350","authenticated-orcid":false,"given":"Alexandru I.","family":"Tomescu","sequence":"additional","affiliation":[{"name":"Helsinki Institute for Information Technology, Department of Computer Science, University of Helsinki, Helsinki, Finland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7002-0803","authenticated-orcid":false,"given":"Anna","family":"Kuosmanen","sequence":"additional","affiliation":[{"name":"Helsinki Institute for Information Technology, Department of Computer Science, University of Helsinki, Helsinki, Finland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Topi","family":"Paavilainen","sequence":"additional","affiliation":[{"name":"Helsinki Institute for Information Technology, Department of Computer Science, University of Helsinki, Finland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Travis","family":"Gagie","sequence":"additional","affiliation":[{"name":"EIT, Diego Portales University, Santiago, Chile"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1099-8735","authenticated-orcid":false,"given":"Rayan","family":"Chikhi","sequence":"additional","affiliation":[{"name":"CNRS, CRIStAL, University of Lille, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,2,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/1778666.1778667"},{"key":"e_1_2_1_2_1","volume-title":"Orlin","author":"Ahuja Ravindra K.","year":"1993","unstructured":"Ravindra K. Ahuja , Thomas L. Magnanti , and James B . Orlin . 1993 . Network Flows : Theory, Algorithms, and Applications. Prentice-Hall , Inc., Upper Saddle River, NJ. Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin. 1993. Network Flows: Theory, Algorithms, and Applications. Prentice-Hall, Inc., Upper Saddle River, NJ."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1999.1063"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746612"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591885"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40450-4_12"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/1370949"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497498"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/BDCloud.2014.118"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1186\/s13059-015-0587-3"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702403098"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2010.04.003"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/146637.146650"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/146637.146656"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1023\/B:ORDE.0000034609.99940.fb"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1082036.1082039"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(75)90103-X"},{"key":"e_1_2_1_18_1","first-page":"701","article-title":"Note on Dilworth\u2019s decomposition theorem for partially ordered sets","volume":"7","author":"Fulkerson D. R.","year":"1956","unstructured":"D. R. Fulkerson . 1956 . Note on Dilworth\u2019s decomposition theorem for partially ordered sets . Proc. Amer. Math. Soc. 7 , 4 (1956), 701 -- 702 . D. R. Fulkerson. 1956. Note on Dilworth\u2019s decomposition theorem for partially ordered sets. Proc. Amer. Math. Soc. 7, 4 (1956), 701--702.","journal-title":"Proc. Amer. Math. Soc."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/800057.808675"},{"key":"e_1_2_1_20_1","volume-title":"Variation graph toolkit improves read mapping by representing genetic variation in the reference. Nature Biotechnol. 36 (Aug","author":"Garrison Erik","year":"2018","unstructured":"Erik Garrison , Jouni Sir\u00e9n , Adam M. Novak , Glenn Hickey , Jordan M. Eizenga , Eric T. Dawson , William Jones , Shilpa Garg , Charles Markello , Michael F. Lin , Benedict Paten , and Richard Durbin . 2018. Variation graph toolkit improves read mapping by representing genetic variation in the reference. Nature Biotechnol. 36 (Aug . 2018 ), 875. Erik Garrison, Jouni Sir\u00e9n, Adam M. Novak, Glenn Hickey, Jordan M. Eizenga, Eric T. Dawson, William Jones, Shilpa Garg, Charles Markello, Michael F. Lin, Benedict Paten, and Richard Durbin. 2018. Variation graph toolkit improves read mapping by representing genetic variation in the reference. Nature Biotechnol. 36 (Aug. 2018), 875."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/18.suppl_1.S181"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/070685373"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/0202019"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/99935.99944"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1929934.1929941"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-89929-9_7"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1186\/s12859-016-1103-9"},{"key":"e_1_2_1_28_1","volume-title":"Tomescu","author":"M\u00e4kinen Veli","year":"2015","unstructured":"Veli M\u00e4kinen , Djamal Belazzougui , Fabio Cunial , and Alexandru I . Tomescu . 2015 . Genome-Scale Algorithm Design. Cambridge University Press . Veli M\u00e4kinen, Djamal Belazzougui, Fabio Cunial, and Alexandru I. Tomescu. 2015. Genome-Scale Algorithm Design. Cambridge University Press."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2105-13-255"},{"key":"e_1_2_1_30_1","volume-title":"Proceedings of the IAPR Workshop on Structural and Syntactic Pattern Recognition. 22--33","author":"Manber U.","unstructured":"U. Manber and S. Wu . 1992. Approximate string matching with arbitrary costs for text and hypertext . In Proceedings of the IAPR Workshop on Structural and Syntactic Pattern Recognition. 22--33 . U. Manber and S. Wu. 1992. Approximate string matching with arbitrary costs for text and hypertext. In Proceedings of the IAPR Workshop on Structural and Syntactic Pattern Recognition. 22--33."},{"key":"e_1_2_1_31_1","first-page":"118","article-title":"Computational pan-genomics: Status, promises and challenges","volume":"19","author":"Tobias Marschall","year":"2018","unstructured":"Tobias Marschall et al. 2018 . Computational pan-genomics: Status, promises and challenges . Brief. Bioinform. 19 , 1 (2018), 118 -- 135 . Tobias Marschall et al. 2018. Computational pan-genomics: Status, promises and challenges. Brief. Bioinform. 19, 1 (2018), 118--135.","journal-title":"Brief. Bioinform."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.5555\/313651.313661"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(99)00333-3"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-43681-4_20"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.1979.234213"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488705"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-60044-2_51"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1038\/nmeth.4197"},{"key":"e_1_2_1_39_1","doi-asserted-by":"crossref","unstructured":"Mikko Rautiainen and Tobias Marschall. 2017. Aligning sequences to general graphs in O(V+mE) time Mikko Rautiainen and Tobias Marschall (Eds.). bioRxiv 216127.  Mikko Rautiainen and Tobias Marschall. 2017. Aligning sequences to general graphs in O ( V + mE ) time Mikko Rautiainen and Tobias Marschall (Eds.). bioRxiv 216127.","DOI":"10.1101\/216127"},{"key":"e_1_2_1_40_1","volume-title":"S-9","author":"Rizzi Romeo","year":"2014","unstructured":"Romeo Rizzi , Alexandru I. Tomescu , and Veli M\u00e4kinen . 2014. On the complexity of minimum path cover with subpath constraints for multi-assembly. BMC Bioinform. 15 , S-9 ( 2014 ), S5. Romeo Rizzi, Alexandru I. Tomescu, and Veli M\u00e4kinen. 2014. On the complexity of minimum path cover with subpath constraints for multi-assembly. BMC Bioinform. 15, S-9 (2014), S5."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1137\/0207011"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-39763-2_33"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974768.2"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCBB.2013.2297101"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2016.2631160"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCBB.2015.2418753"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1186\/s12859-015-0530-3"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(77)90031-X"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01683268"},{"key":"e_1_2_1_50_1","volume-title":"Approximation Algorithms","author":"Vazirani Vijay V.","unstructured":"Vijay V. Vazirani . 2001. Approximation Algorithms . Springer-Verlag . Vijay V. Vazirani. 2001. Approximation Algorithms. Springer-Verlag."},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1186\/s12859-015-0533-0"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.5220\/0004903502330238"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-07953-0_20"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920879"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3301312","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3301312","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T01:02:04Z","timestamp":1750208524000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3301312"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,2,6]]},"references-count":54,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2019,4,30]]}},"alternative-id":["10.1145\/3301312"],"URL":"https:\/\/doi.org\/10.1145\/3301312","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,2,6]]},"assertion":[{"value":"2018-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-02-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}