Related Experiment Video
Updated: Aug 12, 2025

Rare Event Detection Using Error-corrected DNA and RNA Sequencing
Published on: August 3, 2018
How to optimally sample a sequence for rapid analysis
Martin C Frith1,2,3, Jim Shaw4, John L Spouge5
1Artificial Intelligence Research Center, AIST, Tokyo 135-0064, Japan.
Motivation:
We face an increasing flood of genetic sequence data, from diverse sources, requiring rapid computational analysis. Rapid analysis can be achieved by sampling a subset of positions in each sequence. Previous sequence-sampling methods, such as minimizers, syncmers and minimally overlapping words, were developed by heuristic intuition, and are not optimal.
Results:
We present a sequence-sampling approach that provably optimizes sensitivity for a whole class of sequence comparison methods, for randomly evolving sequences. It is likely near-optimal for a wide range of alignment-based and alignment-free analyses. For real biological DNA, it increases specificity by avoiding simple repeats. Our approach generalizes universal hitting sets (which guarantee to sample a sequence at least once) and polar sets (which guarantee to sample a sequence at most once). This helps us understand how to do rapid sequence analysis as accurately as possible.
Availability And Implementation:
Source code is freely available at https://gitlab.com/mcfrith/noverlap.
Supplementary Information:
Supplementary data are available at Bioinformatics online.
Related Concept Videos
RNA-seq
Before the discovery of RNA-seq, microarray-based methods and Sanger sequencing were used for transcriptome analysis. However, while...
Sanger Sequencing
Next-generation Sequencing
Next-Generation Sequencing Methods
Although all next-generation methods use different technologies, they all share a set of standard features....
DNA Isolation

