Mendelsoft

Author

Description


MendelSoft is an open source software which detects marker genotyping incompatibilities (Mendelian errors only) in complex pedigrees using weighted constraint satisfaction techniques. The input of the software is a pedigree data with genotyping data at a single locus. The output of the software is a list of individuals for which the removal of their genotyping data restores consistency. This list is of minimum size when the program ends. Official website

Another possibility is to find the most probable consistent correction with respect to a Bayesian formulation of the problem. In this case, the output of the software is a list of individuals for which predicted genotypes differ from their genotyping data and such that the corresponding joint probability for the whole problem is maximum.

The problem, its formulation as a weighted constraint satisfaction problem, and some experimental results on simulated and real large animal pedigrees (up to 129516 individuals) are described in:

M. Sanchez, S. de Givry, and T. Schiex
Mendelian error detection in complex pedigrees using weighted constraint satisfaction techniques (preprint)
In Constraints journal, special issue on bioinformatics, 13(1), 2008.

S. de Givry, I. Palhiere, Z. Vitezica, and T. Schiex
Mendelian error detection in complex pedigree using weighted constraint satisfaction techniques
In ICLP-05 workshop on Constraint Based Methods for Bioinformatics, page 9p., Sitges, Spain, 2005.

Weighted Constraint Satisfaction Problems

MendelSoft is directly derived from ToulBar2, an open source weighted constraint satisfaction solver. This is an on-going project and future versions will appear soon. The algorithms used by the solver are described in:

J. Larrosa, and T. Schiex
In the quest of the best form of local consistency for Weighted CSP
In Proc. of IJCAI-03, pages 239-244, Acapulco, Mexico, 2003.

S. de Givry, M. Zytnicki, F. Heras, and J. Larrosa
Existential arc consistency: Getting closer to full arc consistency in Weighted CSPs
In Proc. of IJCAI-05, pages 84-89, Edinburgh, Scotland, 2005.

J. Larrosa, E. Morancho, and D. Niso
On the practical applicability of Bucket Elimination: Still-life as a case study
Journal of Artificial Intelligence Research. 23 :421-440, 2005.

C. Lecoutre, L. Sais, S. Tabary, and V. Vidal
Last Conflict based Reasoning
In Proc. of ECAI-06, pages 133-137, Trento, Italy, 2006.

For more information, see the SoftCSP web site.