title: Ancestral genome organization: an alignment approach.
abstract: 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.
authors.affiliation: Département d'Informatique et de Recherche Opérationnelle (DIRO), Université de Montréal, Montreal, Canada.
authors.forename: Patrick
authors.initials: P
authors.lastname: Holloway
authors.forename: Krister
authors.initials: K
authors.lastname: Swenson
authors.forename: David
authors.initials: D
authors.lastname: Ardell
authors.forename: Nadia
authors.initials: N
authors.lastname: El-Mabrouk
mesh_terms: D001407:Bacillus / Q000235:genetics*; D003198:Computer Simulation; D019143:Evolution, Molecular; D020440:Gene Duplication / Q000235:genetics; D016680:Genome, Bacterial / Q000235:genetics*; D023281:Genomics / Q000379:methods*; D008957:Models, Genetic; D005810:Multigene Family / Q000235:genetics; D010802:Phylogeny; D012335:RNA, Ribosomal / Q000235:genetics; D016415:Sequence Alignment / Q000379:methods*
chemical_list: D012335:RNA, Ribosomal