资源描述：
《Scribe资讯博二 F88526030 叶正圣.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、SuffixTreesInstructor:Hsueh-ILuScribe:資訊博二F88526030葉正聖資訊大四B87506019黃友正資訊大四B87506029李建鴻10/17/2001AlgorithmsforBioinformaticsExactStringMatchingProblemINPUT:PandTOUTPUT:alloccurrencesofPinTTIME:O(
2、P
3、+
4、T
5、)TRICK:FundamentalPreprocessing(PatternandText)(lineartime)PTZZ[
6、P
7、+
8、i]>=
9、P
10、PoccursinT[i..i+
11、P
12、-1]10/17/2001AlgorithmsforBioinformaticsExactStringMatchingProblemQ1:CanwesolvetheprobleminO(
13、T
14、)timeifweknowPinadvance?Q2:CanwesolvetheprobleminO(
15、P
16、)timeifweknowTinadvance?ByFundamentalPreprocessing?Byanyalgorithm?10/17/2001AlgorithmsforBio
17、informaticsQuestion1Q1:CanwesolvetheprobleminO(
18、T
19、)timeifweknowPinadvance?事先知道Pattern,也可preprocessing,能否只用O(
20、T
21、)時間做完?觀察1:P的長度可能有關Ans:Yes.(A)做弊版:O(
22、P
23、+
24、T
25、)=O(
26、T
27、))(B)正確版:FundamentalProcessing,當成做P的z-value繼續做10/17/2001AlgorithmsforBioinformaticsQuestion2Q2:Canwesolvethep
28、robleminO(
29、P
30、)timeifweknowTinadvance?ByFundamentalPreprocessing?Byanyalgorithms?Ans:做弊版:P全1,T全1,Output就要O(
31、T
32、)時間(全部output)另一個argument:Input/Output時間不能算另一個argument:超強preprocessing,ex.神奇HashTable,神奇字典,etc.(雖然preprocessing可能要exponentialtime,不管的話)10/17/2001AlgorithmsforBio
33、informatics再問另一個問題問題改成只找出SubTree的一個output或回答Yes/No(output變小了!)再問一次,答案是:Q1還是可以,因為緊錮咒消失了Q2就不知道了,FundamentalProcessingorch2-ch4各種algorithm,不知道在不存在Suffix-tree可在linear-time建出來,powerful!10/17/2001AlgorithmsforBioinformaticsSuffixTreesInput:P,TOutput:anoccurrenceofPinT,ifany“
34、NO”ifPdoesnotoccurinTEXECTSTRINGMATCHINGSUBSTRINGPROBLEM10/17/2001AlgorithmsforBioinformaticsSuffixTreesChapter5:IntroductionChapter6:ConstructionAlgorithmsChapter7:AplicationsChapter8:LeastCommonAncestorChapter9:MoreApplicaitons10/17/2001AlgorithmsforBioinformaticsSub
35、stringMatchingStringS:bbabbaab(
36、S
37、=m)PatternP:baa(
38、P
39、=n)Objective:在S中找PTechniques:透過prepropessing建立有用的資料結構PreprocessingPO(n)timeBoyer-MooreO(m)timeKnuth-Merris-ProttO(m)timePreprocessingSO(m)timeSuffix-tree-matchingO(n)time!!10/17/2001AlgorithmsforBioinformaticsSuffixe
40、s與StringMatchingS=bbabbaab1stsuffix=bbabbaab2ndsuffix=babbaab3rdsuffix=abbaab4thsuffix=bbaab5thsuffix=baab6thsuffix=a
