Sequence Database Searching and BLAST Algorithms

Vocabulary practice flashcards covering sequence similarity searches, BLAST programs and parameters, heuristics, gap penalty models, and Karlin-Altschul alignment statistics.

Homolog Search

The computational process of scanning a sequence database to identify homologs, potentially distant homologs, or sequences similar to a given query sequence.

Smith-Waterman Algorithm

An optimal local sequence alignment algorithm that performs an exhaustive brute-force search; while computationally ideal for finding optimal alignments, it is too slow for large sequence databases.

Heuristic Database Search

A search approach that implements computational shortcuts and approximations to achieve high speed at the cost of potential errors, creating a trade-off between accuracy and speed.

BLAST (Basic Local Alignment Search Tool)

A heuristic algorithm designed to identify regions of local similarity between biological sequences and compute the statistical significance of matches.

FASTA

A sequence comparison tool that is generally slower than BLAST but can be more sensitive for detecting distantly related DNA sequences with conserved functional homology.

Word Size (K-tuple)

The predetermined length of short exact or high-scoring sequence seeds used by BLAST to initiate alignments; decreasing word size increases sensitivity but decreases search speed.

Threshold Parameter ($T$)

A score cutoff used in BLAST to identify the 'neighborhood' of a query word using substitution matrices; words with scores meeting or exceeding $T$ are evaluated for database hits.

High-Scoring Pair (HSP)

An alignment segment between two sequences formed by extending initial word hits in both directions until the alignment score drops below a predetermined drop-off value.

Drop-off Value

A defined numerical parameter indicating how much an alignment score can fall below the current maximum during word extension before extension terminates.

BLASTN

A member of the BLAST family that queries a nucleotide database using a nucleotide query sequence.

BLASTP

A member of the BLAST family that queries a protein database using a protein query sequence.

BLASTX

A BLAST program that translates a nucleotide query sequence into six potential reading frames to query a protein database.

TBLASTN

A BLAST program that searches a six-frame translated nucleotide database using a protein query sequence.

TBLASTX

A BLAST program that translates a nucleotide query into protein to search against a translated nucleotide database across all six reading frames.

PSI-BLAST (Position-Specific Iterated BLAST)

A program that executes a BLASTP search, generates a multiple alignment, builds a Position-Specific Scoring Matrix (PSSM), and iteratively uses this matrix to find distant homologs.

PHI-BLAST (Pattern-Hit Initiated BLAST)

A BLAST variant that takes a user-specified search pattern or motif and identifies protein sequences that match the query and contain the exact pattern.

MEGA-BLAST

A nucleotide BLAST program optimized by default to rapidly find highly similar sequences using larger word sizes (defaulting to $28$ on NCBI).

Discontinuous MEGA-BLAST

A nucleotide BLAST algorithm variation that allows non-contiguous seed matches to search for more dissimilar sequences.

Expect Value ($E$-value)

An estimate of the number of alignments with a score equal to or greater than $S$ expected to arise by chance alone, calculated as $E = Kmn\,e^{-\lambda S}$.

BLAST Probability ($P$-value)

The theoretical probability of observing a database match score greater than or equal to a given value by chance alone, calculated from the Expect value as $P = 1 - e^{-E}$.

Karlin-Altschul Statistics

The statistical theory establishing that maximum scores of ungapped local sequence alignments between unrelated sequences follow an extreme value distribution.

Low Complexity Region

A sequence segment with repetitive or biased nucleotide or amino acid composition, rendered in lowercase when masked, which is filtered out so it does not distort alignment statistics.

ClusteredNR

A protein database where sequences sharing at least $90\%$ sequence identity and $90\%$ sequence length are clustered into a single entity to diversify search results.

Linear Gap Cost

A gap scoring scheme where penalty costs scale strictly by gap length with an opening penalty of zero ($\text{open} = 0$), used by default in Megablast for computational speed.

Query Cover

The percentage of the query sequence length that aligns to and is covered by the matching database hit.

Raw Score

The direct sum of scoring matrix values for matches and penalties for mismatches and gaps along an alignment.

Bit Score

A normalized score derived from the raw score that accounts for the scoring matrix and search space parameters ($K$ and $\lambda$), permitting comparisons between different searches.