title: Phylogenetic invariants for genome rearrangements.
abstract: 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.
authors.affiliation: Centre de recherches mathématiques, University de Montréal, Québec, Canada. sankoff@ere.umontreal.ca
authors.forename: D
authors.initials: D
authors.lastname: Sankoff
authors.forename: M
authors.initials: M
authors.lastname: Blanchette
mesh_terms: 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