Ancestral Genome Organization: An Alignment Approach
| Autor: | Krister M. Swenson, David H. Ardell, Patrick Holloway, Nadia El-Mabrouk |
|---|---|
| Rok vydání: | 2013 |
| Předmět: |
Theoretical computer science
Linear programming Bacillus Biology Genome Evolution Molecular Gene Duplication Gene duplication Genetics Computer Simulation Point (geometry) Molecular Biology Phylogeny Comparative genomics Models Genetic Heuristic Genomics Quantitative Biology::Genomics Dynamic programming Computational Mathematics Computational Theory and Mathematics RNA Ribosomal Multigene Family Modeling and Simulation A priori and a posteriori Sequence Alignment Genome Bacterial |
| Zdroj: | Journal of Computational Biology. 20:280-295 |
| ISSN: | 1557-8666 1066-5277 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|