Abstract
We analyze the algorithmic complexity of physical mapping by hybridization in situations of restricted forms of chimeric errors, which is motivated by typical experimental conditions. The constituents of a chimeric probe always occur in pure form in the data base, too. This problem can be modelled by a variant of the k-consecutive ones problem. We show that even under this restriction the corresponding decision problem is \( \mathcal{N}\mathcal{P} \)-complete. Considering the most important situation of strict 2-chimerism, for the related optimization problem a complete separation between efficiently solvable and \( \mathcal{N}\mathcal{P} \)-hard cases is given based on the sparseness parameters of the clone library. For the favourable case we present a fast algorithm and a data structure that provides an effective description of all optimal solutions to the problem.
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.
References
F. Alizadeh, R. Karp, L. Newberg, D. Weisser, Physical mapping of chromosomes: a combinatorial problem in molecular biology, Algorithmica 13, 52–76, 1995.
F. Alizadeh, R. Karp, D. Weisser, G. Zweig, Physical mapping of chromosomes using unique probes, Proc. 5th Annual ACM-SIAM Symposium on Discrete Algorithms SODA’94, 489–500, 1994.
J. Atkins, M. Middendorf, On physical mapping and the consecutive ones property for sparse matrices, DAMATH: Discrete Applied Mathematics and Combinatorial Operations Research and Computer Science 71, 1996.
K. Booth, G. Lueker, Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms, J. Computer and System Sciences 13, 335–379, 1976.
D. Fulkerson, O. Gross, Incidence matrices and interval graphs, Pacific Journal of Mathematics 15, 835–856, 1965.
P. Goldberg, M. Golumbic, H. Kaplan, R. Shamir, Four strikes against physical mapping of DNA, J. Computational Biology 2, 139–152, 1995.
D. Greenberg, S. Istrail, The chimeric mapping problem: Algorithmic strategies and performance evaluation on synthetic genomic data, Computers and Chemistry 18, 207–220, 1994.
D. Greenberg, S. Istrail, Physical Mapping by STS Hybridization: Algorithmic Strategies and the challenge of Software Evaluation, J. Comp. Biology 2, 219–273, 1995.
M. Garey, D. Johnson, Computers and Intractability: A Guide to NP-Completeness, Freeman, 1979.
M. Garey, D. Johnson, R. Tarjan, The planar Hamiltonian circuit problem is NP-complete, SIAM J. Computing 5, 704–714, 1976.
To Know Ourselves. Human Genome Program, U.S. Department of Energy, 1996.
W. Hsu. A simple test for the consecutive ones property, Proc. 3rd Int. Symposium on Algorithms and Computation ISAAC’92, LNCS650, 459–468, 1992.
W. Hsu, On physical mapping algorithms: an error tolerant test for the consecutive ones property, Proc. 3rd Int. Conf. Computing and Combinatorics, COCOON’97, LNCS 1267, 242–250, 1997.
H. Kaplan, R. Shamir, R. Tarjan. Tractability of parameterized completion problems on chordal and interval graphs: Minimum fill-in and physical mapping, Proc. 35th Symp. on Foundations of Computer Science FOCS’94, 780–793, 1994.
N. Korte, R. Möhring. An incremental linear-time algorithm for recognizing interval graphs, SIAM J. Computing 18, 68–81, 1989.
S. Weis, Das Entscheidungsproblem Physikalische Kartierung mit starkchimerischen Fehlern, Technical Report A-99-05, Med. Uni. Lübeck, Institut für Theoretische Informatik, 1999.
S. Weis, Zur algorithmischen Komplexität des Optimierungsproblems Physikalische Kartierung mit starkchimerischen Fehlern, Technical Report A-99-06, Med. Uni. Lübeck, Institut für Theoretische Informatik, 1999.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Weis, S., Reischuk, R. (2000). The Complexity of Physical Mapping with Strict Chimerism. In: Du, DZ., Eades, P., Estivill-Castro, V., Lin, X., Sharma, A. (eds) Computing and Combinatorics. COCOON 2000. Lecture Notes in Computer Science, vol 1858. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44968-X_38
Download citation
DOI: https://doi.org/10.1007/3-540-44968-X_38
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-67787-1
Online ISBN: 978-3-540-44968-3
eBook Packages: Springer Book Archive