Loading...
Please wait, while we are loading the content...
Similar Documents
Transforming Cabbage into Turnip (polynomial algorithm for sorting signed permutations by reversals) (1995)
| Content Provider | CiteSeerX |
|---|---|
| Author | Hannenhalli, Sridhar Pevzner, Pavel |
| Description | Analysis of genome rearrangements in molecular biology started in the late 1930's, when Dobzhansky and Sturtevant published a milestone paper presenting a rearrangement scenario with 17 inversions for the species of Drosophila. Analysis of genomes evolving by inversions leads to a combinatorial problem of sorting by reversals studied in detail recently. Kececioglu and Sankoff conjectured that sorting by reversals is NP-hard, but despite many attempts their conjecture remains open. We study sorting of signed permutations by reversals, a problem which adequately models rearrangements in small genomes like chloroplast or mitochondrial DNA. The previously suggested performance guarantee algorithms for sorting signed permutations by reversals approximate the reversal distance between permutations with an astonishing accuracy for both simulated and biological data. We prove a duality theorem explaining this intriguing performance and show that there exists a "hidden" parameter which allow... |
| File Format | |
| Journal | JOURNAL OF THE ACM |
| Language | English |
| Publisher | ACM Press |
| Publisher Date | 1995-01-01 |
| Access Restriction | Open |
| Subject Keyword | Polynomial Algorithm Hidden Parameter Molecular Biology Astonishing Accuracy Mitochondrial Dna Small Genome Inversion Lead Many Attempt Genome Rearrangement Intriguing Performance Milestone Paper Duality Theorem Biological Data Rearrangement Scenario Model Rearrangement Reversal Distance Combinatorial Problem Performance Guarantee Algorithm |
| Content Type | Text |
| Resource Type | Article |
