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):

  1. Download
    rpoly.exe     [version 1.2 - february 2008]


    2. rpoly.exe [version 1.1 - july 2007]

  2. Download minisat+.exe

  3. Keep on the same directory rpoly.exe and minisat+.exe executables

  4. Usage:  ./rpoly inputfile

UNIX:   

  1. Download
    rpoly [version 1.2.1 - may 2008] (README)


    2. rpoly [version 1.2 - february 2008]
    rpoly [version 1.1 - july 2007]

  2. Download and decompress minisat+

  3. Keep on the same directory rpoly and minisat+_64-bit_static executables

  4. 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

Version 1.2 has a more detailed output format, see example.

 

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.