title: On the inference of parsimonious indel evolutionary scenarios.
abstract: 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.
authors.affiliation: School of Computer Science, McGill University, 3480 University Street, Montreal, Quebec, H3A 2A7, Canada. lchind@po-box.mcgill.ca
authors.forename: Leonid
authors.initials: L
authors.lastname: Chindelevitch
authors.forename: Zhentao
authors.initials: Z
authors.lastname: Li
authors.forename: Eric
authors.initials: E
authors.lastname: Blais
authors.forename: Mathieu
authors.initials: M
authors.lastname: Blanchette
mesh_terms: D000465:Algorithms; D000818:Animals; D019295:Computational Biology; D019005:Cystic Fibrosis Transmembrane Conductance Regulator / Q000235:genetics; D019143:Evolution, Molecular; D053476:Extinction, Biological; D017353:Gene Deletion; D016678:Genome; D009154:Mutation; D010802:Phylogeny; D011382:Programming, Linear; D016415:Sequence Alignment
chemical_list: D019005:Cystic Fibrosis Transmembrane Conductance Regulator