Improved Algorithmic Complexity for the 3SEQ Recombination Detection Algorithm.
Improved Algorithmic Complexity for the 3SEQ Recombination Detection Algorithm.
复制标题
DOI：
10.1093/molbev/msx263
复制
发表时间：
2018-01-01
影响因子：
10.7
通讯作者：
Boni MF
中科院分区：
文献类型：
--
作者：
Lam HM;Ratmann O;Boni MF
在大型基因组数据库时代识别重组序列是具有挑战性的，因为它需要有效的算法来识别候选重组体和亲本，以及适当的统计方法来校正进行的大量比较。在2007年，引入了一种精确的非参数镶嵌统计的计算，该统计为推定的重组体提供了高精度的P值。这种精确的计算意味着多重比较校正的P值也具有高精度，这在大型数据库中执行数百万或数十亿次测试时至关重要。在这里，我们介绍了一个改进的算法复杂度的计算从O（mn3）到O（mn2），其中m和n是在候选重组的重组信息位点的数量。这种新的计算允许重组分析与数以千计的多态性位点进行比对。基准运行的病毒基因组序列比对，新功能的介绍，并讨论了重组分析以外的应用。
Identifying recombinant sequences in an era of large genomic databases is challenging as it requires an efficient algorithm to identify candidate recombinants and parents, as well as appropriate statistical methods to correct for the large number of comparisons performed. In 2007, a computation was introduced for an exact nonparametric mosaicism statistic that gave high-precision P values for putative recombinants. This exact computation meant that multiple-comparisons corrected P values also had high precision, which is crucial when performing millions or billions of tests in large databases. Here, we introduce an improvement to the algorithmic complexity of this computation from O(mn3) to O(mn2), where m and n are the numbers of recombination-informative sites in the candidate recombinant. This new computation allows for recombination analysis to be performed in alignments with thousands of polymorphic sites. Benchmark runs are presented on viral genome sequence alignments, new features are introduced, and applications outside recombination analysis are discussed.
登录
查看更多内容
影响因子：
3.7
作者：
Wikramaratna PS;Simmons CP;Gupta S;Recker M
通讯作者：
Recker M
影响因子：
3.8
作者：
Faye O;Freire CC;Iamarino A;Faye O;de Oliveira JV;Diallo M;Zanotto PM;Sall AA
通讯作者：
Sall AA
影响因子：
5.3
作者：
Dudas G;Rambaut A
通讯作者：
Rambaut A
影响因子：
13.2
作者：
Zhu Z;Chan JF;Tee KM;Choi GK;Lau SK;Woo PC;Tse H;Yuen KY
通讯作者：
Yuen KY
影响因子：
3.8
作者：
Uzcategui, NY;Camacho, D;Gould, EA
通讯作者：
Gould, EA