Columba

Columba performs efficient approximate pattern matching in genomic sequences using search schemes to identify occurrences under edit distance constraints.

Key Features:

• Dynamic Partitioning Algorithm: Implements a dynamic partitioning algorithm that partitions search patterns to reduce the search space across search schemes.
• Implementation in C++: Implemented in C++ for computational performance and integration with bioinformatics workflows.
• Multiple Search Schemes: Supports multiple search schemes to flexibly enumerate all approximate occurrences of a pattern in a text.
• Memory Optimization Techniques: Employs memory interleaving techniques for Burrows-Wheeler transform representations to enhance data processing efficiency.
• Redundancy Reduction: Applies redundancy reduction methods for the edit distance metric to minimize unnecessary computations.

Scientific Applications:

• Variant identification: Identifying genetic variants by approximate matching of sequencing reads to reference genomes.
• Sequencing data analysis: Analyzing sequencing data including Illumina reads and their reverse complements for approximate matches.
• High-throughput retrieval: Retrieving all occurrences of 100,000 Illumina reads and their reverse complements within a maximum edit distance of four in the human genome on a single CPU core in under three minutes.
• Large-scale approximate matching: Handling large genomic datasets for high-throughput approximate pattern matching applications.

Methodology:

Uses search schemes combined with dynamic partitioning algorithms, memory interleaving for Burrows-Wheeler transform representations, and redundancy reduction techniques for the edit distance metric.