Efficient bounds for oriented chromosome inversion distance

John Kececioglu; David Sankoff

doi:10.1007/3-540-58094-8_26

Efficient bounds for oriented chromosome inversion distance

John Kececioglu, David Sankoff

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

71 Scopus citations

Abstract

We study the problem of comparing two circular chromosomes that have evolved by chromosome inversion, assuming that the order of corresponding genes is known, as well as their orientation. Determining the minimum number of inversions is equivalent to finding the minimum of reversals to sort a signed circular permutation, where a reversal takes an arbitrary substring of elements and reverses their order, as well as flipping their sign. We show that tight bounds on the minimum number of reversals can be found by simple and efficient algorithms.

Original language	English (US)
Title of host publication	Combinatorial Pattern Matching - 5th Annual Symposium, CPM 1994, Proceedings
Editors	Maxime Crochemore, Dan Gusfield
Publisher	Springer-Verlag
Pages	307-325
Number of pages	19
ISBN (Print)	9783540580942
DOIs	https://doi.org/10.1007/3-540-58094-8_26
State	Published - 1994
Event	5th Annual Symposium on Combinatorial Pattern Matching, CPM 1994 - Asilomar, United States Duration: Jun 5 1994 → Jun 8 1994

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	807 LNCS

Other

Other	5th Annual Symposium on Combinatorial Pattern Matching, CPM 1994
Country/Territory	United States
City	Asilomar
Period	6/5/94 → 6/8/94

Keywords

Chromosome inversion
Genome rearrangements
Reversal distance
Sorting by signed reversals

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/3-540-58094-8_26

Cite this

Kececioglu, J., & Sankoff, D. (1994). Efficient bounds for oriented chromosome inversion distance. In M. Crochemore, & D. Gusfield (Eds.), Combinatorial Pattern Matching - 5th Annual Symposium, CPM 1994, Proceedings (pp. 307-325). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 807 LNCS). Springer-Verlag. https://doi.org/10.1007/3-540-58094-8_26

Efficient bounds for oriented chromosome inversion distance. / Kececioglu, John; Sankoff, David.
Combinatorial Pattern Matching - 5th Annual Symposium, CPM 1994, Proceedings. ed. / Maxime Crochemore; Dan Gusfield. Springer-Verlag, 1994. p. 307-325 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 807 LNCS).

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

Kececioglu, J & Sankoff, D 1994, Efficient bounds for oriented chromosome inversion distance. in M Crochemore & D Gusfield (eds), Combinatorial Pattern Matching - 5th Annual Symposium, CPM 1994, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 807 LNCS, Springer-Verlag, pp. 307-325, 5th Annual Symposium on Combinatorial Pattern Matching, CPM 1994, Asilomar, United States, 6/5/94. https://doi.org/10.1007/3-540-58094-8_26

Kececioglu J, Sankoff D. Efficient bounds for oriented chromosome inversion distance. In Crochemore M, Gusfield D, editors, Combinatorial Pattern Matching - 5th Annual Symposium, CPM 1994, Proceedings. Springer-Verlag. 1994. p. 307-325. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-58094-8_26

Kececioglu, John ; Sankoff, David. / Efficient bounds for oriented chromosome inversion distance. Combinatorial Pattern Matching - 5th Annual Symposium, CPM 1994, Proceedings. editor / Maxime Crochemore ; Dan Gusfield. Springer-Verlag, 1994. pp. 307-325 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{b90b4f96854c4c1eab72b51be9e2cc1e,

title = "Efficient bounds for oriented chromosome inversion distance",

abstract = "We study the problem of comparing two circular chromosomes that have evolved by chromosome inversion, assuming that the order of corresponding genes is known, as well as their orientation. Determining the minimum number of inversions is equivalent to finding the minimum of reversals to sort a signed circular permutation, where a reversal takes an arbitrary substring of elements and reverses their order, as well as flipping their sign. We show that tight bounds on the minimum number of reversals can be found by simple and efficient algorithms.",

keywords = "Chromosome inversion, Genome rearrangements, Reversal distance, Sorting by signed reversals",

author = "John Kececioglu and David Sankoff",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1994.; 5th Annual Symposium on Combinatorial Pattern Matching, CPM 1994 ; Conference date: 05-06-1994 Through 08-06-1994",

year = "1994",

doi = "10.1007/3-540-58094-8_26",

language = "English (US)",

isbn = "9783540580942",

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

publisher = "Springer-Verlag",

pages = "307--325",

editor = "Maxime Crochemore and Dan Gusfield",

booktitle = "Combinatorial Pattern Matching - 5th Annual Symposium, CPM 1994, Proceedings",

}

TY - GEN

T1 - Efficient bounds for oriented chromosome inversion distance

AU - Kececioglu, John

AU - Sankoff, David

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

PY - 1994

Y1 - 1994

N2 - We study the problem of comparing two circular chromosomes that have evolved by chromosome inversion, assuming that the order of corresponding genes is known, as well as their orientation. Determining the minimum number of inversions is equivalent to finding the minimum of reversals to sort a signed circular permutation, where a reversal takes an arbitrary substring of elements and reverses their order, as well as flipping their sign. We show that tight bounds on the minimum number of reversals can be found by simple and efficient algorithms.

AB - We study the problem of comparing two circular chromosomes that have evolved by chromosome inversion, assuming that the order of corresponding genes is known, as well as their orientation. Determining the minimum number of inversions is equivalent to finding the minimum of reversals to sort a signed circular permutation, where a reversal takes an arbitrary substring of elements and reverses their order, as well as flipping their sign. We show that tight bounds on the minimum number of reversals can be found by simple and efficient algorithms.

KW - Chromosome inversion

KW - Genome rearrangements

KW - Reversal distance

KW - Sorting by signed reversals

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

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

U2 - 10.1007/3-540-58094-8_26

DO - 10.1007/3-540-58094-8_26

M3 - Conference contribution

SN - 9783540580942

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

SP - 307

EP - 325

BT - Combinatorial Pattern Matching - 5th Annual Symposium, CPM 1994, Proceedings

A2 - Crochemore, Maxime

A2 - Gusfield, Dan

PB - Springer-Verlag

T2 - 5th Annual Symposium on Combinatorial Pattern Matching, CPM 1994

Y2 - 5 June 1994 through 8 June 1994

ER -

Efficient bounds for oriented chromosome inversion distance

Abstract

Publication series

Other

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this