Haplotype Inference on Pedigrees with Recombinations, Errors, and Missing Genotypes via SAT solvers

Details Haplotype Inference on Pedigrees with Recombinations, Errors, and Missing Genotypes via SAT solvers Haplotype Inference on Pedigrees with Recombinations, Errors, and Missing Genotypes via SAT solvers

2011-07-19

arxiv.org/abs/1107.3724v1

Computer Science

Data Structures and Algorithms

14 pages, 1 figure, 4 tables, the associated software reHCstar is available at http://www.algolab.eu/reHCstar

Scientific paper

The Minimum-Recombinant Haplotype Configuration problem (MRHC) has been highly successful in providing a sound combinatorial formulation for the important problem of genotype phasing on pedigrees. Despite several algorithmic advances and refinements that led to some efficient algorithms, its applicability to real datasets has been limited by the absence of some important characteristics of these data in its formulation, such as mutations, genotyping errors, and missing data. In this work, we propose the Haplotype Configuration with Recombinations and Errors problem (HCRE), which generalizes the original MRHC formulation by incorporating the two most common characteristics of real data: errors and missing genotypes (including untyped individuals). Although HCRE is computationally hard, we propose an exact algorithm for the problem based on a reduction to the well-known Satisfiability problem. Our reduction exploits recent progresses in the constraint programming literature and, combined with the use of state-of-the-art SAT solvers, provides a practical solution for the HCRE problem. Biological soundness of the phasing model and effectiveness (on both accuracy and performance) of the algorithm are experimentally demonstrated under several simulated scenarios and on a real dairy cattle population.

Affiliated with

Also associated with

No associations

Rating

Haplotype Inference on Pedigrees with Recombinations, Errors, and Missing Genotypes via SAT solvers does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Haplotype Inference on Pedigrees with Recombinations, Errors, and Missing Genotypes via SAT solvers, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Haplotype Inference on Pedigrees with Recombinations, Errors, and Missing Genotypes via SAT solvers will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-514684