Abstract
We focus on the combinatorial analysis of physical mapping with repeated probes. We present computational complexity results, and we describe and analyze an algorithmic strategy. We are following the research avenue proposed by Karp [9] on modeling the problem as a combinatorial problem - the Hypergraph Superstring Problem - intimately related to the Lander-Waterman stochastic model [16]. We show that a sparse version of the problem is MAXSNP-complete, a result that carries over to the general case. We show that the minimum Sperner decomposition of a set collection, a problem that is related to the Hypergraph Superstring problem, is NP-complete. Finally we show that the Generalized Hypergraph Superstring Problem is also MAXSNP-hard.We present an efficient algorithm for retrieving the PQ-tree of optimal zero repetition solutions, that provides a constant approximation to the optimal solution on sparse data. We provide experimental results on simulated data.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Papadimitriou C.H. Approximability. In Computational Complexity. Addison-Wesley Publishing Company, 1994.
Papadimitriou C.H. and Yannakakis M. The traveling salesman problem with distances one and two. Math. of Operations Research, pages 1–12, 1993.
Green E.D. and Green P. Sequence-tagged site (sts) content mapping of human chromosomes: Theoretical considerations and early experiences. PCR Methods and Applications, 1:77–90, 1991.
Greenberg D.S. and Istrail S. Physical mapping by sts hybridization: Algorithmic strategiews and the challange of software evaluation. Journal of Computational Biology, 2, Number 2:219–274, 1995.
Lander E.S. and Waterman M.S. Genomic mapping by fingerprinting random clones: A mathematical analysis. Genomics, 2:231–239, 1988.
Alizadeh F., Karp M.R., Newberg L.A., and Weisser D.K. Physical mapping of chromosomes: A combinatorial problem in molecular biology. Algorithmica, 13:52–76, 1995.
Alizadeh F., Karp R.M., Weisser D.K., and Zweig G. Physical mapping of chromosomes using unique probes. Manuscript, 1995.
Lipski W. Jr. On strings containing all subsets as substrings. Discrete Mathematics, 21:253–259, 1978.
Karp R.M. Mapping the genome: Some combinatorial problems arising in molecular biology. Symposium on Discrete Algorithms, SODA 93:278–285, 1993.
Waterman M.S. Personal communication about the work of Simon Tavare. Ocrober, 1997.
Nelson D.O. and Speed T.P. Statistical issues in constructing high resolution physical maps. Statistical Science, 9, No. 3:334–354, 1994.
Erdos Paul. Personal Communication, 1993.
Arratia R., Lander E.S., Tavare S., and Waterman M.S. Genomic mapping by anchoring random clones: A mathematical analysis. Genomics, 11:806–827, 1991.
Booth K.S. and Lueker G.S. Testing for the consecutive ones property, interval graphs and planarity using pq-tree algorithms. J. Comput. Sys. Sci., 13:335–379, 1976.
Foote S., Vollrath D., Hilton A., and Page D. The human y chromosome: Overlapping dna clones spanning the euchromatic region. Science, pages 60–66, October 1992.
Lander E.S. and Waterman M.S. Genomic mapping by fingerprinting random clones: A mathematical analysis. Genomics, 2, Number 2:219–274, 1988.
Waterman M.S. In Introduction to Computational Biology. Chapman and Hall, 1995.
Shamir. Personal communication, October 1997.
Ghosh S.P. Consecutive storage of relevant records with redundancy. Communications of the ACM, 18:464–471, 1975.
Kou A.T. Polynomial complete consecutive information retrieval problems. SIAM J. Computing, 6, No.1:67–75, 1977.
Lipski W. Information storage and retrieval-mathematical foundations ii. Theoretical Computer Science, 3:183–212, 1976.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1999 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Batzoglou, S., Istrail, S. (1999). Physical Mapping with Repeated Probes: The Hypergraph Superstring Problem. In: Crochemore, M., Paterson, M. (eds) Combinatorial Pattern Matching. CPM 1999. Lecture Notes in Computer Science, vol 1645. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-48452-3_5
Download citation
DOI: https://doi.org/10.1007/3-540-48452-3_5
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-66278-5
Online ISBN: 978-3-540-48452-3
eBook Packages: Springer Book Archive