|
|
 |
SATlotyper |
Haplotype inference from unphased SNP data in heterozygous polyploids based on SAT |
|
Contents:
|
|
|
|
|
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
|
|
|
|
|
|
References
|
|
[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
|
|
|
|
|
|
|
|
