III: Medium: Collaborative Research: Scalable Kinship Inference in Wild Populations Across Years and Generations

在野生种群中跨年份和世代的可扩展的亲属关系推断分子生态学研究的基石是家庭群体的重建（亲属关系分析）。了解自由生活种群中的个体如何相互关联，为研究许多重要的生物过程提供了最佳的可能性，从性选择到扩散和招募的模式。分子DNA技术和计算方法的最新进展使这些研究成为可能。然而，许多概念和计算上的挑战仍然存在，需要加以解决，以推进这些研究。迄今为止，现有的亲属关系分析的研究工作主要集中在计算方法，解决一个单一的关系，如亲子关系分配或重建全同胞群体。包括多个目标，例如具有最小亲子关系分配的半同胞重建，或多代的层次结构，使得基础计算问题的公式化极具挑战性，并且先前方法的简单扩展不能以实用的，可扩展的，该方法以一种鲁棒的方式解决了包括多代物种或涉及多个优化函数的数据集的亲缘关系重建问题。本研究的目标是设计一种稳健、简洁、通用的计算方法，用于从多等位基因标记推断野生种群中的多代亲缘关系。简约假设是这些方法的基础，因为它不需要先验知识，关于抽样方法的假设，或模型的存在，这是大多数自由生活人群的情况。该项目的不同任务包括基于现有的生物学研究制定计算亲缘关系推理问题，分析计算复杂性并为所产生的组合优化问题提供解决方案，以及设计鲁棒的，可扩展的和高效的高性能实现。由此产生的计算方法将在从现有生物学研究中收集的数据集上进行评估，并将通过Kinalyzer基于网络的服务部署到生物界，目前仅用于亲缘关系推断。该项目中提出的研究将极大地影响不同的应用领域，包括组合优化和数据挖掘的基础研究，以及生物学中的行为生态学等不同领域，进化遗传学、保护、法医学和流行病学。该项目的多学科性质和研究团队将加强相关领域的课程设计，并引入新的跨学科课程。这一具有凝聚力的多学科项目将在一个单一的应用框架内提供生物学、运筹学、算法分析、生物信息学和高性能计算方面的培训机会。该项目将利用团队的多样化科学专业知识和广泛的指导经验，促进真正的跨学科合作，并为新一代跨学科科学家提供蓬勃发展的环境。

Scalable kinship inference in wild populations across years and generationsA cornerstone of research in molecular ecology is the reconstruction of family groups (kinship analysis).Understanding how individuals in free-living populations are related to each other provides the bestopportunity to study many important biological processes, ranging from sexual selection to patternsof dispersal and recruitment. Recent advances in molecular DNA technologies and computationalmethods have made these studies possible. However, many conceptual and computational challengesremain and need to be addressed in order to advance these studies. To date, existing research workon kinship analysis has primarily focused on computational methods that address a single relationship, such as parentage assignment or reconstruction of full sib groups. Inclusion of multiple objectives, such as half-sib reconstruction with minimum parentage assignment, or hierarchy over multiple generations, makes formulation of the underlying computational problem extremely challenging, and simple extensions of previous methods do not address in a practical, scalable, and robust manner the problem of kinship reconstruction for data sets that include multiple generations of species or involve multiple optimization functions.The goal of the proposed research is to design robust, parsimonious, and versatile computationalapproaches for inferring multi-generation kinship relationships in wild populations from multiallelicmarkers. Parsimony assumption is fundamental to these approaches as it requires no prior knowledge,assumptions about sampling methodology, or existence of models, which is the case for most free-livingpopulations. The diverse tasks of this project include formulating computational kinship inferenceproblems based on existing biological studies, analyzing computational complexity of and providingsolutions to the resulting combinatorial optimization problems, and designing robust, scalable andefficient high performance implementations. The resulting computational methods will be evaluatedon datasets collected from existing biological studies and will be deployed to the biological communitythrough the Kinalyzer web-based service, currently actively used for sibship inference only.The research proposed in this project will greatly impact diverse application areas including funda-mental research in combinatorial optimization and data mining, and within biology, areas as diverse asbehavioral ecology, evolutionary genetics, conservation, forensics, and epidemiology. The multidisci-plinary nature of the project and the research team will enhance curriculum design of related areas andintroduce new cross-disciplinary courses. This cohesive, multidisciplinary project will provide trainingopportunities in biology, operation research, algorithms analysis, bioinformatics and high performancecomputing, within a single application framework. The project will leverage the diverse scientific ex-pertise and extensive mentoring experience of the team to foster a true interdisciplinary collaborationand to provide a thriving environment for a new generation of interdisciplinary scientists.