PatternHunter faster and more sensitive homology search.ppt

PatternHunter: faster and more sensitive homology search By Bin Ma, John Tromp and Ming Li Agenda PatternHunter Spaced Seed Algorithm Performance PatternHunter II Algorithm Performance Translated PatternHunter PatternHunter – Spaced Seed Outline A short review about BLAST. Some definition and background. What’s the difference and the same between BLAST and PatternHunter. Why PatternHunter is better?? Nonconsecutive seeds Proof Blast Algorithm Find seeded matches Extent to HSP’s (High scoring Segment Pairs) Gapped Extension, dynamic programming Report significant local alignments A short review about BLAST Find hits. BLAST first scans the database for words that score at least T when aligned with some word within the query sequence. Any aligned word pair satisfying this condition is called a hit. A short review about BLAST Find HSPs HSP (High scoring Segment Pair) is much longer than a single word pair, and may therefore entail multiple hits on the same diagonal within a relative shot distance of one another. A short review about BLAST Generate gapped alignment This means that two or more HSPs in BLAST with scores well below 38 bits can, in combination, rise to statistical significance. If any one of these HSPs is missed, so may be the combined result. A short review about BLAST In summary, the new gapped BLAST algorithm requires two non-overlapping hits of score at least T, within a distance A of one another, to invoke an ungapped extension of the second hit. If the HSP generated normalized score at least Sg bits, then a gapped extension is triggered. Some definition, some background Similarity How similar it is between two sequences? Usually mean that the probability of the same symbol appear in anywhere of two sequences. Sensitivity The probability to find a local alignment. Specificity In all local alignments, how many alignments are homologous. Define the Seed Defining the seed: w - weight or number of positions to match Blastn: 11 MegaBlast: 28 model