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:


  1. Download
    [version 1.2 - february 2008]

  2. rpoly.exe [version 1.1 - july 2007]
  3. Download minisat+.exe

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

  5. Usage:  ./rpoly inputfile


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

  2. rpoly [version 1.2 - february 2008]
    rpoly [version 1.1 - july 2007]
  3. Download and decompress minisat+

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

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


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.

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.



RPoly uses MiniSat+, a Pseudo-Boolean Optimization tool provided by Niklas Een and Niklas Sorensson (see MiniSat+)



If you have any comments or questions, please email: