Common intervals and sorting by reversals: a marriage of necessity

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

Zeitschriftenaufsatz | Veröffentlicht | Englisch
 
Download
OA
Autor*in
Bergeron, Anne; Heber, Steffen; Stoye, JensUniBi
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
2002
Zeitschriftentitel
Bioinformatics
Band
18
Ausgabe
Suppl 2
Seite(n)
S54-S63
ISSN
1367-4803
eISSN
1460-2059
Page URI
https://pub.uni-bielefeld.de/record/1773329

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. https://doi.org/10.1093/bioinformatics/18.suppl_2.S54
Bergeron, Anne, Heber, Steffen, and Stoye, Jens. 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.
Alle Dateien verfügbar unter der/den folgenden Lizenz(en):
Copyright Statement:
Dieses Objekt ist durch das Urheberrecht und/oder verwandte Schutzrechte geschützt. [...]
Volltext(e)
Access Level
OA Open Access
Zuletzt Hochgeladen
2019-09-06T08:48:07Z
MD5 Prüfsumme
044799cfb72389c6b1f342f4c4f5fb3b


12 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
On the repeat-annotated phylogenetic tree reconstruction problem.
Swidan F, Ziv-Ukelson M, Pinter RY., J Comput Biol 13(8), 2006
PMID: 17061918
PROFcon: novel prediction of long-range contacts.
Punta M, Rost B., Bioinformatics 21(13), 2005
PMID: 15890748

References

Daten bereitgestellt von Europe PubMed Central.

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