Algorithms to distinguish the role of gene-conversion from single-crossover recombination in the derivation of SNP sequences in populations.
Algorithms to distinguish the role of gene-conversion from single-crossover recombination in the derivation of SNP sequences in populations.
复制标题
区分基因转换和单交换重组在群体 SNP 序列推导中的作用的算法。
DOI：
10.1089/cmb.2007.0096
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
Wu,Yufeng
中科院分区：
文献类型：
--
作者：
Song,YunS;Ding,Zhihong;Gusfield,Dan;Langley,CharlesH;Wu,Yufeng
减数分裂重组是一个基本的生物事件，也是造成物种内遗传变异的主要进化力量之一。除了其基本作用之外，重组还是几个关键应用问题的核心。最重要的例子是人群中的“关联图谱”，人们普遍希望它能帮助找到影响遗传疾病的基因（Carlson et al., 2004; Clark, 2003）。因此，最近的大量注意力集中在当突变和重组都发生时推断群体中序列的历史推导的问题上。在算法文献中，最近的大部分工作都是针对单交叉重组。然而，基因转换是一种重要且更常见的（两次交叉）重组形式，在算法文献中对其进行的研究要少得多。在本文中，我们明确地将基因转换纳入离散方法中以研究历史重组。我们关注的是用于识别和定位历史交叉和基因转换（以及单核苷酸突变）程度的算法，以及构建这些事件的完整推定历史的问题。新颖的技术问题涉及将基因转换纳入最近开发的离散方法（Myers 和 Griffiths，2003；Song 等人，2005），该方法计算无需基因转换的所需重组量的下限和上限信息。我们首先检查 Myers 和 Griffiths (2003) 的下界方法的最自然扩展，表明可以有效地计算扩展，但这种扩展只能产生弱下界。然后，我们提出了导致更高下界的其他想法，并展示了如何通过整数线性规划解决下界问题的更符合生物学现实的版本。我们还展示了如何计算所需单交换和基因转换数量的有效上限，以及显示突变、单交换和基因转换的假定历史的显式网络。下界方法和上限方法都可以处理缺失条目的数据，并且上限方法可以用于高精度地推断缺失条目。我们通过证明这些方法可以有效地用于区分未经基因转换生成的模拟衍生序列与通过基因转换生成的序列来验证这些方法的重要性。我们将这些方法应用于最近研究的拟南芥序列，识别出序列中比以前识别出的更多区域（Plagnol 等人，2006），其中基因转换可能发挥了重要作用。演示软件可在 www.csif.cs.ucdavis.edu/∼gusfield 获取。
Meiotic recombination is a fundamental biological event and one of the principal evolutionary forces responsible for shaping genetic variation within species. In addition to its fundamental role, recombination is central to several critical applied problems. The most important example is “association mapping” in populations, which is widely hoped to help find genes that influence genetic diseases (Carlson et al., 2004; Clark, 2003). Hence, a great deal of recent attention has focused on problems of inferring the historical derivation of sequences in populations when both mutations and recombinations have occurred. In the algorithms literature, most of that recent work has been directed to single-crossover recombination. However,gene-conversionis an important, and more common, form of (two-crossover) recombination which has been much less investigated in the algorithms literature. In this paper, we explicitly incorporate gene-conversion into discrete methods to study historical recombination. We are concerned with algorithms for identifying and locating the extent of historical crossing-over and gene-conversion (along with single-nucleotide mutation), and problems of constructing full putative histories of those events. The novel technical issues concern the incorporation of gene-conversion into recently developed discrete methods (Myers and Griffiths, 2003; Song et al., 2005) that computelowerandupper-boundinformation on the amount of needed recombination without gene-conversion. We first examine the most natural extension of the lower bound methods from Myers and Griffiths (2003), showing that the extension can be computed efficiently, but that this extension can only yield weak lower bounds. We then develop additional ideas that lead to higher lower bounds, and show how to solve, via integer-linear programming, a more biologically realistic version of the lower bound problem. We also show how to compute effective upper bounds on the number of needed single-crossovers and gene-conversions, along with explicit networks showing a putative history of mutations, single-crossovers and gene-conversions. Both lower and upper bound methods can handle data with missing entries, and the upper bound method can be used to infer missing entries with high accuracy. We validate the significance of these methods by showing that they can be effectively used to distinguish simulation-derived sequences generated without gene-conversion from sequences that were generated with gene-conversion. We apply the methods to recently studied sequences ofArabidopsis thaliana, identifying many more regions in the sequences than were previously identified (Plagnol et al., 2006), where gene-conversion may have played a significant role. Demonstration software is available atwww.csif.cs.ucdavis.edu/∼gusfield.