Phylogenetic invariants for genome rearrangements.
We review the combinatorial optimization problems in calculating edit distances between genomes and phylogenetic inference based on minimizing gene order changes. With a view to avoiding the computational cost and the "long branches attract" artifact of some tree-building methods, we explore the probabilization of genome rearrangement models prior to developing a methodology based on branch-length invariants. We characterize probabilistically the evolution of the structure of the gene adjacency set for reversals on unsigned circular genomes and, using a nontrivial recurrence relation, reversals on signed genomes. Concepts from the theory of invariants developed for the phylogenetics of homologous gene sequences can be used to derive a complete set of linear invariants for unsigned reversals, as well as for a mixed rearrangement model for signed genomes, though not for pure transposition or pure signed reversal models. The invariants are based on an extended Jukes-Cantor semigroup. We illustrate the use of these invariants to relate mitochondrial genomes from a number of invertebrate animals.
Sankoff
D
D
Centre de recherches mathématiques, University de Montréal, Québec, Canada. sankoff@ere.umontreal.ca
Blanchette
M
M
D000465:Algorithms; D000818:Animals; D019143:Evolution, Molecular; D015321:Gene Rearrangement; D007448:Invertebrates / Q000235:genetics; D008957:Models, Genetic; D015233:Models, Statistical; D010802:Phylogeny; D012680:Sensitivity and Specificity