{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,11]],"date-time":"2026-03-11T23:22:15Z","timestamp":1773271335574,"version":"3.50.1"},"reference-count":19,"publisher":"World Scientific Pub Co Pte Lt","issue":"03","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. Bioinform. Comput. Biol."],"published-print":{"date-parts":[[2006,6]]},"abstract":"<jats:p> Given a multiple alignment of orthologous DNA sequences and a phylogenetic tree for these sequences, we investigate the problem of reconstructing a most parsimonious scenario of insertions and deletions capable of explaining the gaps observed in the alignment. This problem, called the Indel Parsimony Problem, is a crucial component of the problem of ancestral genome reconstruction, and its solution provides valuable information to many genome functional annotation approaches. We first show that the problem is NP-complete. Second, we provide an algorithm, based on the fractional relaxation of an integer linear programming formulation. The algorithm is fast in practice, and the solutions it produces are, in most cases, provably optimal. We describe a divide-and-conquer approach that makes it possible to solve very large instances on a simple desktop machine, while retaining guaranteed optimality. Our algorithms are tested and shown efficient and accurate on a set of 1.8 Mb mammalian orthologous sequences in the CFTR region. <\/jats:p>","DOI":"10.1142\/s0219720006002168","type":"journal-article","created":{"date-parts":[[2006,9,7]],"date-time":"2006-09-07T06:38:49Z","timestamp":1157611129000},"page":"721-744","source":"Crossref","is-referenced-by-count":27,"title":["ON THE INFERENCE OF PARSIMONIOUS INDEL EVOLUTIONARY SCENARIOS"],"prefix":"10.1142","volume":"04","author":[{"given":"LEONID","family":"CHINDELEVITCH","sequence":"first","affiliation":[{"name":"School of Computer Science, McGill University, 3480 University Street, Montreal, Quebec, H3A 2A7, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"ZHENTAO","family":"LI","sequence":"additional","affiliation":[{"name":"School of Computer Science, McGill University, 3480 University Street, Montreal, Quebec, H3A 2A7, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"ERIC","family":"BLAIS","sequence":"additional","affiliation":[{"name":"McGill Centre for Bioinformatics and School of Computer Science, McGill University, 3775 University Street, Montreal, Quebec, H3A 2B4, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"MATHIEU","family":"BLANCHETTE","sequence":"additional","affiliation":[{"name":"McGill Centre for Bioinformatics and School of Computer Science, McGill University, 3775 University Street, Montreal, Quebec, H3A 2B4, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2011,11,21]]},"reference":[{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1101\/gr.2800104"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1101\/gr.1933104"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1101\/gr.1975204"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1101\/gr.1960404"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1101\/gr.926603"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1007\/BF01734359"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.2307\/2412116"},{"key":"rf11","volume-title":"Computers and Intractability","author":"Garey M.","year":"1979"},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-78240-4"},{"key":"rf13","first-page":"649","volume":"6","author":"Hein J.","journal-title":"Mol. Biol. Evol."},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1101\/gr.1976004"},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1089\/106652703322756122"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1002\/9781118627372"},{"key":"rf18","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2105-6-63"},{"key":"rf19","volume-title":"Theory of Linear and Integer Programming","author":"Schrijver A.","year":"1998"},{"key":"rf20","doi-asserted-by":"publisher","DOI":"10.1101\/gr.809403"},{"key":"rf21","doi-asserted-by":"publisher","DOI":"10.1089\/1066527041410472"},{"key":"rf22","doi-asserted-by":"publisher","DOI":"10.1038\/nature01262"},{"key":"rf23","doi-asserted-by":"publisher","DOI":"10.1038\/nature01858"}],"container-title":["Journal of Bioinformatics and Computational Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0219720006002168","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T13:02:18Z","timestamp":1565182938000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0219720006002168"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,6]]},"references-count":19,"journal-issue":{"issue":"03","published-online":{"date-parts":[[2011,11,21]]},"published-print":{"date-parts":[[2006,6]]}},"alternative-id":["10.1142\/S0219720006002168"],"URL":"https:\/\/doi.org\/10.1142\/s0219720006002168","relation":{},"ISSN":["0219-7200","1757-6334"],"issn-type":[{"value":"0219-7200","type":"print"},{"value":"1757-6334","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,6]]}}}