Stinus-BLAST.pdf

(305 KB) Pobierz
BLAST, gapped BLAST and PSI-BLAST
1
Overview
•
•
•
•
•
Quick repetition of pairwise alignment
Statistical fundament of BLAST
The basic BLAST algorithm
Gapped BLAST
PSI-BLAST
2
Pairwise alignment
• Global alignment
– Needleman-Wunsch
• Local Alignment
– Smith-Waterman
• Dynamic programming, fill out matrix
• Find optimal solution
• Time complexity:
O(mn)
3
BLAST
•
•
•
•
•
Heuristic method
Fast search through large databases
Good but not necessarily best solution
Skip explicit search of the entire matrix
Extensions:
– Faster
– Include gaps
– Use position-specific scoring matrices
4
Statistical fundament
Recall random walks and extreme value
distributions
Assumption: Independet background
distribution of amino acids,
P
i
s
ij
denote the score of aligning AAs
i
and
j
The
expected score
must be negative
∑
PP s
i
i
,
j
j ij
<
0
(cf. random walks – else drift to infinity)
5

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin