TY  - JOUR
AB  - This paper revisits the problem of sorting by reversals with tools developed in the context of detecting common intervals. Mixing the two approaches yields new definitions and algorithms for the reversal distance computations, that apply directly on the original permutation. Traditional constructions such as recasting the signed permutation as a positive permutation, or traversing the overlap graph to analyze its connected components, are replaced by elementary definitions in terms of intervals of the permutation. This yields simple linear time algorithms that identify the essential features in a single pass over the permutation and use only simple data structures like arrays and stacks.
DA  - 2002
DO  - 10.1093/bioinformatics/18.suppl_2.S54
LA  - eng
IS  - Suppl 2
M2  - S54
PY  - 2002
SN  - 1367-4803
SP  - S54-S63
T2  - Bioinformatics
TI  - Common intervals and sorting by reversals: a marriage of necessity
UR  - https://nbn-resolving.org/urn:nbn:de:0070-bipr-538
Y2  - 2024-11-22T03:45:11
ER  -