ScoringMatrix[SeqA[i]][SeqB[j]]

SHRiMP:AccurateMappingofShortReadsinLetter-andColour-spacesStephenRumble,PhilLacroute,…,ArendSidow,MichaelBrudnoHowSHRiMPworks:Stage1:MapreadstotargetgenomeStage2:ComputestatisticsReadMappingThreephasesVeryfastk-merscan(indexreads,scangenome)Fast,vectorizedSmith-WatermantoconfirmSlow,completebacktrackingS-Wfortop‘n’hitsReadMapping:Phase1Createahashtableofsize4^(k-merlength)4bases–ignoreallelse(‘N’,‘X’,wobblecodes…)Thisbecomesourkmertoreadindex…AACTGTACCAGTGAGReadMapping:Phase1Createahashtableofsize4^(k-merlength)4bases–ignoreallelse(‘N’,‘X’,wobblecodes…)Thisbecomesourkmertoreadindex…AACTGTaccagtgagAACTGTReadMapping:Phase1Createahashtableofsize4^(k-merlength)4bases–ignoreallelse(‘N’,‘X’,wobblecodes…)Thisbecomesourkmertoreadindex…aACTGTAccagtgagAACTGTACTGTAReadMapping:Phase1Createanindexofsize4(k-merlength)4bases–ignoreallelse(‘N’,‘X’,wobblecodes…)Thisisourk-mertoreadindex…aaCTGTACcagtgagAACTGTACTGTACTGTACReadMapping:Phase1Createahashtableofsize4^(k-merlength)4bases–ignoreallelse(‘N’,‘X’,wobblecodes…)Thisbecomesourkmertoreadindex…accTGTACCagtgagAACTGTACTGTACTGTACTGTACCReadMapping:Phase1Createahashtableofsize4^(k-merlength)4bases–ignoreallelse(‘N’,‘X’,wobblecodes…)Thisbecomesourkmertoreadindex…AACTGTACTGTACTGTACTGTACCRead7Read32Read18Read12Read13Read12Read7Read15ReadMapping:Phase1Oncewe’veindexedallreads,justscanthegenomebyk-merGenomeReadsReadMapping:Phase1Rememberthek-merhitswithinagiveninterval(window)Whensufficienthits,lookmoreclosely“Lookmoreclosely”meanscalculateafastSmith-WatermanscoreTechnicalitiesWedon’talwaysusefullk-mers(q-grams).Weactuallysupport‘spacedseeds’,butthealgorithmdoesn’tchangemuch.Foreachspacedseed,‘compressout’thek-meranduseitasthehashindexReadMapping:Phase2Smith-WatermanisveryexpensiveNxMmatrixisn’ttoobigforshortreadsandwindows,but…WecallthevectorizedcodemillionsoftimesWedon’twantabottleneck–aimfornomorethan50%ofthetotalruntimeWeonlywantonescoreasquicklyaspossibleReadMapping:Phase2CellbeingcomputedPreviouslycomputedcellsACTAGACTTGTCCAGTMi,jmaxMi1,j1S(Ai1,Bj1)Mi1,jgapMi,j1gapReadMapping:Phase2Eachforward-facingdiagonalinS-Wmatrixdependson:Smallconstant#ofpreviousdiagonalsSmallconstant#ofscalarsWecancomputeentirediagonalsinparallelOurspeed-upisproportionaltothediagonalsizeReadMapping:Phase2+---+CurrentPreviousPenultimateACTAGACTTGTCCAGTACTAGACTTGTGACCT+---+ReadMapping:Phase2MostcommodityprocessorshavevectorinstructionsRemembertheMMXbrouhaha?SIMD–SingleInstruction,MultipleData41287291536212310+=ReadMapping:Phase2+---+CurrentPreviousPenultimateACTAGACTTGTCCAGTACTAGACTTGTGACCT+---+ReadMapping:Phase2MatchscorestypicallyuseascoringmatrixScoringMatrix[SeqA[i]][SeqB[j]]Butthisdoesn’tscale:IndividualcellscoresbecomeabottleneckCanprecomputea‘queryprofile’(expensive),or…Ifweonlycareaboutstrictmatch/mismatchwecanuselogicalbit-wiseoperationsSIMDinstructionsworkhere(fullyparallel)ReadMapping:Phase2Results:OurvectorizedS-Wisasfast,orfasterthanotherverycomplicatedSIMDimplementations500million+matrixcells/secondonCore2machinesEvenwithsmallseeds,S-WaccountsforatmosthalfofthetotalruntimeReadMapping:Phase3Recap:K-merscanselectsareasofreasonablesimilarityVectorizedS-W(dis)confirmssimilarityBest‘n’hitsperreadaregivenafullalignmentwithbacktraceReadMapping:Phase3Letter-spacealignmentsaresimple:K-merscan,VectorizedS-W,FullS-Winletters,giveuserprettyoutputWhataboutABSOLiDcolour-space?BiologistswanttoseeA,C,G,T,not0,1,2,3…DealingwithstrangeSOLiDproperties…Oursolution:K-merscan,VectorizedS-Wincolour-spaceFullS-Winletter-space,butwecan’tjustconvertABDi-baseReadsWethinkintermsofnucleotides:A,C,G,andT’s.AB’sNGSmachineoutputs4coloursOnecolourperpairofbases:TTGAGCGTTCT0122331020123T1032G2301C3210ATGCAABDi-baseReadsAGCT00001122330123T1032G2301C3210ATGCASOLiDTranslationsGiventhefollowingread,thereare4translations(weneedaninitialbase):012233102AACTCGCAAGCCAGATACCTGGTCTATGGATTGAGCGTTCSOLiDTranslationsReadsbeginwithaknownprimer(‘T’)012233102AACTCGCAAGCCAGATACCTGGTCTATGGATTGAGCGTTCSOLiDTranslationsWhathappensifareaderroroccurs?Therighttranslationwas:TTGAGCGTTC010233102AACCTATGGACCAAGCGTTCGGTTCGCAAGTTGGATACCTColour-spaceSmith-WatermanTherearefouruniquetranslationsforeveryreadAnerrorwillcauseustochangeframes(differenttranslation)WhynotdoaS-Wacrossallfourletter-spacetranslationswithsomeerrorpenalty?Colour-spaceSmith-WatermanThinkof4S-WmatricesstackedaboveoneanotherIfwehave1readerror,butotherwiseperfectmatch,we’lluse2matricesGenomeReadFrame1Frame2Frame3Frame4Colour-spaceSmith-WatermanEndresult:G:1123724TA-ACCACGGTCACACTTGCATCAC1123701|||||||||||||||X|||||||T:TACACCACGGTCAGACTtGCATCACR:0T031110113012122121131321124Shouldbe‘0’StatisticsAfterreadsaremapped,mullovertheresultsForeachread:P(hitbypurechance–notavalidhit)P(hitgeneratedbygenome–validhit)P(hitisbestofallforparticularread)ResultsSpeedSimplek-merscanisveryfastImportantwhenseedsarebigger(lessS-W)VectorizedS-WisfastImportantwhenseedsaresmaller(moreS-W)Generallywell-