Sequence Database
Searching
Dr. Zoya Khalid
[Link]@[Link]
What is database searching?
• Goal: find similar (homologous) sequences of a query sequence in a
sequence of database
• Input: query sequence & database
• Output: hits (pairwise alignments)
Basics of database searching
• Core: pairwise alignment algorithm
• Speed (fast sequence comparison)
• Relevance of the search results (statistical tests)
• Recovering all information of interest
• The results depend of the search parameters like gap penalty, scoring matrix.
• Specificity (TN/N) and sensitivity (TP/P)
What program to use for searching?
• FASTA
• more sensitive for DNA-DNA comparisons
• FASTX and TFASTX can find similarities in sequences with frameshifts
• BLAST
• fastest and easily accessed on the Web
• A suite; BLASTP, BLASTN, BLASTX
FASTA
• Derived from logic of the dot plot
• compute best diagonals from all frames of alignment
• Word method looks for exact matches between
words in query and test sequence
• hash tables
• DNA words are usually 6 bases
• protein words are 1 or 2 amino acids
• only searches for diagonals in region of word matches
= faster searching
FASTA
• after all diagonals found, tries to join diagonals by adding gaps
• computes alignments in regions of best diagonals
• Dynamic Programming
BLAST
Basic Local Alignment Search Tool
• An important goal of genomics is to determine if a particular
sequence is like another sequence.
• This is accomplished by comparing the new sequence with sequences
that have already been reported and stored in a database.
• This process is principally one that uses alignment procedures to
uncover the “like” sequence in the database.
BLAST
• The BLAST is a set of algorithms that attempt to find a short fragment of a
query sequence that aligns perfectly with a fragment of a subject sequence
found in a database.
• That initial alignment must be greater than a neighborhood score threshold
(T). For the original BLAST algorithm, the fragment is then used as a seed to
extend the alignment in both directions.
• The alignment is extended in both directions until the T score for the
aligned segment does not continue to increase.
• Said another way, BLAST looks for short sequences in the query that
matches short sequences found in the database.
The Blast Search Algorithm
1. Sequence (query) is broken into words of length W
2. Align all words with sequences in the database
3. Calculate score T using a substitution matrix
4. Discard words whose T value is below a neighborhood score
threshold
5. Extend words in both directions until score falls by dropoff value X
when compared to previous best score
BLAST Statistics
E-Value :
• The Expect value (E) is a parameter that describes the number of hits one
can "expect" to see by chance when searching a database of a particular
size.
• It decreases exponentially as the Score (S) of the match increases.
Essentially, the E value describes the random background noise.
• For example, an E value of 1 assigned to a hit can be interpreted as
meaning that in a database of the current size one might expect to see 1
match with a similar score simply by chance.
• The lower the E-value, or the closer it is to zero, the more "significant" the
match is
BLAST Statistics
Scores (bits)
• The bit score, S', is derived from the raw alignment score, S, taking
the statistical properties of the scoring system into account.
• Because bit scores are normalized with respect to the scoring system,
they can be used to compare alignment scores from different
searches.
Interpretation of BLAST hits
• very low E values (e-100) are homologs
• moderate E values are related genes
• long list of gradually declining of E values indicates a large gene family
• long regions of moderate similarity are more significant than short
regions of high identity
Threshold Value T
• The proper value for T depends on both the values in the scoring matrix and
the balance between speed and sensitivity.
• Higher values of T progressively remove more word hits and reduce the
search space.
• This makes BLAST run faster, but increases the chance of missing an
alignment.
• Word size (W) is another variable that controls the number of word hits. It's
easy to see why a word size of 1 will produce more hits than a word size of
10.
• In general, if T is scaled uniformly with W, smaller word sizes increase
sensitivity and decrease speed. The interplay between W, T, and the scoring
matrix is critical, and choosing them wisely is the most effective way to
control the speed and sensitivity of BLAST
Threshold T
PSI- BLAST
• Position-Specific Iterative (PSI)-BLAST is a protein sequence profile
search method that builds off the alignments generated by a run of
the BLASTp program.
• The first iteration of a PSI-BLAST search is identical to a run of BLASTp
program .
• It then generates a multiple alignment of the highest scoring pairs of
the BLASTp run above a certain preset score or e-value threshold and
calculates a profile or a position-specific score matrix (PSSM) from the
multiple alignment.
• The PSSM captures the conservation pattern in alignment and stores
it as a matrix of scores for each position in the alignment-highly
conserved positions receive high scores and weakly conserved
positions receive scores near zero.
• This profile is used in place of the original substitution matrix for a
further search of the database to detect sequences that match the
conservation pattern specified by the PSSM.
• The newly detected sequences from this second round of the search,
which are above the specified score (e-value) threshold are again
added to alignment the profile is refined for another round of
searching.
• This process is iteratively continued until desired or until
convergence, i.e., the state where no new sequences are detected
above the defined threshold.
• The iterative profile generation process makes PSI-BLAST far more
capable of detecting distant sequence similarities than a single query
alone in BLASTp, because it combines the underlying conservation
information from a range of related sequence into a single score
matrix.
• In the evolution, three-dimensional (3D) structures of proteins may
be conserved even after considerable erosion of their sequence
similarity.
• PSI-BLAST has been demonstrated to be useful in detecting such
relationships via sequence searches, which were previously only
detected through direct comparison of the 3D structures