Home    Contact   FAQs   Imprint   Login  


Haplotype inference from unphased SNP data in heterozygous polyploids based on SAT


Description of SATlotyper Software
SATlotyper [1] is a software tool designed for inferring haplotypes from polyploid and polyallelic unphased SNP data.

SATlotyper uses Boolean operators and variables to formulate Haplotype Inference by Pure Parsimony (HIPP) [2] for the Boolean Satisfiability Problem (SAT) [1,3].

For finding the most parsimonious set of explaining haplotypes, SATlotyper starts with assuming one explaining haplotype and increases the number of haplotypes until a satisfying set is found.

Since SAT is NP-complete, it can not be guaranteed that a solution is found in reasonable time for a given data. However, empiric tests showed that it is possible to calculate inferences for data from real world.

Furthermore, SATlotyper gives constraints for alternative explaining solutions and is able to optimize the likelihood of the result by means of a bootstrapping procedure. More information about the program can be found in [1].
Go To Top

System Requirements
The software is distributed as a Java JAR file and requires Java Runtime Environment 1.5.0 or higher. For the user‘s convenience, the downloadable archive contains statically linked versions of MiniSat and MiraXT. The software is accessed from command line. Under UNIX like systems the program runs out of the box with MiniSat, MiraXT and the Sat4J solver. Users with Microsoft® Windows are restricted on running the Sat4J solver.
Go To Top

Release History
2008/07/30        SATlotyper_v0.1b
2008/09/17        SATlotyper_v0.1.1b
2008/11/04        SATlotyper_v0.1.1+GUI
2009/04/06        SATlotyper_v0.1.1+GUI (update)
2009/04/09        SATlotyper_v0.1.1+GUI (update2)
2009/04/23        SATlotyper_v0.1.2+GUI
2009/06/02        SATlotyper_v0.1.3+GUI
2010/02/26        SATlotyper_v0.1.4b+GUI
2010/03/01        SATlotyper_v0.1.4+GUI
2010/03/22        SATlotyper_v0.1.5+GUI
NEW: better SAT solving support for windows
Go To Top

[1] J. Neigenfind, G. Gyetvai, R. Basekow, S. Diehl, U. Achenbach, C. Gebhardt, J. Selbig, B. Kersten, Haplotype inference from unphased SNP data in heterozygous polyploids based on SAT, BMC Genomics, 9:356, 2008

[2] D. Gusfield, Haplotype inference by Pure Parsimony, Proceedings of the 14th annual Symposium on Combinatorial Pattern Matching, 144-155, 2003

[3] I. Lynce and J. P. Marques-Silva, Efficient haplotype inference with Boolean Satisfiability, National Conference on Artificial Intelligence (AAAI), 2006
Go To Top

GabiPD Webmaster