Related Experiment Video
Updated: Feb 20, 2026

Rare Event Detection Using Error-corrected DNA and RNA Sequencing
Published on: August 3, 2018
Improved Algorithmic Complexity for the 3SEQ Recombination Detection Algorithm
Ha Minh Lam1,2, Oliver Ratmann3, Maciej F Boni1,2,4
1Wellcome Trust Major Overseas Programme, Oxford University Clinical Research Unit, Ho Chi Minh City, Vietnam.
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.
Related Concept Videos
Next-generation Sequencing
Next-Generation Sequencing Methods
Although all next-generation methods use different technologies, they all share a set of standard features....
Conservative Site-specific Recombination and Phase Variation
The recognition sites for Cre recombinase called LoxP...
RNA-seq
Before the discovery of RNA-seq, microarray-based methods and Sanger sequencing were used for transcriptome analysis. However, while...
Maxam-Gilbert Sequencing
Challenges of the Maxam-Gilbert Method
The...
Sanger Sequencing

