Improved algorithmic complexity for the 3SEQ recombination detection algorithm
File(s)
Published version
Author(s)
Ratmann, O
Ha Minh Lam
Boni, MF
Type
Journal Article
Abstract
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.
Date Issued
2017-10-03
Date Acceptance
2017-09-28
Citation
Molecular Biology and Evolution, 2017, 35 (1), pp.247-251
ISSN
1537-1719
Publisher
Oxford University Press (OUP)
Start Page
247
End Page
251
Journal / Book Title
Molecular Biology and Evolution
Volume
35
Issue
1
Copyright Statement
© The Author(s) 2017. Published by Oxford University Press on behalf of the Society for Molecular Biology and Evolution.
This is an Open Access article distributed under the terms of the Creative Commons Attribution Non-Commercial License
(http://creativecommons.org/licenses/by-nc/4.0/), which permits non-commercial re-use, distribution, and reproduction in any medium,
provided the original work is properly cited. For commercial re-use, please contact journals.permissions@oup.com
This is an Open Access article distributed under the terms of the Creative Commons Attribution Non-Commercial License
(http://creativecommons.org/licenses/by-nc/4.0/), which permits non-commercial re-use, distribution, and reproduction in any medium,
provided the original work is properly cited. For commercial re-use, please contact journals.permissions@oup.com
License URL
Sponsor
Medical Research Council (MRC)
Bill & Melinda Gates Foundation
Grant Number
MR/K010174/1B
GCAEN 511473
Subjects
mosaic structure
nonparametric
recombination
0604 Genetics
0603 Evolutionary Biology
0601 Biochemistry And Cell Biology
Evolutionary Biology
Publication Status
Published
Date Publish Online
2017-10-03