Computational Aspects of Inferring Evolutionary History

Jesper Jansson
June, 1999
Licentiate Thesis in Computer Science

Abstract

This Licentiate thesis consists of an introduction and three articles related to computational biology. The main theme is combinatorial problems involving evolutionary trees.

The first problem considered, the maximum homeomorphic agreement subtree problem (MHT), amounts to comparing different evolutionary trees for a fixed set of species and identifying a subtree common to all of them. The next problem, the maximum inferred consensus tree problem (MICT), suggests a topological method for tree construction; a few variants of MICT are also studied. Finally, in the Hamming center problem (HCP), we want to find an unbiased representation for a set of strings of equal length. HCP is a special case of a problem in which all internal nodes of a given evolutionary tree have to be labeled.

In the first article included in the thesis, we present some new results on the inapproximability of MHT and the computational complexity of MICT. The second article deals with a variant of MICT in which a left-right ordering is imposed upon the species. The third article contains a randomized approximation algorithm for HCP.

Compressed PostScript version (309965 bytes).

A printed version of the thesis can be obtained from:

Technical Reports Librarian

Department of Computer Science

Lund University

Box 118

SE-221 00 Lund

Sweden

E-mail: Anne-Marie.Westerberg@cs.lth.se

Back