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

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

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.