权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Randomised algorithms and approximation in phylogenetics

系统发育学中的随机算法和近似

基本信息

批准号：
EP/D063574/1
负责人：
Magnus Bordewich
金额：
$ 26.89万
依托单位：
Durham University
依托单位国家：
英国
项目类别：
Fellowship
财政年份：
2006
资助国家：
英国
起止时间：
2006 至无数据
项目状态：
已结题

来源：
https://gtr.ukri.org/projects?ref=EP%2FD063574%2F1
关键词：
Randomised algorithms approximation phylogenetics

项目摘要

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.

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