# 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

Department

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.

Keywords

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.,

PMID: 26355514

Wang BF, Lin CH, Yang IT.,

*IEEE/ACM Trans Comput Biol Bioinform*11(1), 2014PMID: 26355514

Easy identification of generalized common and conserved nested intervals.

de Montgolfier F, Raffinot M, Rusu I.,

PMID: 24650221

de Montgolfier F, Raffinot M, Rusu I.,

*J. Comput. Biol.*21(7), 2014PMID: 24650221

Ancestral genome organization: an alignment approach.

Holloway P, Swenson K, Ardell D, El-Mabrouk N.,

PMID: 23560866

Holloway P, Swenson K, Ardell D, El-Mabrouk N.,

*J. Comput. Biol.*20(4), 2013PMID: 23560866

A new efficient algorithm for the gene-team problem on general sequences.

Wang BF, Kuo CC, Liu SJ, Lin CH.,

PMID: 22282907

Wang BF, Kuo CC, Liu SJ, Lin CH.,

*IEEE/ACM Trans Comput Biol Bioinform*9(2), 2012PMID: 22282907

Output-sensitive algorithms for finding the nested common intervals of two general sequences.

Wang BF.,

PMID: 21844635

Wang BF.,

*IEEE/ACM Trans Comput Biol Bioinform*9(2), 2012PMID: 21844635

Cactus graphs for genome comparisons.

Paten B, Diekhans M, Earl D, John JS, Ma J, Suh B, Haussler D.,

PMID: 21385048

Paten B, Diekhans M, Earl D, John JS, Ma J, Suh B, Haussler D.,

*J. Comput. Biol.*18(3), 2011PMID: 21385048

Finding nested common intervals efficiently.

Blin G, Faye D, Stoye J.,

PMID: 20874403

Blin G, Faye D, Stoye J.,

*J. Comput. Biol.*17(9), 2010PMID: 20874403

A unified approach for reconstructing ancient gene clusters.

Stoye J, Wittler R.,

PMID: 19644167

Stoye J, Wittler R.,

*IEEE/ACM Trans Comput Biol Bioinform*6(3), 2009PMID: 19644167

Solving the preserving reversal median problem.

Bernt M, Merkle D, Middendorf M.,

PMID: 18670038

Bernt M, Merkle D, Middendorf M.,

*IEEE/ACM Trans Comput Biol Bioinform*5(3), 2008PMID: 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.,

PMID: 11779828

Bourque G, Pevzner PA.,

*Genome Res.*12(1), 2002PMID: 11779828

hannenhalli,

*proc focs*(), 1995

kececioglu,

*lect notes comput sci*807(), 1994

Fast Algorithms to Enumerate All Common Intervals of Two Permutations

Uno,

Uno,

*Algorithmica*26(2), 2000
Polynomial-time algorithm for computing translocation distance between genomes

Hannenhalli,

Hannenhalli,

*Discrete Applied Mathematics*71(1-3), 1996
A linear-time algorithm for computing inversion distance between signed permutations with an experimental study.

Bader DA, Moret BM, Yan M.,

PMID: 11694179

Bader DA, Moret BM, Yan M.,

*J. Comput. Biol.*8(5), 2001PMID: 11694179

Transforming cabbage into turnip: polynomial algorithm for sorting signed permutations by reversals

Hannenhalli,

Hannenhalli,

*Journal of the ACM*46(1), 1999
Efficient algorithms for multichromosomal genome rearrangements

Tesler,

Tesler,

*Journal of Computer and System Sciences*65(3), 2002
Two notes on genome rearrangement.

Ozery-Flato M, Shamir R.,

PMID: 15290782

Ozery-Flato M, Shamir R.,

*J Bioinform Comput Biol*1(1), 2003PMID: 15290782

A Faster and Simpler Algorithm for Sorting Signed Permutations by Reversals

Kaplan,

Kaplan,

*SIAM Journal on Computing*29(3), 2000
Sorting by Transpositions

Bafna,

Bafna,

*SIAM Journal on Discrete Mathematics*11(2), 1998
Gene order breakpoint evidence in animal mitochondrial phylogeny.

Blanchette M, Kunisawa T, Sankoff D.,

PMID: 10441671

Blanchette M, Kunisawa T, Sankoff D.,

*J. Mol. Evol.*49(2), 1999PMID: 10441671

On the Similarity of Sets of Permutations and Its Applications to Genome Comparison

Bergeron, 2003

Bergeron, 2003

Finding All Common Intervals of k Permutations

Heber, 2006

Heber, 2006

Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms

Booth,

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

Ajana, 2002

Inversion Medians Outperform Breakpoint Medians in Phylogeny Reconstruction from Gene-Order Data

Moret, 2002

Moret, 2002

### Export

0 Marked Publications### Web of Science

View record in Web of Science®### Sources

PMID: 17037962

PubMed | Europe PMC