Abstract
Consistency checking is a fundamental computational problem in genetics. Given a pedigree and information on the genotypes (of some) of the individuals in it, the aim of consistency checking is to determine whether these data are consistent with the classic Mendelian laws of inheritance. This problem arose originally from the geneticists’ need to filter their input data from erroneous information, and is well motivated from both a biological and a sociological viewpoint. This paper shows that consistency checking is NP-complete, even with focus on a single gene and in the presence of three alleles. Several other results on the computational complexity of problems from genetics that are related to consistency checking are also offered. In particular, it is shown that checking the consistency of pedigrees over two alleles, and of pedigrees without loops, can be done in polynomial time.
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
Abecasis, G.R., Cherny, S.S., Cookson, W.O., Cardon, L.R.: Merlin: Rapid analysis of dense genetic maps using sparse gene flow trees. Nature Genetics 30, 97–101 (2002)
Aceto, L., Hansen, J.A., Ingólfsdóttir, A., Johnsen, J., Knudsen, J.: The complexity of checking consistency of pedigree information and related problems, Research Report RS–03–17, BRICS (2003), Available from http://www.brics.dk/RS/03/17/
Bryant, R.: Graph-based algorithms for boolean function manipulation. IEEE Trans. Comput. C-35, 677–691 (1986)
Decode News Center (November 2001), http://www.decode.com/news/releases/
Gu, J., Purdom, P.W., Franco, J., Wah, B.W.: Algorithms for the satisfiability (SAT) problem: a survey. In: Satisfiability problem: theory and applications (Piscataway, NJ, 1996). DIMACS Ser. Discrete Math. Theoret. Comput. Sci, vol. 35, pp. 19–151. Amer. Math. Soc, Providence (1997)
Gudbjartsson, D.F., Jonasson, K., Kong, C.A.: Fast multipoint linkage calculation with Allegro. Nature Genetics 20, 12–13 (2000)
Klug And, W.S., Cummings, M.R.: Concepts of Genetics, 5th edn. Prentice-Hall, Englewood Cliffs (1997)
Kruglyak, L., Daly, M.J., Reeve-Daly, M.P., Lander, E.S.: Parametric and nonparametric linkage analysis: A unified multipoint approach. American Journal of Human Genetics 58, 1347–1363 (1996)
Lange, K., Goradia, T.M.: An algorithm for automatic genotype elimination. American Journal of Human Genetics 40, 250–256 (1987)
Li, J., Jiang, T.: Efficient rule-based haplotyping algorithms for pedigree data [extended abstract]. In: Proceedings of RECOMB 2003, Berlin, Germany, April 10-13, pp. 197–206. ACM, New York (2003)
O’Connell, J.R., Weeks, D.E.: Pedcheck: A program for identification of genotype incompatibilities in linkage analysis. American Journal of Human Genetics 63, 259–266 (1998)
O’Connell, J.R., Weeks, D.E.: An optimal algorithm for automatic genotype elimination. American Journal of Human Genetics 65, 1733–1740 (1999)
Papadimitriou, C.H.: Computational Complexity. Addison-Wesley, Reading (1995)
Piccolboni, A., Gusfield, D.: On the complexity of fundamental computational problems in pedigree analysis, Tech. Rep. CSE-99-8, Computer Science Department, University of California, Davis (September 1999); Revised version to appear in the Journal of Computational Biology
Sobel, E., Papp, J.C., Lange, K.: Detection and integration of genotyping errors in statistical genetics. American Journal of Human Genetics 70, 496–508 (2002)
Strachan, T., Read, A.P.: Human Molecular Genetics 2. Wiley-Liss, Chichester (1999)
Valiant, L.G.: The complexity of computing the permanent. Theoret. Comput. Sci. 8, 189–201 (1979)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Aceto, L., Hansen, J.A., Ingólfsdóttir, A., Johnsen, J., Knudsen, J. (2003). The Complexity of Checking Consistency of Pedigree Information and Related Problems. In: Blundo, C., Laneve, C. (eds) Theoretical Computer Science. ICTCS 2003. Lecture Notes in Computer Science, vol 2841. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-45208-9_15
Download citation
DOI: https://doi.org/10.1007/978-3-540-45208-9_15
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-20216-5
Online ISBN: 978-3-540-45208-9
eBook Packages: Springer Book Archive