Large scale comparative genetic mapping offers exciting prospects for understanding genomic evolution and has recently become of interest in computational molecular biology. The genome rearrangement problem is the computational problem of determining the smallest number of evolutionary events required to transform a given genome into another. In this thesis, we study a specific variant of the genome rearrangement problem. We assume that every genome has exactly one linear chromosome, and that each gene is an oriented unit and appears exactly once per genome. Furthermore, our model allows only two kinds of evolutionary events: reversals and transpositions. The problem is equivalent to the problem of sorting signed permutations by transpositions and reversals. We explore the characteristics of signed permutations and their sorting path. This exploration results in lower and upper bounds for a shortest sorting path. These bounds help us develop three approximation algorithms. We also prove that sorting by transpositions and reversals is at least as hard as the problem sorting by transpositions only - the complexity of which is unknown. In an effort to implement an algorithm to find an optimal sorting path of events, we designed four techniques to reduce the input size of the problem and thus achieve an improvement of the actual running time for any exhaustive algorithm.
| Identifer | oai:union.ndltd.org:uvic.ca/oai:dspace.library.uvic.ca:1828/524 |
| Date | 10 April 2008 |
| Creators | Zhang, Fei. |
| Contributors | Stege, Ulrike.|Müller, Hausi A. |
| Source Sets | University of Victoria |
| Detected Language | English |
Page generated in 0.0026 seconds