Due the sheer size and complexity of genomes, it is essential to develop automated methods to analyze them. To compare genomes, one distance measure that has been proposed is to determine the minimum number of evolutionary changes needed to transform one genome into another. In recent years, great progress has been made in this area with efficient exact algorithms that can transform one genome to another applying a wide range of evolutionary operations. However, gene duplications, a common occurrence and arguably the most important evolutionary operation, have proven to be one of the most difficult evolutionary operations to integrate.
We examine the most successful gene duplication algorithms: a family of algorithms that we call the rearrangement-duplication algorithms. Rather than compare two genomes, these algorithms attempt to efficiently remove the duplicates from a genome using the fewest number of duplications and other evolutionary operations.
In this thesis we give a complete survey of all the genome halving algorithms, a highly successful group of rearrangement-duplication algorithms that efficiently and exactly handle whole genome doubling ( tetraploidization). We also introduce the genome aliquoting algorithms, a new variation on the genome halving problem, that attempts to handle unlimited scale whole genome duplications. As a new and challenging problem there are currently no efficient exact algorithms. However, early results include two approximation algorithms.
| Identifer | oai:union.ndltd.org:uottawa.ca/oai:ruor.uottawa.ca:10393/30069 |
| Date | January 2010 |
| Creators | Warren, Robert B |
| Publisher | University of Ottawa (Canada) |
| Source Sets | Université d’Ottawa |
| Language | English |
| Detected Language | English |
| Type | Thesis |
| Format | 163 p. |
Page generated in 0.0021 seconds