Software from Dan Gusfield and Gusfield's group at U.C. Davis July 2018

Software

21. Integer Programming for Traveling Salesman Problems. Three programs to generate compact ILP formulations for TSP problems.
Perl program to generate an ILP formulation for the TS Path problem, using the Gavish-Graves (GG) compact ILP formulation

Perl program to generate an ILP formulation for the TS Tour problem, using the Gavish-Graves (GG) compact ILP formulation

Perl program to generate an ILP formulation for the TS Path problem, using the Miller-Tucker-Zemlin (MTZ) compact ILP formulation

20. ChordAlg (updated version 2015): An interactive suite of programs for the study of Chordal Graph Theory and related topics.
ChordAlg was developed by Rob Gysel (under the supervision of Dan Gusfield) and first released in 2009. It is maintained and periodically expanded by Rob Gysel.
Find the current version at ChordAlg

19. July 2015: PHENDIST, Computing the Phenotypic Distance.
Software accompaning the paper
``Association Mapping for Compound Heterozygous Traits Using Phenotypic Distance and Integer Programming"
by Dan Gusfield and Rasmus Nielsen, in WABI 2015 (see recent publications list).
tarfile including a readme to explain the programs and files

18. June, 2015: Software accompaning the paper "Persistent Phylogeny: A Galled-tree and Integer Linear Programming Approach"
Dan Gusfield

Program perfreduce.pl
This removes fully-compatible columns from a binary input matrix M for the persistent-phylogeny problem. Run this before creating the extended matrix M_e. The first line of the input should contain a set identifier of the form X.Y where X and Y are integers.

Program PERILP.pl
This creates the ILP needed to solve an instance of the persistent-phylogeny problem. The input is an extended matrix M_e, where the first line of the input contains a set identifier of the form X.Y, where X and Y are integers. The program assumes that the entries in M_e are 0, 1, or 2, where 2 has the meaning of a `?` in the persistent-phylogeny problem.

If the file that contains the ILP is called ilp, the Gurobi ILP solver (assuming you have installed it) can be called by the command line:
gurobi_cl timelimit=360 resultfile=blat.sol ilp
that will run the solver, with a timeout after 360 seconds, and put the result (the values of all the variables) in the file blat.sol. You can use a different name for the resultfile but it has to have the .sol extension.

17. April 2015: PerftPhy -- Software accompaning the paper "PerfectPhy: A program for the construction of perfect phylogenies from data with an arbitrary number of states"
Michael Coulombe, Kristian Stevens and Dan Gusfield

tarfile with programs and example files.
This is the software implementing the algorithms of Kannan and Warnow for efficiently determining if a fixed k-state matrix has a perfect phylogeny. If perfect phylogenies exist, for the input dataset PerfectPhy implements their algorithm for enumerating them. We have also included extensions for finding specific perfect phylogenies, minimum size, minimum edge weight, and maximum edge support.

16. MultPerf: Software accompaning the paper `` The Multistate Perfect Phylogeny Problem with Missing and Removable Data: Solutions via Integer Programming and Chordal Graph Theory" RECOMB 2009

tarfile with programs and example files.
This is the full version, with all the programs (other than Cplex) needed to recreate the empirical results in the paper. However, it requires that you have Cplex to solve any ILPs that are created, and it has some compiled C code for Mac OSX.

tarfile with programs and example files. This version does not require Cplex, but has some compiled C code for Mac OSX.
This version will create any needed ILP formulations, but not solve any ILPs, since Cplex is not available. However, many of the data sets may solve without the need for solving an ILP. Extract the files from this tarfile in a different directory than the files from the first tarfile.

15. OptimalCR: Link to software accompaning the paper ``EXTENSIONS AND IMPROVEMENTS TO THE CHORDAL GRAPH APPROACH TO THE MULTI-STATE PERFECT PHYLOGENY PROBLEM" in IEEE/ACM Transactions on Computational Biology and Bioinformatics, Vol. 8, 2011, pages 912-917, by R. Gysel and D. Gusfield

Software to solve the Character Removal (CR) Problem for the Multistate Perfect Phylogeny Problem

14. Link to software accompaning the paper ``Triangulation Heuristics for Maximum Character Compatibility."
Proceedings, IEEE 3rd International Conference on Computational Advances in Bio and Medical Sciences (ICCABS 2013). R. Gysel K. Stevens and D. Gusfield

Heuristics for Triangulation for Maximum Character Compatibility

13. Program CCHI, Clark Consensus Haplotype Inference, June 2007: A full implementation of Clark Consensus Haplotype Inference Method

12. Package FPPG: Integer Programming Formulations for Phylogenetic and Population Genetic Problems on Haplotypic and Genotypic Data.

June 9, 2006
We have posted twelve Perl programs that produce integer programming formulations (that can be input in lp format and solved by Cplex or GLPK) for seven problems that arise in phylogenetics and population genetics. These problems and the ideas behind their ILP solution are discussed in the paper: ``Integer Programming Formulations and Computations Solving Phylogenetic and Population Genetic Problems with Missing or Genotypic Data"
D. Gusfield and Y. Frid and D. Brown
LNCS, vol. 4598, Proceedings of the 13'th Annual International Conference on Combinatorics and Computing, 2007, p. 51-64

Problem M1: Given a binary matrix M with some entries missing, fill in (impute) the missing values so as to **minimize** the number of incompatible pairs of sites (sites that contain all four binary pairs 0,0; 0,1; 1,0; 1,1) in the resulting matrix M'.

Programs misstest.pl and bbmisstest.pl create the ILP formulations to solve this problem. Both ILP formulations solve very rapidly over a wide range of data, but the formulation created by bbmisstest.pl solves faster.

Problem HM1: Given a ternary matrix M representing the genotypes of n individuals, find a pair of haplotypes for each of the n individuals that explain the genotypes (that is, phase the unphased genotype data), so as to minimize the number of incompatible pairs of sites in the resulting haplotype matrix M'.
Programs hmisstest.pl and hbbmisstest.pl create the ILP formulations to solve this problem. Both ILP formulations solve reasonably rapidly over a wide range of data, but the formulation created by hbbmisstest.pl solves faster.

Problem TR1: Given a binary matrix M with some entries missing, impute missing values to give the **minimum** number of columns to remove, so that there are no pairs of columns that are incompatible in the resulting matrix M'. Note that if there is no cell that has a missing value, then this problem finds the minimum number of columns to remove from M so that the resulting matrix M' has no pair of incompatible columns.
Program mcontest.pl creates the ILP formulations to solve this problem by CPLEX or GLPK (or other ILP solvers).

Problem HR1: Given a ternary matrix M representing the genotypes of n individuals, find a pair of haplotypes for each of the n individuals that explain the genotypes (that is, phase the unphased genotype data), so as to **minimize** the number of columns that have to be removed in order that no incompatible pairs of sites remain in the resulting haplotype matrix M'.
Program hmcontest.pl creates the ILP formulations to solve this problem by CPLEX or GLPK (or other ILP solvers).

Problem HKM1: Given a binary matrix M with some entries missing, fill in (impute) the missing values so as to **minimize** the resulting Hudson-Kaplan lower bound on the number of recombinations needed to generate the binary sequences, under the infinite sites model of mutations.

Programs misstesthk.pl and bbmisstesthk.pl create the ILP formulations to solve this problem. Both ILP formulations solve very rapidly over a wide range of data, but the formulation created by bbmisstesthk.pl solves faster.

Problem HKHM1: Given a ternary matrix M representing the genotypes of n individuals, find a pair of haplotypes for each of the n individuals that explain the genotypes (that is, phase the unphased genotype data), so as to minimize the resulting Hudson-Kaplan lower bound on the number of recombinations needed to generate the binary sequences, under the infinite sites model of mutations.
Programs hmisstesthk.pl and bbhmisstesthk.pl create the ILP formulations to solve this problem. Both ILP formulations solve reasonably rapidly over a wide range of data, but the formulation created by hbbmisstesthk.pl solves faster.

Problem MinPPH: Given a ternary matrix M representing the genotypes of n individuals, find a pair of haplotypes for each of the n individuals that explain the genotypes (that is, phase the unphased genotype data), so that the deduced haplotypes fit a perfect phylogeny (that is, have no pairs in conflict), and minimize the number of distinct haplotypes used (i.e., over all solutions to the phasing problem that fit a perfect phylogeny).
Programs minpph.pl and bbminpph.pl create the ILP formulations to solve this problem. Both produce formulations that solve reasonably quickly, but the formulation created by bbminpph.pl solves much faster than the one created by minpph.pl.

To download any of these programs, click on:
misstest.pl
bbmisstest.pl
hmisstest.pl
hbbmisstest.pl
mcontest.pl
hmcontest.pl
misstesthk.pl
bbmisstesthk.pl
hmisstesthk.pl
bbhmisstesthk.pl
minpph.pl
bbminpph.pl
example input file data1g that can be used as input by any of these programs

11. Package FMPH: Integer Programming Formulations To Solve Maximum Parsimony Haplotyping

The following two programs create integer programs (solvable by Cplex or GLPK) that find haplotype pairs for a set of input genotypes (that is, the haplotypes phase the genotypes), **minimizing** the number of distinct haplotypes used in the solution. The first program, minthap.pl, implements the ILP formulation called RTIP, generating an integer program whose solution minimizes the **total** number of distinct haplotypes used, including haplotypes obtained from homozygous genotypes or single site ambiguous genotypes in the input set of genotypes, even if those haplotypes are not used to resolve any of the multi-site ambiguous genotypes in the input. The second program, mindhap.pl, generates an integer program whose solution minimizes the number of distinct haplotypes needed to phase just the ambiguous genotypes in the input.
The methods underlying these programs are described in the paper ``Haplotyping by Pure Parsimony", which can be obtained from the recent papers page.

minthap.pl
mindhap.pl

Phylogenetic Networks with Recombination (Ancestral Recombination Graphs) and other Software concerning recombination

January, 2009

10. RecBlock: Software to compute the Minimum Mosaic of a Set of Recombinants

RecBlock implements the methods described in the paper "Improved Algorithms for Inferring the Minimum Mosaic of a set of Recombinants" available via the link to recent papers.
For RecBlock executables for OS X RecBlock for OS X (use "save as" to download)
For RecBlock executables for Linux or Windows RecBlock for Linux or Windows
For instructions on running RecBlock README.txt
For a simple example of the data data example

9. Software for Phylogenetic and Genealogical Networks

We have posted three sets of programs that concern problems of deriving and analyzing Phylogenetic Networks. The first set of programs, HapBound-GC and SHRUB-GC, concern unconstrained recombination with both crossovers and gene-conversions allowed. The second set, HapBound and SHRUB, concern unconstrained recombination with only crossovers allowed. The third set of programs concern Galled Trees, which are phylogenetic networks where the recombination cycles are constrained to be disjoint.

8. HapBound-GC and SHRUB-GC


March, 2006
HapBound-GC computes lower bounds on the number of single-crossover recombinations and gene-conversions needed to generate a set of binary sequences under the infinite sites assumption (e.g., one mutation per site). SHRUB-GC constructs an actual network (ARG) that derives the set of sequences, minimizing the total number of crossover and conversion events (when run to completion). See the RECOMB 06 paper on the list of recent papers for an explanation of the programs and their underlying ideas.
To download HapBound-GC and SHRUB-GC click on
HapBound-GC and SHRUB-GC

7. HapBound and SHRUB


April 2005
HapBound computes lower bounds on the number of recombinations needed to generate a set of binary sequences under the infinite sites assumption (e.g., one mutation per site). SHRUB constructs an actual network (ARG) that derives the set of sequences. We have found through extensive evaluation that the lower bounds computed by HapBound are close (often equal) to the number of recombinations used by SHRUB. See the ISMB 2005 paper by Song, Wu and Gusfield on the recent papers list for more on this.
To download SHRUB click on
SHRUB

6. Galled Tree Programs

October 12, 2004
We are now beginning to release several programs concerned with the reconstruction of phylogenetic network with constrained and unconstrained recombination, given a set of binary sequences. The first two programs determine if the input sequences can be reconstructed with a galled-tree network, i.e., a phylogenetic network where all the cycles caused by recombinations are non-intersecting (node disjoint). One version allows only single crossover recombination, while the other program allows multiple crossover recombination. When an ancestral sequence has been specified in advance, and there is a galled-tree for the input sequences using that ancestral sequence, the galled-tree produced by the program is guaranteed to use the minimum number of recombination nodes (events) over all possible phylogenetic networks that use the specified ancestral sequence and that generate the input sequences. When no ancestral sequence is specified in advance, and there is a galled-tree for the input sequences using some (program determined) ancestral sequence, the galled-tree produced is guaranteed to use the minimum number of recombination nodes over all possible phylogenetic networks that generate the input sequences, and all possible choices of ancestral sequence. More details are several papers available from the recent papers page, and in the README file for the software.

To download a tar file with the programs and associated files, click on
galledtree programs

5. Perfect Phylogeny Haplotyping

We have four related software packages for a question of current interest concerning haplotype inference:

LPPH - A Linear-Time Algorithm for Perfect Phylogeny Haplotyping (NEW, posted May 12, 2005)

GPPH (formerly called PPH) - Perfect Phylogeny Haplotyper based on graph realization

DPPH - Perfect Phylogeny Haplotyper: a direct method

BPPH - Perfect Phylogeny Haplotyper: The Berkeley method

These programs take in unphased, SNP genotype data, and determine whether that data can be explained by pairs of haplotypes (phased data) which satisfy either the three or the four-gamete test, as specified by the user. That is, whether there are pairs of haplotypes that explain the genotype data, and can fit a rooted or an unrooted tree, where each change of state occurs only once in the tree. If there is such a set of haplotype pairs that explain the genotype data, the program produces one set, along with the tree that it fits, and determines if that set is the unique solution to the problem. All three programs produce a count of the number of solutions, and program DPPH also produces a representation of all of them. Program LPPH is the fastest of the four programs.

For background on this problem, and the two methods, see the papers with "Perfect Phylogeny" in the title in: recent papers or see the specific references on the pages linked above.

4. As a by-product of writing the program GPPH, we also have a stand-alone program for solving the graph-realization problem. The graph realization problem is equivalent to determining if a binary matroid is graphic. To download a copy:
Graph Realization

String Algorithms; Sequence Alignment and Analysis

We also have three software packages that implement string and sequence analysis algorithms in computational biology and bioinformatics: XPARAL and Strmat and Seqio

3. XPARAL is an X-Windows based program which computes a parameterized alignment of two sequences, displaying all of the optimal alignments for the two sequences when the costs of substitutions, gaps and insertions or deletions are varied. The user provides as input two sequences, an alignment type (global, local, end-gap free and substring), and selects which two of the alignment costs to vary. The program then displays the upper right quadrant of a two-dimensional graph, where the graph axes specify the possible values of the varying costs. The quadrant is partitioned into convex polygons, where each polygon specifies an alignment that is optimal over the range of costs within the polygon. The user is then able to view and print out those optimal alignments.

Several updates to XPARAL were made By Marisano James in Spring 2010, including compiling a version for MAC OSX. Source code is also now posted.

2. Strmat consists of a simple menu system and source C code implementing many exact matching methods, particularly those based on the Z algorithm and on suffix trees.


1. Seqio-1.2.2 is a bioinformatics/database format conversion package (version 1.2.2) written by Jim Knight in 1996 when he was a postdoc here at UCD. There has been no further development since then on the version available here.
 
 




Return to Gusfield's Departmental page

This research was partially supported by NSF grants ITR-9723346, SEI-BIO 0513910, CCF-0515378, IIS-0803564, CCF-1017580 and NSF IIS-1219278.

Return to Gusfield Homepage


July, 2015