An abstract interpretation framework for genotype elimination algorithms. (English) Zbl 1242.68167

Summary: We apply abstract interpretation to the problem of genotype elimination in pedigrees. First, we give a formalization of some existing algorithms that try to remove from pedigrees all genotypes that violate the Mendelian rules of inheritance. The formalization enables the application of the abstract interpretation technique to the problem. We then introduce a particular abstraction, parameterized on given partitions of the set of genotypes. We instantiate this abstraction in order to obtain two existing algorithms for allele consolidation, thus giving a formal proof of their correctness. Moreover, the second of these two algorithms is shown to be an example of a forward complete abstraction.


68Q60 Specification and verification (program logics, model checking, etc.)
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68P05 Data structures


Pedcheck; Celer
Full Text: DOI


[1] Aceto, Luca; Hansen, Jens A.; Ingólfsdóttir, Anna; Johnsen, Jacob; Knudsen, John, The complexity of checking consistency of pedigree information and related problems, J. comput. sci. technol., 19, 1, 42-59, (2004)
[2] Patrick Cousot, Radhia Cousot, Abstract interpretation: A unified lattice model for static analysis of programs by construction or approximation of fixpoints, in: POPL, 1977, pp. 238-252. · Zbl 1149.68389
[3] Patrick Cousot, Radhia Cousot, Systematic design of program analysis frameworks, in: POPL, 1979, pp. 269-282. · Zbl 0413.06004
[4] De Francesco, Nicoletta; Lettieri, Giuseppe; Martini, Luca, Celer: an efficient program for genotype elimination, (), 56-70
[5] Nicoletta De Francesco, Giuseppe Lettieri, Luca Martini, Efficient genotype elimination via adaptive allele consolidation, IEEE/ACM Transactions on Computational Biology and Bioinformatics, 2012, IEEE Computer Society Digital Library, IEEE Computer Society, http://doi.ieeecomputersociety.org/10.1109/TCBB.2012.46.
[6] Alfons Geser, Jens Knoop, Gerald Lüttgen, Bernhard Steffen, Oliver Rüthing, Chaotic fixed point iterations, Technical Report MIP-9403, Univ. of Passau.
[7] Giacobazzi, Roberto; Ranzato, Francesco; Scozzari, Francesca, Making abstract interpretations complete, J. ACM, 47, 2, 361-416, (2000) · Zbl 1133.68370
[8] Lange, K.; Goradia, T.M., An algorithm for automatic genotype elimination, Am. J. human genetics, 40, 250-256, (1987)
[9] Logozzo, Francesco; Peled, Doron; Zuck, Lenore D., ()
[10] Luo, Y.; Lin, S., Finding starting points for Markov chain monet Carlo analysis of genetic data from large and complex pedigrees, Genet. epidemiol., 25, 1, 14-24, (2003)
[11] O’Connell, J.R.; Weeks, D.E., An optimal algorithm for automatic genotype elimination, Am. J. human genetics, 65, 6, 1733-1740, (1999)
[12] O’Connell, Jeffrey R.; Weeks, Daniel E., The vitesse algorithm for rapid exact multilocus linkage analysis via genotype set-recoding and fuzzy inheritance, Nature genetics, 11, 4, 402-408, (1995)
[13] O’Connell, Jeffrey R.; Weeks, Daniel E., Pedcheck: a program for identification of genotype incompatibilities in linkage analysis, The American journal of human genetics, 63, 1, 259-266, (1998)
[14] Pirinen, Matti; Gasbarra, Dario, Finding consistent gene transmission patterns on large and complex pedigrees, IEEE/ACM trans. comput. biol. bioinformatics, 3, 3, 252-262, (2006)
[15] Francesco Ranzato, Olivia Rossi-Doria, Francesco Tapparo, A forward-backward abstraction refinement algorithm, in: Logozzo et al. [9], pages 248-262. · Zbl 1138.68458
[16] Ranzato, Francesco; Tapparo, Francesco, Generalized strong preservation by abstract interpretation, J. log. comput., 17, 1, 157-197, (2007) · Zbl 1120.68074
[17] Ranzato, Francesco; Tapparo, Francesco, Generalizing the paige – tarjan algorithm by abstract interpretation, Inf. comput., 206, 5, 620-651, (2008) · Zbl 1197.68054
[18] Sanchez, Marti; Givry, Simon; Schiex, Thomas, Mendelian error detection in complex pedigrees using weighted constraint satisfaction techniques, Constraints, 13, 1-2, 130-154, (2008) · Zbl 1144.92324
[19] Susumu, Suzuki; Toshihide, Ibaraki, The complexity of assigning genotypes to people in a pedigree consistently, Discrete mathematics, 307, 16, 2122-2131, (2007) · Zbl 1112.92040
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.