A faster and simpler algorithm for sorting signed permutations by reversals

Haim Kaplan; Ron Shamir; Robert E. Tarjan

doi:10.1137/S0097539798334207

A faster and simpler algorithm for sorting signed permutations by reversals

Haim Kaplan, Ron Shamir, Robert E. Tarjan

Research output: Contribution to journal › Article › peer-review

133 Scopus citations

Abstract

We give a quadratic time algorithm for finding the minimum number of reversals needed to sort a signed permutation. Our algorithm is faster than the previous algorithm of Hannenhalli and Pevzner and its faster implementation by Berman and Hannenhalli. The algorithm is conceptually simple and does not require special data structures. Our study also considerably simplifies the combinatorial structures used by the analysis.

Original language	English (US)
Pages (from-to)	880-892
Number of pages	13
Journal	SIAM Journal on Computing
Volume	29
Issue number	3
DOIs	https://doi.org/10.1137/S0097539798334207
State	Published - 2000

All Science Journal Classification (ASJC) codes

General Computer Science
General Mathematics

Keywords

Computational molecular biology
Reversal distance
Sorting permutations

Access to Document

10.1137/S0097539798334207

Cite this

@article{cd6eb6bc6cb14ea2b69f77be4dc44b08,

title = "A faster and simpler algorithm for sorting signed permutations by reversals",

abstract = "We give a quadratic time algorithm for finding the minimum number of reversals needed to sort a signed permutation. Our algorithm is faster than the previous algorithm of Hannenhalli and Pevzner and its faster implementation by Berman and Hannenhalli. The algorithm is conceptually simple and does not require special data structures. Our study also considerably simplifies the combinatorial structures used by the analysis.",

keywords = "Computational molecular biology, Reversal distance, Sorting permutations",

author = "Haim Kaplan and Ron Shamir and Tarjan, {Robert E.}",

year = "2000",

doi = "10.1137/S0097539798334207",

language = "English (US)",

volume = "29",

pages = "880--892",

journal = "SIAM Journal on Computing",

issn = "0097-5397",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "3",

}

TY - JOUR

T1 - A faster and simpler algorithm for sorting signed permutations by reversals

AU - Kaplan, Haim

AU - Shamir, Ron

AU - Tarjan, Robert E.

PY - 2000

Y1 - 2000

N2 - We give a quadratic time algorithm for finding the minimum number of reversals needed to sort a signed permutation. Our algorithm is faster than the previous algorithm of Hannenhalli and Pevzner and its faster implementation by Berman and Hannenhalli. The algorithm is conceptually simple and does not require special data structures. Our study also considerably simplifies the combinatorial structures used by the analysis.

AB - We give a quadratic time algorithm for finding the minimum number of reversals needed to sort a signed permutation. Our algorithm is faster than the previous algorithm of Hannenhalli and Pevzner and its faster implementation by Berman and Hannenhalli. The algorithm is conceptually simple and does not require special data structures. Our study also considerably simplifies the combinatorial structures used by the analysis.

KW - Computational molecular biology

KW - Reversal distance

KW - Sorting permutations

UR - http://www.scopus.com/inward/record.url?scp=0033295439&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0033295439&partnerID=8YFLogxK

U2 - 10.1137/S0097539798334207

DO - 10.1137/S0097539798334207

M3 - Article

AN - SCOPUS:0033295439

SN - 0097-5397

VL - 29

SP - 880

EP - 892

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

IS - 3

ER -

A faster and simpler algorithm for sorting signed permutations by reversals

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this