RPoly: Haplotype Inference by Pure Parsimony
RPoly is a software to infer haplotypes from genotype data using the pure parsimony criterion, i.e., find the minimum number of haplotypes which explain a given set of genotypes.
Rpoly is an efficient tool which uses pseudo-Boolean optimization to solve haplotype inference by pure parsimony.
For further information see:
[version 1.1] A. Graça, J. P. Marques-Silva, I. Lynce and A. Oliveira, Efficient Haplotype Inference with Pseudo-Boolean Optimization, Algebraic Biology 2007, July 2007.
[version 1.2] A. Graça, J. P. Marques-Silva, I. Lynce and A. Oliveira, Efficient Haplotype Inference with Combined CP and OR Techniques (Short Paper), CPAIOR 2008, May 2008.
How to Use RPoly:
WINDOWS (CYGWIN EXECUTABLES):
Download
rpoly.exe [version 1.2 - february 2008]
Download minisat+.exe
Keep on the same directory rpoly.exe and minisat+.exe executables
Usage: ./rpoly inputfile
UNIX:
Download and decompress minisat+
Keep on the same directory rpoly and minisat+_64-bit_static executables
Usage: ./rpoly inputfile
Input file format:
- The input file must contain the genotype data. Each line represents a genotype and corresponds to an individual. Each column represents a SNP. A 0 represents the wild homozygous allele, a 1 represents a homozygous mutant allele and a 2 corresponds to a heterozygous position. All individuals must have the same number of SNPs.
Example:
2110202
2002110
1011101
2022202
2222222
Output format:
- The result is an explanation of each genotype into a haplotype pair in such a way that the number of distinct haplotypes is minimum. In each haplotype, 0 represents the wild allele, while 1 corresponds to a mutant allele.
Example:
RPoly's result for the example above is:
1011101 = 1011101 + 1011101
2002110 = 0000110 + 1001110
2022202 = 0000000 + 1011101
2110202 = 0110001 + 1110100
2222222 = 0110001 + 1001110
MiniSat+:
RPoly uses MiniSat+, a Pseudo-Boolean Optimization tool provided by Niklas Een and Niklas Sorensson (see MiniSat+)
Contacts:
If you have any comments or questions, please email:
assg_at_sat.inesc-id.pt.