Résumé
Rapidly increasing numbers of organisms have been completely sequenced and most of their genes identified; homologies among these genes are also getting established. It thus has become possible to represent whole genomes as ordered lists of gene identifiers and to study the evolution of these entities through computational means, in systematics as well as in comparative genomics. While dealing with rearrangements is nontrivial, the biggest stumbling block remains gene duplication and losses, leading to considerable difficulties in determining orthologs among gene families—all the more since orthology determination has a direct impact on the selection of rearrangements. None of the existing phylogenetic reconstruction methods that use gene orders is able to exploit the information present in complete gene families—most assume singleton families and equal gene content, limiting the evolutionary operations to rearrangements, while others make it so by eliminating nonshared genes and selecting one exemplar from each gene family. In this work, we leverage our past work on genomic distances, on tight bounding of parsimony scores through linear programming, and on divide-and-conquer methods for large-scale reconstruction to build the first computational approach to phylogenetic reconstruction from complete gene order data, taking into account not only rearrangements, but also duplication and loss of genes. Our approach can handle mulitchromosomal data and gene families of arbitrary sizes and scale up to hundreds of genomes through the use of disk-covering methods. We present experimental results on simulated unichromosomal genomes in a range of sizes consistent with prokaryotes. Our results confirm that equalizing gene content, as done in existing phylogenetic tools, discards important phylogenetic information; in particular, our approach easily outperforms that most commonly referenced tool, MGR, often returning trees with less that one quarter of the errors found in the MGR trees.