ProbeMatch

ProbeMatch performs gapped and ungapped alignments of oligonucleotide sequences against genome databases to identify sequence matches that include insertions, deletions, and mismatches.

Key Features:

• Gapped and ungapped alignments: Supports both ungapped and gapped alignments allowing up to three errors per alignment, including insertions, deletions, and mismatches, unlike ELAND which performs ungapped alignments with a maximum of two mismatches.
• Gapped q-grams and patterned q-grams: Employs gapped q-grams and various patterned q-grams to efficiently identify candidate target hits and reduce the number of sequences requiring full examination while maintaining sensitivity.
• Performance and scalability: Demonstrated aligning 169,095 Illumina GAII reads against the human genome in under three hours, finding alignments for 28,625 reads, a task reported as not achievable with ELAND.

Scientific Applications:

• Genome Mapping: Mapping sequencing reads from high-throughput platforms such as Illumina GAII to reference genomes for assembly and annotation tasks.
• Variant Detection: Identifying genetic variants that involve insertions and deletions as well as mismatches.
• Comparative Genomics: Comparing genomic sequences across species by accommodating indels and mismatches more effectively than tools limited to ungapped alignments.

Methodology:

ProbeMatch uses gapped q-grams and patterned q-grams to narrow candidate alignments and performs gapped and ungapped alignments against genome databases allowing up to three errors (insertions, deletions, mismatches).