Large-scale methods for multiple sequence alignment and phylogeny estimation

Bioinformatic analyses generally involve passing genetic sequence data through a pipeline of transformations. These prominently include multiple sequence alignment (MSA) and phylogeny estimation, which are both core challenges in computational biology. Their established mathematical formulations are usually difficult NP-hard problems that are attacked with careful and laborious heuristics. Consequently, the most accurate methods tend to be the most computationally expensive with increasing dataset size, and this limits the analysis to datasets of only modest volume. Larger datasets are becoming increasingly available and require qualitatively different approaches. In this thesis, we consider divide-and-conquer frameworks that employ slow-but-accurate base methods to efficiently solve the problem piecewise. The continued development of accurate and efficient large-scale methods will, it is hoped, facilitate more effective bioinformatic analysis of larger and larger datasets