Section 26

Minimal ARG for Kreitman data

An example ancestral recombination graph for the Kreitman (1983) data explaining the data with the minimum of 7 recombinations. The ARG was constructed by beagle and visualised by Graphviz.

Section 26 is a small collection of related programs for analysing SNP data sets under the coalescent with an infinite sites model. The collection is available as C source code and python scripts in a tar archive (note: this archive unpacks into the same directory as the tar file is located in). The software is available under the GNU Lesser General Public License. There are several choices available for the data file format, both in terms of the underlying structure of the format and of the actual sequence representation. Running each program with option -h should output a brief description of usage. At present, the collection consists of four main programs:

To compile all programs except cob, make sure that you have gcc, flex, bison, and python properly installed, then simply run make. To compile all programs, make sure that the libraries required for cob are installed in the places indicated in the Makefile and then run make all+. The distribution also contains various python scripts, mainly used for our experimentation with the programs. If you have any problems with the software, please email If possible, please include an example data set causing the problem.

The relevant citations for this software are Minimum Recombination Histories by Branch and Bound by R.B. Lyngsø, Y.S. Song & J. Hein, Proceedings of Workshop on Algorithms in Bioinformatics 2005, Lecture Notes in Computer Science 3692, pp. 239–250; Counting All Possible Ancestral Configurations of Sample Sequences in Population Genetics by Y.S. Song, R.B. Lyngsø & J. Hein, IEEE/ACM Transactions on Computational Biology and Bioinformatics 3, 239–251; Accurate Computation of Likelihoods in the Coalescent with Recombination via Parsimony by R.B. Lyngsø, Y.S. Song & J. Hein, Proceedings of International Conference on Research in Computational Molecular Biology, Lecture Notes in Computer Science 4955, pp. 463–477. Slides for a presentation of the methods are also available.

In case you wondered, the program suite is named after Section 26 at the banks of the Duckburg River. The first program in the suite was beagle that was named after the infamous Beagle Boys that go by the same acronym as branch & bound. So initially the program suite was called the beagle suite. When coming to Duckburg the Beagle Boys initially moved to Section 26 at the Duckburg River, which thus with a properly far fetching imagination can be consider the Beagle (Boys') suite.

Rune Lyngsų,