HapBound and SHRUB

Software accompaniment to
Song, Y.S., Wu, Y. and Gusfield, D. Efficient computation of close lower and upper bounds on the minimum number of recombinations in biological sequence evolution, Proceedings of ISMB 2005. Bioinformatics 21, Suppl.1, (2005) i413-i422.

Note: Files can be downloaded using "Save Link/Target As..." After downloading the softwares, you may need to change file access permissions.
(e.g. chmod u+x HapBound)

Lower bound

Upper bound

Example data sets

Kreitman's data
(SHRUB and HapBound -M produce 7. The optimal RecMin bound is 6.)
Simulated data set 1 (generated using Hudson's MS with n=50, theta=10, rho=15)
(SHRUB and HapBound -S produce 10. The optimal RecMin bound is 8.)
Simulated data set 2 (generated using Hudson's MS with n=75, theta=10, rho=10)
(SHRUB produces 12, while HapBound -S produces 11. The optimal RecMin bound is 11.
The minimum number of recombinations for this data set is 12.)

Example Ancestral Recombination Graph (ARG)

Recommended software for viewing the ARGs generated by SHRUB

GIF files needed for graphics