III-CXT-Medium: Collaborative Research: Inference of Complex Genealogical Histories in Populations: Algorithms and Applications

III-CXT-Medium：协作研究：群体中复杂谱系历史的推断：算法和应用

• 批准号: 0803440
• 负责人: Yufeng Wu
• 金额: $ 30.52万
• 依托单位: University of Connecticut
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2008
• 资助国家: 美国
• 起止时间: 2008-09-01 至 2012-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0803440&HistoricalAwards=false
• 关键词: III; CXT; Medium; Collaborative; Research

The genomes of individuals alive today are derived from some common ancestor(s) by the actions of mutations and meiotic recombinations. Recombination mixes two homologous chromosomes in an individual to produce a third recombinant, mosaic chromosome, consisting of alternating segments of the two homologs. A recombinant chromosome is then passed on to a child of the individual. Therefore, the derivation of genomes in a current population, from some ancestral genome(s), cannot be represented by a tree, but rather must be represented by a directed acyclic graph, called a Phylogenetic Network or Genealogical Network, or Ancestral Recombination Graph (ARG). Explicitly knowing the historically correct genealogical network that derived extant genomes, or knowing critical features of the network, would greatly facilitate the solution of fundamental problems in biology, and has important practical applications, for example in association mapping in populations, a technique to find genes affecting diseases and important economic traits. However, since we cannot directly examine the past, we must computationally deduce a genealogical network, or features of it, from genomes that we can examine in populations today. The development of algorithms for such computation requires significant interaction of ideas from biology, computer science, graph-theory, mathematics, and algorithm and software engineering. This interdisciplinary project, conducted by computer scientists in collaboration with a population geneticist, is focused on developing efficient algorithms to infer and exploit complex genealogical histories under a variety of biological models of the evolution of genomic sequences and of genetic traits, using different types of existing and emerging biological data. These algorithms will be implemented in software that can be used to study fundamental biological questions, and applied to practical problems such as association mapping of complex traits. The central thesis of the project is that explicit genealogical networks can be efficiently computed, and that these networks capture enough of the true history (even if the networks don?t capture all of it) to allow researchers to more effectively answer fundamental biological questions, and more effectively solve practical biological problems. The project also addresses fundamentally new algorithmic problems and biological applications, driven by new kinds of population variation data that are becoming available, new areas of biology where population data is becoming available, new biological models that have been recently proposed for the evolution of sequences and genetic traits in populations, new understanding of different genomic variations that affect important traits, and biological controversies and questions about the nature (and even the existence) of recombination, and about its role in other biological phenomena. This work will contribute to algorithmic computer science and also to several areas of biology, particularly population genetics. The algorithms and software that will be developed will allow biologists to deduce complex genealogical histories, to better understand the role of recombination, and to address both fundamental biological problems and applied practical problems. The software will be disseminated on the web, along with slides and videos of lectures on the algorithms underlying the software. The project will allow the joint mentoring of graduate students and post-doctoral researchers by advisers from both computer science and biology. The participation of researchers from both computer science and biology makes the research more visible to their respective communities, encouraging other interdisciplinary research.

今天活着的个体的基因组是由一些共同的祖先(S)通过突变和减数分裂重组的作用而产生的。重组将两条同源染色体混合在一个个体中，产生第三条重组的马赛克染色体，由两条同源染色体的交替片段组成。然后，重组的染色体被传递给该个体的孩子。因此，当前种群中的基因组从某个祖先基因组(S)派生出来的过程不能用树来表示，而必须用一个有向无环图来表示，称为系统发生网络或遗传网络，或祖先重组图。明确了解派生现存基因组的历史上正确的系谱网络，或了解该网络的关键特征，将极大地促进生物学基本问题的解决，并具有重要的实际应用，例如在种群关联图谱中，这是一种寻找影响疾病和重要经济性状的基因的技术。然而，由于我们不能直接研究过去，我们必须通过计算从我们今天可以在种群中研究的基因组中推断出一个谱系网络或其特征。这种计算算法的发展需要生物学、计算机科学、图论、数学以及算法和软件工程的思想的重大互动。这一跨学科项目由计算机科学家与一名人口遗传学家合作进行，重点是开发有效的算法，利用不同类型的现有和新兴生物数据，在基因组序列和遗传特征进化的各种生物学模型下推断和利用复杂的系谱历史。这些算法将在可用于研究基本生物学问题的软件中实现，并应用于实际问题，如复杂性状的关联图谱。该项目的中心论题是，显式的系谱网络可以被有效地计算，并且这些网络能够捕获足够的真实历史(即使网络不能捕获全部历史)，以允许研究人员更有效地回答基本的生物学问题，并更有效地解决实际的生物学问题。该项目还从根本上解决了新的算法问题和生物学应用，其驱动因素是：正在获得的新类型的种群变异数据，正在获得种群数据的新的生物学领域，最近为种群中的序列和遗传特征的进化提出的新的生物学模型，对影响重要特征的不同基因组变异的新理解，以及关于重组的性质(甚至存在)及其在其他生物现象中的作用的生物学争议和问题。这项工作将有助于算法计算机科学，也有助于生物学的几个领域，特别是种群遗传学。将开发的算法和软件将使生物学家能够推断复杂的系谱历史，更好地理解重组的作用，并解决基本的生物学问题和实际应用问题。该软件将在网络上传播，以及关于该软件背后算法的幻灯片和讲座视频。该项目将允许由来自计算机科学和生物学的顾问共同指导研究生和博士后研究人员。来自计算机科学和生物学的研究人员的参与使这项研究对各自的社区更具可见性，从而鼓励其他跨学科研究。