UNWORDS

UNWORDS computes the shortest DNA substrings (absent words) that do not occur within given DNA sequences to identify absent subsequences for genome analysis.

Key Features:

• Bit-vector encoding: Represents candidate strings using bit-vector encoding to streamline absent-word computations.
• Efficient algorithm: Implements a novel algorithm to compute shortest absent words more efficiently than prior methods.
• Parameter-free shortest-word detection: Computes shortest absent words directly without requiring a specified length estimate.
• Space optimization: Avoids index structures such as suffix trees and suffix arrays, reducing memory usage compared to traditional approaches.
• Scalability and performance: Scales to large genomes (e.g., human and mouse) and has been demonstrated on genomes of ~10^9 to ~10^5 base pairs, with reported runtime ~10 minutes for the human genome using ~2.5 MB of space.

Scientific Applications:

• Genome comparison: Identify unique absent subsequences to assess compositional uniqueness between organisms.
• Expression profiling: Use absent words as markers in expression profiling studies to aid interpretation of gene regulation and expression patterns.
• Genetic engineering: Guide design of synthetic genes or modifications by identifying sequences absent from natural genomes to avoid unintended overlaps.
• Pan-genomics and metagenomics: Enable comprehensive absent-word analysis across diverse and large-scale genomic datasets.

Methodology:

Uses a novel algorithm that leverages bit-vector encoding to compute shortest absent words while avoiding suffix trees and suffix arrays.