PGT

PGT identifies motifs and ungapped local alignments in multimegabase DNA sequences using locality-sensitive hashing to enable discovery and annotation of conserved genomic features.

Key Features:

• Efficient Local Alignment Detection: PGT employs the LSH-ALL-PAIRS (Locality-Sensitive Hashing - All Pairs) algorithm to find ungapped local alignments in large genomic sequences.
• Locality-Sensitive Hashing (Randomized Search): The tool uses locality-sensitive hashing as a randomized search technique to improve efficiency and sensitivity when processing long sequences.
• Sensitivity to Divergent Alignments: PGT can identify alignments with as little as 63% identity in mammalian genomic sequences up to tens of megabases and tolerates up to a specified fraction of substitutions.
• Balancing Efficiency and Sensitivity: The approach optimizes detection of short exact matches that are rare in background sequences yet indicative of significant similarities.
• Customizable Alignment Parameters: Users can specify alignment length and substitution rate to tailor searches for different analysis goals.

Scientific Applications:

• Comparative Genomics: Detecting local alignments with substitutions to identify conserved elements across species or strains.
• Annotation of Conserved Features: Facilitating annotation of genomic regions that are evolutionarily conserved through motif and alignment discovery.
• Evolutionary and Functional Genomics: Supporting studies of evolutionary relationships and functional elements by identifying significant sequence similarities in large genomes.

Methodology:

The LSH-ALL-PAIRS algorithm applies locality-sensitive hashing as a randomized search to detect ungapped local alignments in long, multimegabase DNA sequences, with user-settable alignment length and substitution-rate parameters and reported sensitivity to ~63% identity in mammalian sequences up to tens of megabases.