Loading...
Please wait, while we are loading the content...
Similar Documents
Sorting by reversals in subquadratic time
| Content Provider | Hyper Articles en Ligne (HAL) |
|---|---|
| Author | Tannier, Eric Sagot, Marie-France |
| Copyright Year | 2004 |
| Abstract | The problem of sorting by signed reversals is inspired by a genome rearrangement problem in computational molecular biology. Given two genomes represented as signed permutations of the same elements (e.g. orthologous genes), the problem consists in finding a most parsimonious scenario of reversals that transforms one genome into the other. We propose a method for sorting a signed permutation by reversals in time O(n). The best known algorithms run in time O(n^2), the main obstacle to an improvement being a costly operation of detection of so-called «safe» reversals. We bypass this detection and, using the same data structure as a previous random approximation algorithm, we achieve the same subquadratic complexity for finding an exact optimal solution. This answers an open question by Ozery-Flato and Shamir whether a subquadratic complexity could ever be achieved for solving the problem. |
| Related Links | https://inria.hal.science/inria-00071486/file/RR-5097.pdf |
| Language | English |
| Publisher | HAL CCSD |
| Publisher Date | 2004-01-01 |
| Access Restriction | Open |
| Subject Keyword | SORTING PERMUTATIONS GENOME REARRANGEMENT POLYNOMIAL TIME ALGORITHM INVERSIONS COMPUTATIONAL BIOLOGY REVERSALS |
| Content Type | Text |
| Resource Type | Report |
| Subject | Computer Science |
