| Comparative approaches are fundamental to analyzing genomic sequence data, and therefore touch almost all aspects of bioinformatics research. The core tasks of sequence alignment, phylogenetic inference, and ancestral sequence reconstruction must be performed as accurately as possible in order for their results to be useful. Due to the difficult combinatorial nature of these problems, as well as the necessary assumptions made by the models upon which they are based, even the best methods to solve them will make errors. These errors will impact and potentially bias any downstream analysis performed on sequence data. The overall objective of my thesis is to explore algorithmic techniques to quantify sources of error in comparative sequence analysis, and ensure that they are minimized. This work is divided into three results: (1) a novel context-sensitive indel model for more accurate sequence alignment, (2) an algorithm to efficiently compute the expected error of ancestral sequence reconstruction, and (3) an approximation algorithm with tight error bound guarantees for an application of phylogenetic analysis that arises in conservation biology. |
