Résumé
We present a comparative genomics approach for inferring ancestral genome organization and evolutionary scenarios, based on present-day genomes represented as ordered gene sequences with duplicates. We develop our methodology for a model of evolution restricted to duplication and loss, and then show how to extend it to other content-modifying operations, and to inversions. From a combinatorial point of view, the main consequence of ignoring rearrangements is the possibility of formulating the problem as an alignment problem. On the other hand, duplications and losses are asymmetric operations that are applicable to one of the two aligned sequences. Consequently, an ancestral genome can directly be inferred from a duplication-loss scenario attached to a given alignment. Although alignments are a priori simpler to handle than rearrangements, we show that a direct approach based on dynamic programming leads, at best, to an efficient heuristic. We present an exact pseudo-boolean linear programming algorithm to search for the optimal alignment along with an optimal scenario of duplications and losses. Although exponential in the worst case, we show low running times on real datasets as well as synthetic data. We apply our algorithm (*) in a phylogenetic context to the evolution of stable RNA (tRNA and rRNA) gene content and organization in Bacillus genomes. Our results lead to various biological insights, such as rates of ribosomal RNA proliferation among lineages, their role in altering tRNA gene content, and evidence of tRNA class conversion.