Name
Abstract | ||
|---|---|---|
An important problem for phylogenetic investigations that are based on gene orders is to find for three given gene orders a fourth gene order that has a minimum sum of reversal distances to the three given gene orders. This problem is called Reversal Median problem (RMP). The RMP is studied here under the constraint that common (combinatorial) structures are preserved which are modeled as common intervals. An existing branch-and-bound algorithm for RMP is extended here so that it can solve the RMP with common intervals optimally. This algorithm is applied to mitochondrial gene order data for different animal taxa. It is shown that common intervals occur often for most taxa and that many common intervals are destroyed when the RMP is solved optimally with standard methods that do not consider common intervals. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1007/11875741_6 | CompLife |
Keywords | Field | DocType |
existing branch-and-bound algorithm,reversal median problem,mitochondrial gene order,minimum sum,important problem,gene order data,phylogenetic investigation,common interval,common intervals optimally,different animal taxon,gene order,branch and bound algorithm | Combinatorics,Gene,Phylogenetic tree,Gene orders,Mitochondrial DNA,Mathematics | Conference |
Volume | ISSN | ISBN |
4216 | 0302-9743 | 3-540-45767-4 |
Citations | PageRank | References |
2 | 0.39 | 11 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Matthias Bernt | 1 | 77 | 11.06 |
| Daniel Merkle | 2 | 364 | 43.93 |
| Martin Middendorf | 3 | 1334 | 161.45 |