Common intervals and sorting by reversals: a marriage of necessity

Bergeron A, Heber S, Stoye J (2002)
Bioinformatics 18(Suppl 2): S54-S63.

Download
OA
Journal Article | Published | English
Author
; ;
Abstract
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.
Publishing Year
ISSN
eISSN
PUB-ID

Cite this

Bergeron A, Heber S, Stoye J. Common intervals and sorting by reversals: a marriage of necessity. Bioinformatics. 2002;18(Suppl 2):S54-S63.
Bergeron, A., Heber, S., & Stoye, J. (2002). Common intervals and sorting by reversals: a marriage of necessity. Bioinformatics, 18(Suppl 2), S54-S63.
Bergeron, A., Heber, S., and Stoye, J. (2002). Common intervals and sorting by reversals: a marriage of necessity. Bioinformatics 18, S54-S63.
Bergeron, A., Heber, S., & Stoye, J., 2002. Common intervals and sorting by reversals: a marriage of necessity. Bioinformatics, 18(Suppl 2), p S54-S63.
A. Bergeron, S. Heber, and J. Stoye, “Common intervals and sorting by reversals: a marriage of necessity”, Bioinformatics, vol. 18, 2002, pp. S54-S63.
Bergeron, A., Heber, S., Stoye, J.: Common intervals and sorting by reversals: a marriage of necessity. Bioinformatics. 18, S54-S63 (2002).
Bergeron, Anne, Heber, Steffen, and Stoye, Jens. “Common intervals and sorting by reversals: a marriage of necessity”. Bioinformatics 18.Suppl 2 (2002): S54-S63.
Main File(s)
File Name
Access Level
OA Open Access

This data publication is cited in the following publications:
This publication cites the following data publications:

5 Citations in Europe PMC

Data provided by Europe PubMed Central.

Evaluating synteny for improved comparative studies.
Ghiurcuta CG, Moret BM., Bioinformatics 30(12), 2014
PMID: 24932010
An asymmetric approach to preserve common intervals while sorting by reversals.
Braga MD, Gautier C, Sagot MF., Algorithms Mol Biol 4(), 2009
PMID: 20042101
Alignments of mitochondrial genome arrangements: applications to metazoan phylogeny.
Fritzsch G, Schlegel M, Stadler PF., J. Theor. Biol. 240(4), 2006
PMID: 16325206
PROFcon: novel prediction of long-range contacts.
Punta M, Rost B., Bioinformatics 21(13), 2005
PMID: 15890748

Export

0 Marked Publications

Open Data PUB

Web of Science

View record in Web of Science®

Sources

PMID: 12385983
PubMed | Europe PMC

Search this title in

Google Scholar