Abstract
Phylogenetic placement determines possible phylogenetic origins of unknown query DNA or protein sequences, given a fixed reference phylogeny.Its main application is species identification, an essential bioinformatics problem with environmental ecology applications, microbial diversity studies, and medicine. Alignment-free methods for phylogenetic placement are a novel group of methods designed to eliminate the need to align query sequences within reference sequences --- a current limit to the applicability of phylogenetic placement methods in the next-generation sequencing (NGS) era.One of such methods is RAPPAS. It introduced the concept of phylogenetically aware k-mers (phylo-k-mers): k-mers paired with relevant probabilistic information about the reference phylogeny. This information determines how probable it is to observe any k-mer in hypothetical sequences arising from different parts of the reference tree. RAPPAS preprocesses the reference phylogenetic tree and alignment, computing phylo-k-mers. This allows fast phylogenetic placement of vast amounts of query sequences; however, the computation of phylo-k-mers is expensive in both running time and memory.This thesis studies the problem of effective indexing of reference phylogenies with phylo-k-mers. Chapter 1 gently introduces the reader to the problem. Starting with a historical overview of biology and bioinformatics of the last decades, it discusses the importance of sequence identification in modern bioinformatics, overwhelmed with amounts of sequencing data produced by NGS technologies. Then, it overviews existing methods of phylogenetic placement and discusses their limitations.Chapter 2 describes and analyzes the existing solution for the central algorithmic problem of phylo-k-mer computation: computing phylo-k-mers for one node in a k-sized window of the reference alignment. In addition, it describes a novel algorithm for this problem based on the divide-and-conquer approach. This algorithm improves the existing solution both theoretically and in practice.Chapter 3 proposes a novel method of filtering phylo-k-mers based on Mutual Information. This method allows reducing memory consumption of phylogenetic placement significantly with a negligible decrease in placement accuracy. It also describes how RAPPAS is connected to well-studied methods of text classification with Naive Bayes.Finally, Chapter 4 presents two new phylo-k-mer-related tools: XPAS for efficient computation of phylo-k-mers and RAPPAS2, an effective reimplementation of RAPPAS. Experimental results provided show that XPAS and RAPPAS2 outperform RAPPAS both in running speed and memory consumption. Both tools are written in modern C++, optimized for efficiency, and are ready to use.The final chapter discusses possible directions of future work on phylo-k-mer-related methods, the challenges that are yet to be overcome, and a discussion on the future of phylogenetic placement.