斯坦福大学-遗传生物信息课程-2009 lecture3.pptVIP

* * * * * * * * * * * * * * * * * Indexing-based local alignment Dictionary: All words of length k (~10) Alignment initiated between words of alignment score ? T (typically T = k) Alignment: Ungapped extensions until score below statistical threshold Output: All local alignments with score statistical threshold …… …… query DB query scan Indexing-based local alignment—Extensions A C G A A G T A A G G T C C A G T C T G A T C C T G G A T T G C G A Gapped extensions until threshold Extensions with gaps until score C below best score so far Output: GTAAGGTCCAGT GTTAGGTC-AGT Sensitivity-Speed Tradeoff long words (k = 15) short words (k = 7) Sensitivity ? Speed ? Kent WJ, Genome Research 2002 Sens. Speed X% Sensitivity-Speed Tradeoff Methods to improve sensitivity/speed Using pairs of words Using inexact words Patterns—non consecutive positions ……ATAACGGACGACTGATTACACTGATTCTTAC…… ……GGCACGGACCAGTGACTACTCTGATTCCCAG…… ……ATAACGGACGACTGATTACACTGATTCTTAC…… ……GGCGCCGACGAGTGATTACACAGATTGCCAG…… TTTGATTACACAGAT T G TT CAC G Measured improvement Kent WJ, Genome Research 2002 Non-consecutive words—Patterns Patterns increase the likelihood of at least one match within a long conserved region 3 common 5 common 7 common Consecutive Positions Non-Consecutive Positions 6 common On a 100-long 70% conserved region: Consecutive Non-consecutive Expected # hits: 1.07 0.97 Prob[at least one hit]: 0.30 0.47 Advantage of Patterns 11 positions 11 positions 10 positions Multiple patterns K patterns Takes K times longer to scan Patterns can complement one another Computational problem: Given: a model (prob distribution) for homology between two regions Find: best set of K patterns that maximizes Prob(at least one match) TTTGATTACACAGAT T G TT CAC G T G T C CAG TTGATT A G Buhler et al. RECOMB 2003 Sun Buhler RECOMB 2004 How long does it take to search the query? Variants of BLAS