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
Zeitschriftenaufsatz | Veröffentlicht | Englisch
Volltext vorhanden für diesen Nachweis
Autor
; ;
Abstract / Bemerkung
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.
Erscheinungsjahr
Zeitschriftentitel
Bioinformatics
Band
18
Zeitschriftennummer
Suppl 2
Seite
S54-S63
ISSN
eISSN
PUB-ID

Zitieren

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. doi:10.1093/bioinformatics/18.suppl_2.S54
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.
Alle Dateien verfügbar unter der/den folgenden Lizenz(en):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Volltext(e)
Access Level
OA Open Access
Zuletzt Hochgeladen
1970-01-01T00:00:00Z

9 Zitationen in Europe PMC

Daten bereitgestellt von Europe PubMed Central.

A New Efficient Algorithm for the All Sorting Reversals Problem with No Bad Components.
Wang BF., IEEE/ACM Trans Comput Biol Bioinform 13(4), 2016
PMID: 26353380
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
A (1.5 + epsilon)-approximation algorithm for unsigned translocation distance.
Cui Y, Wang L, Zhu D, Liu X., IEEE/ACM Trans Comput Biol Bioinform 5(1), 2008
PMID: 18245875
Exploring the solution space of sorting by reversals, with experiments and an application to evolution.
Braga MD, Sagot MF, Scornavacca C, Tannier E., IEEE/ACM Trans Comput Biol Bioinform 5(3), 2008
PMID: 18670039
Alignments of mitochondrial genome arrangements: applications to metazoan phylogeny.
Fritzsch G, Schlegel M, Stadler PF., J Theor Biol 240(4), 2006
PMID: 16325206
Genome rearrangement based on reversals that preserve conserved intervals.
Bernt M, Merkle D, Middendorf M., IEEE/ACM Trans Comput Biol Bioinform 3(3), 2006
PMID: 17048465
PROFcon: novel prediction of long-range contacts.
Punta M, Rost B., Bioinformatics 21(13), 2005
PMID: 15890748

Export

Markieren/ Markierung löschen
Markierte Publikationen

Open Data PUB

Web of Science

Dieser Datensatz im Web of Science®

Quellen

PMID: 12385983
PubMed | Europe PMC

Suchen in

Google Scholar