Improved algorithmic complexity for the 3SEQ recombination detection algorithm

File Description SizeFormat 
msx263.pdfPublished version205.83 kBAdobe PDFView/Open
Title: Improved algorithmic complexity for the 3SEQ recombination detection algorithm
Authors: Ratmann, O
Ha Minh Lam
Boni, MF
Item 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.
Issue Date: 3-Oct-2017
Date of Acceptance: 28-Sep-2017
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 (, 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
Sponsor/Funder: Medical Research Council (MRC)
Bill & Melinda Gates Foundation
Funder's Grant Number: MR/K010174/1B
GCAEN 511473
Keywords: mosaic structure
0604 Genetics
0603 Evolutionary Biology
0601 Biochemistry And Cell Biology
Evolutionary Biology
Publication Status: Published
Appears in Collections:Mathematics
Faculty of Natural Sciences

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

Creative Commonsx