An efficient algorithm for developing topologically valid matchings

Liz Hanks; Ron K. Cytron; Will Gillett

doi:10.1007/3-540-60044-2_40

An efficient algorithm for developing topologically valid matchings

Liz Hanks
, Ron K. Cytron
, Will Gillett

Department of Computer Science & Engineering

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

Abstract

We examine a problem that arises in physical DNA mapping, namely determining what common DNA is represented in two maps. We first present an example illustrating the properties of DNA mapping, and present some biological background supporting our approach. We present a new graph structure, called the Z-graph, that takes advantage of structure that develops during the mapping process, thus catalyzing the discovery of all maximum, topologically valid matchings. We describe an algorithm based on this structure and present experimental data supporting its improved performance as compared with a naive approach.

Original language	English
Title of host publication	Combinatorial Pattern Matching - 6th Annual Symposium, CPM 1995, Proceedings
Editors	Zvi Galil, Esko Ukkonen
Publisher	Springer Verlag
Pages	144-161
Number of pages	18
ISBN (Print)	3540600442, 9783540600442
DOIs	https://doi.org/10.1007/3-540-60044-2_40
State	Published - 1995
Event	6th Annual Symposium on Combinatorial Pattern Matching, CPM 1995 - Espoo, Finland Duration: Jul 5 1995 → Jul 7 1995

Publication series

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

Conference

Conference	6th Annual Symposium on Combinatorial Pattern Matching, CPM 1995
Country/Territory	Finland
City	Espoo
Period	07/5/95 → 07/7/95

Access to Document

10.1007/3-540-60044-2_40

Cite this

Hanks, L., Cytron, R. K., & Gillett, W. (1995). An efficient algorithm for developing topologically valid matchings. In Z. Galil, & E. Ukkonen (Eds.), Combinatorial Pattern Matching - 6th Annual Symposium, CPM 1995, Proceedings (pp. 144-161). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 937). Springer Verlag. https://doi.org/10.1007/3-540-60044-2_40

Hanks, Liz ; Cytron, Ron K. ; Gillett, Will. / An efficient algorithm for developing topologically valid matchings. Combinatorial Pattern Matching - 6th Annual Symposium, CPM 1995, Proceedings. editor / Zvi Galil ; Esko Ukkonen. Springer Verlag, 1995. pp. 144-161 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{df53b4716b5d498ca8ff2caafa96e773,

title = "An efficient algorithm for developing topologically valid matchings",

abstract = "We examine a problem that arises in physical DNA mapping, namely determining what common DNA is represented in two maps. We first present an example illustrating the properties of DNA mapping, and present some biological background supporting our approach. We present a new graph structure, called the Z-graph, that takes advantage of structure that develops during the mapping process, thus catalyzing the discovery of all maximum, topologically valid matchings. We describe an algorithm based on this structure and present experimental data supporting its improved performance as compared with a naive approach.",

author = "Liz Hanks and Cytron, \{Ron K.\} and Will Gillett",

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

year = "1995",

doi = "10.1007/3-540-60044-2\_40",

language = "English",

isbn = "3540600442",

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

publisher = "Springer Verlag",

pages = "144--161",

editor = "Zvi Galil and Esko Ukkonen",

booktitle = "Combinatorial Pattern Matching - 6th Annual Symposium, CPM 1995, Proceedings",

}

Hanks, L, Cytron, RK & Gillett, W 1995, An efficient algorithm for developing topologically valid matchings. in Z Galil & E Ukkonen (eds), Combinatorial Pattern Matching - 6th Annual Symposium, CPM 1995, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 937, Springer Verlag, pp. 144-161, 6th Annual Symposium on Combinatorial Pattern Matching, CPM 1995, Espoo, Finland, 07/5/95. https://doi.org/10.1007/3-540-60044-2_40

An efficient algorithm for developing topologically valid matchings. / Hanks, Liz; Cytron, Ron K.; Gillett, Will.
Combinatorial Pattern Matching - 6th Annual Symposium, CPM 1995, Proceedings. ed. / Zvi Galil; Esko Ukkonen. Springer Verlag, 1995. p. 144-161 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 937).

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

TY - GEN

T1 - An efficient algorithm for developing topologically valid matchings

AU - Hanks, Liz

AU - Cytron, Ron K.

AU - Gillett, Will

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

PY - 1995

Y1 - 1995

N2 - We examine a problem that arises in physical DNA mapping, namely determining what common DNA is represented in two maps. We first present an example illustrating the properties of DNA mapping, and present some biological background supporting our approach. We present a new graph structure, called the Z-graph, that takes advantage of structure that develops during the mapping process, thus catalyzing the discovery of all maximum, topologically valid matchings. We describe an algorithm based on this structure and present experimental data supporting its improved performance as compared with a naive approach.

AB - We examine a problem that arises in physical DNA mapping, namely determining what common DNA is represented in two maps. We first present an example illustrating the properties of DNA mapping, and present some biological background supporting our approach. We present a new graph structure, called the Z-graph, that takes advantage of structure that develops during the mapping process, thus catalyzing the discovery of all maximum, topologically valid matchings. We describe an algorithm based on this structure and present experimental data supporting its improved performance as compared with a naive approach.

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

U2 - 10.1007/3-540-60044-2_40

DO - 10.1007/3-540-60044-2_40

M3 - Conference contribution

AN - SCOPUS:84957917017

SN - 3540600442

SN - 9783540600442

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

SP - 144

EP - 161

BT - Combinatorial Pattern Matching - 6th Annual Symposium, CPM 1995, Proceedings

A2 - Galil, Zvi

A2 - Ukkonen, Esko

PB - Springer Verlag

T2 - 6th Annual Symposium on Combinatorial Pattern Matching, CPM 1995

Y2 - 5 July 1995 through 7 July 1995

ER -

Hanks L, Cytron RK, Gillett W. An efficient algorithm for developing topologically valid matchings. In Galil Z, Ukkonen E, editors, Combinatorial Pattern Matching - 6th Annual Symposium, CPM 1995, Proceedings. Springer Verlag. 1995. p. 144-161. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-60044-2_40

An efficient algorithm for developing topologically valid matchings

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this