Fast sorting by reversal

Piotr Berman; Sridhar Hannenhalli

doi:10.1007/3-540-61258-0_14

Fast sorting by reversal

Piotr Berman
, Sridhar Hannenhalli

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

96 Scopus citations

Abstract

Analysis of genomes evolving by inversions leads to a combinatorial problem of sorting by reversals studied in detail recently. Following a series of work recently, Hannenhalli and Pevzner developed the first polynomial algorithm for the problem of sorting signed permutations by reversals and proposed an O(n⁴) implementation of the algorithm. In this paper we exploit a few combinatorial properties of the cycle graph of a permutation and propose an O(n²α(n)) implementation of the algorithm where a is the inverse Ackerman function. Besides making this algorithm practical, our technique improves implementations of the other rearrangement distance problems.

Original language	English (US)
Title of host publication	Combinatorial Pattern Matching - 7th Annual Symposium, CPM 1996, Proceedings
Editors	Gene Myers, Dan Hirschberg
Publisher	Springer Verlag
Pages	168-185
Number of pages	18
ISBN (Print)	3540612580, 9783540612582
DOIs	https://doi.org/10.1007/3-540-61258-0_14
State	Published - 1996
Event	7th Annual Symposium on Combinatorial Pattern Matching, CPM 1996 - Laguna Beach, United States Duration: Jun 10 1996 → Jun 12 1996

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	1075
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	7th Annual Symposium on Combinatorial Pattern Matching, CPM 1996
Country/Territory	United States
City	Laguna Beach
Period	6/10/96 → 6/12/96

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/3-540-61258-0_14

Cite this

Berman, P., & Hannenhalli, S. (1996). Fast sorting by reversal. In G. Myers, & D. Hirschberg (Eds.), Combinatorial Pattern Matching - 7th Annual Symposium, CPM 1996, Proceedings (pp. 168-185). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1075). Springer Verlag. https://doi.org/10.1007/3-540-61258-0_14

@inproceedings{dcba0d2f351b49709768612a3288de03,

title = "Fast sorting by reversal",

abstract = "Analysis of genomes evolving by inversions leads to a combinatorial problem of sorting by reversals studied in detail recently. Following a series of work recently, Hannenhalli and Pevzner developed the first polynomial algorithm for the problem of sorting signed permutations by reversals and proposed an O(n4) implementation of the algorithm. In this paper we exploit a few combinatorial properties of the cycle graph of a permutation and propose an O(n2α(n)) implementation of the algorithm where a is the inverse Ackerman function. Besides making this algorithm practical, our technique improves implementations of the other rearrangement distance problems.",

author = "Piotr Berman and Sridhar Hannenhalli",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1996.; 7th Annual Symposium on Combinatorial Pattern Matching, CPM 1996 ; Conference date: 10-06-1996 Through 12-06-1996",

year = "1996",

doi = "10.1007/3-540-61258-0\_14",

language = "English (US)",

isbn = "3540612580",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "168--185",

editor = "Gene Myers and Dan Hirschberg",

booktitle = "Combinatorial Pattern Matching - 7th Annual Symposium, CPM 1996, Proceedings",

address = "Germany",

}

Berman, P & Hannenhalli, S 1996, Fast sorting by reversal. in G Myers & D Hirschberg (eds), Combinatorial Pattern Matching - 7th Annual Symposium, CPM 1996, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1075, Springer Verlag, pp. 168-185, 7th Annual Symposium on Combinatorial Pattern Matching, CPM 1996, Laguna Beach, United States, 6/10/96. https://doi.org/10.1007/3-540-61258-0_14

Fast sorting by reversal. / Berman, Piotr; Hannenhalli, Sridhar.
Combinatorial Pattern Matching - 7th Annual Symposium, CPM 1996, Proceedings. ed. / Gene Myers; Dan Hirschberg. Springer Verlag, 1996. p. 168-185 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1075).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Fast sorting by reversal

AU - Berman, Piotr

AU - Hannenhalli, Sridhar

N1 - Publisher Copyright: © Springer-Verlag Berlin Heidelberg 1996.

PY - 1996

Y1 - 1996

N2 - Analysis of genomes evolving by inversions leads to a combinatorial problem of sorting by reversals studied in detail recently. Following a series of work recently, Hannenhalli and Pevzner developed the first polynomial algorithm for the problem of sorting signed permutations by reversals and proposed an O(n4) implementation of the algorithm. In this paper we exploit a few combinatorial properties of the cycle graph of a permutation and propose an O(n2α(n)) implementation of the algorithm where a is the inverse Ackerman function. Besides making this algorithm practical, our technique improves implementations of the other rearrangement distance problems.

AB - Analysis of genomes evolving by inversions leads to a combinatorial problem of sorting by reversals studied in detail recently. Following a series of work recently, Hannenhalli and Pevzner developed the first polynomial algorithm for the problem of sorting signed permutations by reversals and proposed an O(n4) implementation of the algorithm. In this paper we exploit a few combinatorial properties of the cycle graph of a permutation and propose an O(n2α(n)) implementation of the algorithm where a is the inverse Ackerman function. Besides making this algorithm practical, our technique improves implementations of the other rearrangement distance problems.

UR - https://www.scopus.com/pages/publications/84957634698

UR - https://www.scopus.com/pages/publications/84957634698#tab=citedBy

U2 - 10.1007/3-540-61258-0_14

DO - 10.1007/3-540-61258-0_14

M3 - Conference contribution

AN - SCOPUS:84957634698

SN - 3540612580

SN - 9783540612582

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 168

EP - 185

BT - Combinatorial Pattern Matching - 7th Annual Symposium, CPM 1996, Proceedings

A2 - Myers, Gene

A2 - Hirschberg, Dan

PB - Springer Verlag

T2 - 7th Annual Symposium on Combinatorial Pattern Matching, CPM 1996

Y2 - 10 June 1996 through 12 June 1996

ER -

Fast sorting by reversal

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this