ON FINDING TOPOLOGICALLY VALID MATCHINGS IN RESTRICTION-FRAGMENT MAPS
Liz Hanks, Ron K. Cytron, Will D. Gillett · International Journal of Foundations of Computer Science · 1996
We examine a problem that arises in physical DNA mapping, namely determining what common DNA is represented in two maps. We present an example illustrating the properties of DNA mapping, and motivate our approach. We present a new graph structure, called the Ƶ-graph, that takes advantage of structure that develops during the mapping process, thus catalyzing the discovery of all relevant fragment matchings. We describe an algorithm based on this structure and present experimental data supporting its improved performance as compared with a naive approach.