Efficient Estimation of Evolutionary Distances

Fabian Klötzl


The advent of high throughput sequencers has lead to a dramatic increase in the size of available genomic data. Standard methods, which have worked well for many years, are not suitable for the analysis of big data sets, due to their reliance on a time-consuming alignment step. In this thesis, a new alignment-free approach for phylogeny reconstruction is introduced. The corresponding program, andi, is orders of magnitude faster than classical approaches and also superior to comparable alignment-free methods. The central data structure in andi is the enhanced suffix array. It is used to find long exact matches between sequences. In this thesis, various approaches to the construction of enhanced suffix arrays, including novel ones, are evaluated with respect to performance. Additionally, a new parallel algorithm for the computation of suffix arrays is introduced.
Original languageEnglish
QualificationMaster of Science
Awarding Institution
  • Haubold, Bernhard , Supervisor, External person
  • Tantau, Till , Supervisor, External person
Publication statusPublished - 2015


Dive into the research topics of 'Efficient Estimation of Evolutionary Distances'. Together they form a unique fingerprint.

Cite this