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

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

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.