Randomised algorithms and approximation in phylogenetics

算法和计算复杂性是决定计算机科学中哪些问题我们可以或不能希望在合理的时间内解决的基本问题的核心。近年来，在快速发展的生物信息学和计算生物学领域，这一点得到了最明显的强调。以合理的成本收集大量基因数据的技术的出现，使人们有希望了解生物学中的许多深层次问题。然而，回答这些问题中哪些是可解的，哪些将被证明是NP难的问题属于理论计算机科学领域，这意味着不可能有效地计算出准确的解。系统发育学是根据遗传特征重建和分析系统发育(进化)树和网络。在进化生物学中，系统发育树被用来表示一系列现代物种的祖先历史。自1837年查尔斯·达尔文第一次描绘进化树以来，创造这样一棵“生命树”一直是系统生物学的主要目标，现在也是全球学术努力的焦点。系统发育学在突变疾病的研究中也被证明是重要的；最近重建HIV系统发展史的工作有助于追踪疾病的起源。这个项目的广泛目标是开发算法和随机近似方案，这将有益于在系统发生学领域工作的生物学家，以及设计分析这种算法的新技术，这将是理论计算机科学中的独立兴趣。

Algorithms and computational complexity lie at the heart of the fundamental question of determining which problems in computer science we can or cannot hope to solve in a reasonable amount of time. In recent years this has been nowhere highlighted more clearly than in the rapidly developing areas of bio-informatics and computational biology. The advent of techniques for gathering huge volumes of genetic data at a reasonable cost has lead to hopes of understanding many deep problems in biology. However, it lies in the sphere of theoretical computer science to answer the question of which of these problems will be solvable, and which will turn out to be NP-hard, which would suggest it is impossible to compute an exact solution efficiently. Phylogenetics is the reconstruction and analysis of phylogenetic (evolutionary) trees and networks based on inherited characteristics. In evolutionary biology, phylogenetic trees are used to represent the ancestral history of a collection of present-day species. Creating a such a ``tree of life'' has been a primary goal of systematic biology since Charles Darwin's first sketch of an evolutionary tree in 1837, and is now the focus of a global academic effort. Phylogenetics has also proved to be important in the study of mutating diseases; recent work reconstructing the phylogeny of HIV has helped trace the origins of the disease.The broad aim of this project is to develop algorithms and randomised approximation schemes which will be beneficial to biologists working in the field of phylogenetics, as well as devising new techniques for analysing such algorithms, which will be of independent interest in theoretical computer science.