Loading...
Please wait, while we are loading the content...
Similar Documents
Whole Genome Duplications, Multi-Break Rearrangements, and Genome Halving Theorem (2007)
| Content Provider | CiteSeerX |
|---|---|
| Author | Alekseyev, Max A. Pevzner, Pavel A. |
| Description | The Genome Halving Problem, motivated by the whole genome duplication events in molecular evolution, was solved by El-Mabrouk and Sankoff. The El-Mabrouk– Sankoff algorithm is rather complex inspiring a quest for a simpler solution. An alternative approach to Genome Halving Problem based on the notion of the contracted breakpoint graph was recently proposed in [2]. This new technique reveals that while the El-Mabrouk–Sankoff result is correct in most cases, it does not hold in the case of unichromosomal genomes. This raises a problem of correcting El-Mabrouk–Sankoff analysis and devising an algorithm that deals adequately with all genomes. In this paper we efficiently classify all genomes into two classes and show that while the El-Mabrouk–Sankoff theorem holds for the first class, it is incorrect for the second class. The crux of our analysis is a new combinatorial invariant defined on duplicated permutations. Using this invariant we were able to come up with a full proof of the Genome Halving theorem and a polynomial algorithm for Genome Halving Problem (for unichromosomal genomes). We also give the first short proof of the original El-Mabrouk–Sankoff result for multichromosomal genomes. Finally, we discuss a generalization of Genome Halving Problem for a more general set of rearrangement operations (including transpositions) and propose an efficient algorithm for solving this problem. 1 |
| File Format | |
| Language | English |
| Publisher Date | 2007-01-01 |
| Publisher Institution | Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA |
| Access Restriction | Open |
| Subject Keyword | Full Proof Multi-break Rearrangement Polynomial Algorithm Molecular Evolution El-mabrouk Sankoff Algorithm Whole Genome Duplication First Class El-mabrouk Sankoff Analysis Whole Genome Duplication Event Original El-mabrouk Sankoff Result Second Class Simpler Solution El-mabrouk Sankoff Theorem General Set Genome Halving Problem Unichromosomal Genome Contracted Breakpoint Graph Rearrangement Operation Genome Halving Theorem Duplicated Permutation Efficient Algorithm New Technique Reveals El-mabrouk Sankoff Result New Combinatorial Invariant Alternative Approach First Short Proof Multichromosomal Genome |
| Content Type | Text |
| Resource Type | Article |
