On the similarity of sets of permutations and its applications to genome comparison

Bergeron A, Stoye J (2006)
JOURNAL OF COMPUTATIONAL BIOLOGY 13(7): 1340-1354.

Journal Article | Published | English

No fulltext has been uploaded

Author
;
Abstract
The comparison of genomes with the same gene content relies on our ability to compare permutations, either by measuring how much they differ, or by measuring how much they are alike. With the notable exception of the breakpoint distance, which is based on the concept of conserved adjacencies, measures of distance do not generalize easily to sets of more than two permutations. In this paper, we present a basic unifying notion, conserved intervals, as a powerful generalization of adjacencies, and as a key feature of genome rearrangement theories. We also show that sets of conserved intervals have elegant nesting and chaining properties that allow the development of compact graphic representations, and linear time algorithms to manipulate them.
Publishing Year
ISSN
eISSN
PUB-ID

Cite this

Bergeron A, Stoye J. On the similarity of sets of permutations and its applications to genome comparison. JOURNAL OF COMPUTATIONAL BIOLOGY. 2006;13(7):1340-1354.
Bergeron, A., & Stoye, J. (2006). On the similarity of sets of permutations and its applications to genome comparison. JOURNAL OF COMPUTATIONAL BIOLOGY, 13(7), 1340-1354.
Bergeron, A., and Stoye, J. (2006). On the similarity of sets of permutations and its applications to genome comparison. JOURNAL OF COMPUTATIONAL BIOLOGY 13, 1340-1354.
Bergeron, A., & Stoye, J., 2006. On the similarity of sets of permutations and its applications to genome comparison. JOURNAL OF COMPUTATIONAL BIOLOGY, 13(7), p 1340-1354.
A. Bergeron and J. Stoye, “On the similarity of sets of permutations and its applications to genome comparison”, JOURNAL OF COMPUTATIONAL BIOLOGY, vol. 13, 2006, pp. 1340-1354.
Bergeron, A., Stoye, J.: On the similarity of sets of permutations and its applications to genome comparison. JOURNAL OF COMPUTATIONAL BIOLOGY. 13, 1340-1354 (2006).
Bergeron, Anne, and Stoye, Jens. “On the similarity of sets of permutations and its applications to genome comparison”. JOURNAL OF COMPUTATIONAL BIOLOGY 13.7 (2006): 1340-1354.
This data publication is cited in the following publications:
This publication cites the following data publications:

9 Citations in Europe PMC

Data provided by Europe PubMed Central.

Constructing a Gene Team Tree in Almost O (n lg n) Time.
Wang BF, Lin CH, Yang IT., IEEE/ACM Trans Comput Biol Bioinform 11(1), 2014
PMID: 26355514
Easy identification of generalized common and conserved nested intervals.
de Montgolfier F, Raffinot M, Rusu I., J. Comput. Biol. 21(7), 2014
PMID: 24650221
Ancestral genome organization: an alignment approach.
Holloway P, Swenson K, Ardell D, El-Mabrouk N., J. Comput. Biol. 20(4), 2013
PMID: 23560866
A new efficient algorithm for the gene-team problem on general sequences.
Wang BF, Kuo CC, Liu SJ, Lin CH., IEEE/ACM Trans Comput Biol Bioinform 9(2), 2012
PMID: 22282907
Cactus graphs for genome comparisons.
Paten B, Diekhans M, Earl D, John JS, Ma J, Suh B, Haussler D., J. Comput. Biol. 18(3), 2011
PMID: 21385048
Finding nested common intervals efficiently.
Blin G, Faye D, Stoye J., J. Comput. Biol. 17(9), 2010
PMID: 20874403
A unified approach for reconstructing ancient gene clusters.
Stoye J, Wittler R., IEEE/ACM Trans Comput Biol Bioinform 6(3), 2009
PMID: 19644167
Solving the preserving reversal median problem.
Bernt M, Merkle D, Middendorf M., IEEE/ACM Trans Comput Biol Bioinform 5(3), 2008
PMID: 18670038

20 References

Data provided by Europe PubMed Central.


bergeron, lnbi 3240(), 2004

bergeron, bioinformatics 18(), 2002
Genome-scale evolution: reconstructing gene orders in the ancestral species.
Bourque G, Pevzner PA., Genome Res. 12(1), 2002
PMID: 11779828

hannenhalli, proc focs (), 1995

kececioglu, lect notes comput sci 807(), 1994
Fast Algorithms to Enumerate All Common Intervals of Two Permutations
Uno, Algorithmica 26(2), 2000
Polynomial-time algorithm for computing translocation distance between genomes
Hannenhalli, Discrete Applied Mathematics 71(1-3), 1996
Transforming cabbage into turnip: polynomial algorithm for sorting signed permutations by reversals
Hannenhalli, Journal of the ACM 46(1), 1999
Short inversions and conserved gene cluster.
Sankoff D., Bioinformatics 18(10), 2002
PMID: 12376374
Efficient algorithms for multichromosomal genome rearrangements
Tesler, Journal of Computer and System Sciences 65(3), 2002
Two notes on genome rearrangement.
Ozery-Flato M, Shamir R., J Bioinform Comput Biol 1(1), 2003
PMID: 15290782
A Faster and Simpler Algorithm for Sorting Signed Permutations by Reversals
Kaplan, SIAM Journal on Computing 29(3), 2000
Sorting by Transpositions
Bafna, SIAM Journal on Discrete Mathematics 11(2), 1998
Gene order breakpoint evidence in animal mitochondrial phylogeny.
Blanchette M, Kunisawa T, Sankoff D., J. Mol. Evol. 49(2), 1999
PMID: 10441671
On the Similarity of Sets of Permutations and Its Applications to Genome Comparison
Bergeron, 2003
Finding All Common Intervals of k Permutations
Heber, 2006
Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
Booth, Journal of Computer and System Sciences 13(3), 1976
Exploring the Set of All Minimal Sequences of Reversals — An Application to Test the Replication-Directed Reversal Hypothesis
Ajana, 2002
Inversion Medians Outperform Breakpoint Medians in Phylogeny Reconstruction from Gene-Order Data
Moret, 2002

Export

0 Marked Publications

Open Data PUB

Web of Science

View record in Web of Science®

Sources

PMID: 17037962
PubMed | Europe PMC

Search this title in

Google Scholar