Computing Lowest Single Ancestors

Lowest Single Ancestors (LSAs) are a generalization of Lowest Common Ancestors. They are widely used in phylogenetic networks, e.g., for computing consensus- or super-trees. Recently, a fast algorithm for computing LSAs has been proposed.

The aim of this thesis is to compare the practical performance of this algorithm with simpler approaches to this problem. For this, you will have to implement the algorithms in Java or C++, run them on typical phylogenetic networks (as they arise in computational biology), and measure their performance. Promising results are likely to be integrated into our software Splitstree4.

This thesis will be supervised by the Huson lab (Uni Tuebingen). Please contact Johannes Fischer for further information.