School of
Electrical Engineering
and Computer Science


Excap is a tool for finding an informative subset of a set of markers. Genetic markers, defined as variable regions of DNA, can be utilized for distinguishing individuals or populations. As long as markers are independent, it is easy to combine the information they provide. For nonrecombinant sequences like mtDNA, choosing the right set of markers for forensic applications can be difficult and requires careful consideration. In particular, one wants to maximize the utility of the markers.

Excap uses a depth-first search combined with a branch-and-bound approach to search the space of marker sets of a given size. Since the worst case complexity is exponential we also provide some data-reduction techniques and a heuristic in Excap.

A paper on Excap has been published: Kahles A, Sarqume F, Savolainen P, Arvestad L (2013), "Excap: maximization of haplotypic diversity of linked markers.", PLoS One 8(11), e79012.


Excap was written as a student project by Andre Kahles and Fahad Sarqume, under the supervision of Lars Arvestad and Peter Savolainen.


The program code is found at SourceForge:


Andre Kahles was funded through a scholarship of the Klaus Murmann Fellowship Programme of the Foundation of German Business (Stiftung der Deutschen Wirtschaft, SDW). Peter Savolainen is a Royal Academy of Sciences Research Fellow supported by a grant from the Knuth and Alice Wallenberg Foundation.
Published by: Lars Arvestad <>
Updated 2014-09-24