已阅读5页,还剩48页未读, 继续免费阅读
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
2003/10/21,AlgorithmsinBioinformatics,Lecture5,1,生物資訊相關演算法AlgorithmsinBioinformatics,呂學一(中央研究院資訊科學所).tw/hil/,2003/10/21,AlgorithmsinBioinformatics,Lecture5,2,Today,ApplicationsofsuffixtreesSubstringproblem(暖身)“Exactstringmatching”revisitedLinearizationofcircularstring(挪移乾坤)Longestcommonsubstring(異中求同)Intermission小巨smagicshowTheLureofQueen(皇后的魅惑),2003/10/21,AlgorithmsinBioinformatics,Lecture5,3,ApplicationOne,SubstringProblem(recapasawarm-up),2003/10/21,AlgorithmsinBioinformatics,Lecture5,4,SubstringProblem,Input:twostringsPandS,whereSisallowedtobepreprocessedinO(|S|)time.Output:anoccurrenceofPinS.Objective:doneinO(|P|)time.,2003/10/21,AlgorithmsinBioinformatics,Lecture5,5,12345678S=bbabbaab,1,1,3,1,1,2,3,1,2,7,2,3,4,7,1,4,1,7,3,3,4,1,3,3,2003/10/21,AlgorithmsinBioinformatics,Lecture5,6,12345678S=bbabbaab,1,1,7,2,3,4,7,4,7,3,3,4,3,3,Q:Whereareabba,baa,bb?,2003/10/21,AlgorithmsinBioinformatics,Lecture5,7,12345678S=bbabbaab,1,2,1,1,3,4,7,2,3,4,5,7,4,6,7,3,3,4,3,3,3,2,1,1,Q:Whereareabba,baa,bb?,2003/10/21,AlgorithmsinBioinformatics,Lecture5,8,ApplicationTwo,ExactStringMatching,2003/10/21,AlgorithmsinBioinformatics,Lecture5,9,ExactStringMatching,Input:twostringsPandS,whereSisallowedtobepreprocessedinO(|S|)time.Output:alloccurrencesofPinS.Challenge:solvingthisinO(|P|+k)time,wherekisthenumberofoccurrencesofPinS.,2003/10/21,AlgorithmsinBioinformatics,Lecture5,10,Idea,Eachinternalnodekeepsthelabelsofallitsdescendantleaves.,2003/10/21,AlgorithmsinBioinformatics,Lecture5,11,12345678S=bbabbaab,1,2,1,1,3,4,7,2,3,4,5,7,4,6,7,3,3,4,3,3,Q:Somethingsmissing?,6,3,5,2,4,1,5,2,4,1,Q:Howdowefixthisproblem?,2003/10/21,AlgorithmsinBioinformatics,Lecture5,12,123456789S=bbabbaab$,1,2,1,1,3,4,7,2,3,4,5,7,4,6,7,3,3,4,3,3,5,2,4,1,5,2,4,1,8,1,7,9,4,4,5,8,9,9,9,6,3,7,Q:ObtainableinO(|S|)time?,2003/10/21,AlgorithmsinBioinformatics,Lecture5,13,Perhapsnot,S=aaaaa$,1,6,5,4,3,2,1,2,3,4,5,1,2,3,4,1,2,3,1,2,2003/10/21,AlgorithmsinBioinformatics,Lecture5,14,Anobservation,ConsiderthesequenceLofleavesfromlefttoright.ThedescendantleavesofeachinternalnodehastobeconsecutiveinL.,2003/10/21,AlgorithmsinBioinformatics,Lecture5,15,123456789S=bbabbaab$,1,2,1,1,3,4,7,2,3,4,5,7,4,6,7,3,3,3,3,5,2,4,1,5,2,4,1,8,7,9,4,4,5,8,9,9,9,6,3,7,123456789L=637524189,1,3,4,8,4,5,6,7,2003/10/21,AlgorithmsinBioinformatics,Lecture5,16,ApplicationThree,CircularStringLinearization(挪移乾坤),2003/10/21,AlgorithmsinBioinformatics,Lecture5,17,Notation,Let挪(S,i)denotethestringSi|S|S1i1.,挪(S,i),2003/10/21,AlgorithmsinBioinformatics,Lecture5,18,Theproblem,InputastringS.Outputanindexithatmaximizesthealphabeticalorderof挪(S,i).,12345678挪(S,1)=bbabbaab挪(S,2)=babbaabb挪(S,3)=abbaabbb挪(S,4)=bbaabbba挪(S,5)=baabbbab挪(S,6)=aabbbabb挪(S,7)=abbbabba挪(S,8)=bbbabbaa,2003/10/21,AlgorithmsinBioinformatics,Lecture5,19,Navealgorithm,letj=1;fori=2to|S|doif(挪(S,i)挪(S,j)letj=i;outputj;,Timecomplexity?,2003/10/21,AlgorithmsinBioinformatics,Lecture5,20,Q:CanwebeatO(|S|2)?,12345678挪(S,1)=bbabbaab挪(S,2)=babbaabb挪(S,3)=abbaabbb挪(S,4)=bbaabbba挪(S,5)=baabbbab挪(S,6)=aabbbabb挪(S,7)=abbbabba挪(S,8)=bbbabbaa,2003/10/21,AlgorithmsinBioinformatics,Lecture5,21,Linear-TimeAlgorithmviaSuffixTree,2003/10/21,AlgorithmsinBioinformatics,Lecture5,22,Firstattemptgoingright,12345678bbabbaabbabbaababbaabbbaabbaabaababb,Q:Howtofixtheproblem?,2003/10/21,AlgorithmsinBioinformatics,Lecture5,23,SecondAttempt,SuffixtreeforSS,2003/10/21,AlgorithmsinBioinformatics,Lecture5,24,Keyobservation,Eachlength-|S|substringofSSisa挪(S,j)forsomeindexjwith1j|S|.Each挪(S,j)with1j|S|isalength-|S|substringofSS.,2003/10/21,AlgorithmsinBioinformatics,Lecture5,25,1234567890123456SS=bbabbaabbbabbaab,1,1,1,3,1,1,2,3,1,2,7,2,3,4,7,1,4,1,7,3,3,4,1,2,10,4,5,6,1,10,2,2,3,3,2,3,4,5,3,3,2003/10/21,AlgorithmsinBioinformatics,Lecture5,26,1,1,7,4,7,4,7,3,3,10,4,5,6,10,2,2,3,3,3,3,Q:Howtousethissuffixtree?,1234567890123456SS=bbabbaabbbabbaab,2003/10/21,AlgorithmsinBioinformatics,Lecture5,27,Equivalently,OutputtheindexisuchthatSSi|SS|correspondstotherightmostleafofthesuffixtreeforSS.Clearly,thistakesO(|S|)time.,2003/10/21,AlgorithmsinBioinformatics,Lecture5,28,ApplicationFour,Longestcommonsubstring(異中求同),2003/10/21,AlgorithmsinBioinformatics,Lecture5,29,Theproblem,Input:twostringsAandB.Output:alongeststringCthatoccursinbothAandB.,A=bbbabbaabB=baabbabbabC=bbC=baabC=abbaC=bbabba,2003/10/21,AlgorithmsinBioinformatics,Lecture5,30,Navealgorithm,buildsuffixtreeforB;forL=|A|downto1dofori=1to|A|-L+1doifAii+L-1occursinBoutputAii+L-1andhalt;output“nocommonsubstring”;,Timecomplexity?,2003/10/21,AlgorithmsinBioinformatics,Lecture5,31,O(|A|3+|B|),Thefor-looptakestime,Canwedobetterthanthis?,2003/10/21,AlgorithmsinBioinformatics,Lecture5,32,Afasteralgorithm,buildsuffixtreeforB;fori=1to|A|dofindthelargestintegerL(i)suchthatAii+L(i)-1occursinBbybinarysearch;outputAiL(i)fortheiwiththelargestL(i);,Timecomplexity?,2003/10/21,AlgorithmsinBioinformatics,Lecture5,33,O(|A|2log|A|+|B|),Thefor-looptakesO(|A|2log|A|)time.EachbinarysearchtakestimeO(|A|log|A|).ThereareoverallO(|A|)binarysearches.,Canwedobetterthanthis?,2003/10/21,AlgorithmsinBioinformatics,Lecture5,34,DonaldE.Knuthconjecturedin1970that,itisimpossibletosolvethislongestcommonsubstringprobleminO(|A|+|B|)time.,2003/10/21,AlgorithmsinBioinformatics,Lecture5,35,LongestCommonSubstring,inO(|A|+|B|)timeviasuffixtree,2003/10/21,AlgorithmsinBioinformatics,Lecture5,36,Idea,ConstructasuffixtreeTforA#B$,where#and$aretwocharactersnotinAandB.Thereareexactly|A|+|B|+2leavesinT,eachleafcorrespondstoasuffixofA#B$.A-leaf:withlabelin1,2,|A|correspondstoanA-suffix.B-leaf:withlabelin|A|+2,|A|+|B|+1correspondstoaB-suffix.,A-suffix,B-suffix,2003/10/21,AlgorithmsinBioinformatics,Lecture5,37,Observation,LetvbeanarbitrarypositionofT(i.e.,visnotnecessarilyanodeofT.)vhasadescendantA-leafifandonlyifvcorrespondstoaprefixofanA-suffixofA#B$.vhasadescendantB-leafifandonlyifvcorrespondstoaprefixofaB-suffixofA#B$.,root,v,2003/10/21,AlgorithmsinBioinformatics,Lecture5,38,Lemma,LetvbeapositionofT.vhasdescendantA-leafandB-suffixifandonlyifvcorrespondstoacommonsubstringofAandB.,root,v,2003/10/21,AlgorithmsinBioinformatics,Lecture5,39,Question,Dowereallyneed#toseparateAandBintheconcatenatedstringA#B$?,root,$,A,B,A-suffix,B-suffix,v,2003/10/21,AlgorithmsinBioinformatics,Lecture5,40,Thealgorithm,ConstructthesuffixtreeTofA#B$.OutputthestringcorrespondingtoadeepestinternalnodevsuchthatthesubtreeofTrootedatvcontainsbothA-leafandB-leaf.,Q:whynotcheckingleaves?Q:whynotcheckingpositionsofTthatarenotinternalnodesofT?,2003/10/21,AlgorithmsinBioinformatics,Lecture5,41,Itsufficestocheckinternalnodes,Ifthepositionvcontainsbothkindsofdescendantleaves,thensodoesitsclosestinternalnodebelow.,root,v,2003/10/21,AlgorithmsinBioinformatics,Lecture5,42,Time=O(|A|+|B|),O(|A|+|B|)timeforconstructingT.O(|A|+|B|)timeformarkingthecolorsofeachnode,includingeachleafandeachinternalnodesO(|A|+|B|)timeforcomputingthedepthsofallnodesO(|A|+|B|)timetofindadeepestinternalnodewithbothcolors.,2003/10/21,AlgorithmsinBioinformatics,Lecture5,43,SpaceComplexityisalsoO(|A|+|B|).,Q:Canwefurtherimprovethetimeandspacecomplexity?“No”forthetimecomplexity.“Yes”forthespacecomplexity.,2003/10/21,AlgorithmsinBioinformatics,Lecture5,44,ReducingthespacetoO(|A|),2003/10/21,AlgorithmsinBioinformatics,Lecture5,45,LongestCommonSubstring,Input:twostringsAandB.Output:alongeststringCthatoccursinbothAandB.Objective:O(|A|+|B|)timeO(|A|)spaceIdea:ConstructthesuffixtreeofAonly.,2003/10/21,AlgorithmsinBioinformatics,Lecture5,46,Thealgorithm,ConstructthesuffixtreeTofA,keepingallthesuffixlinks.Fori=1to|B|doFindthelargestinteger深(i)suchthatBii+深(i)1occursinB.OutputBii+深(i)1whereiistheindexwithmaximum深(i).,2003/10/21,AlgorithmsinBioinformatics,Lecture5,47,Navely,Finding深(i)foreachitakesO(深(i)+1)timebytraversingTfromtheroot.Butallthese|B|iterationswouldtakeO(|A|B|)timeintotal.,depth=深(i),2003/10/21,AlgorithmsinBioinformatics,Lecture5,48,Observation,深(i+1)深(i)1.,深(i),深(i)1,Whatifthissuffixlinkdoesnotexist?,2003/10/21,AlgorithmsinBioinformatics,Lecture5,49,1234567812345678901A=bbabbaabB=babaabbaaba,1,2,1,1,3,4,7,8,2,3,4,8,5,7,8,4,8,6,7,8,3,3,4,8,3,3,1,Record:深(1)=3,1,Record:深(3)=4,Record:深(5)=6,2003/10/21,AlgorithmsinBioinformatics,Lecture5,50,Timeandspace,Clearly,thespacecomplexityisO(|A|).ThetimecomplexitystillO(|A|+|B|).WefirstshowthatthetimeisO(|A|+
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 高一政治必修一“原始社会的解体和阶级社会的演进”教学设计
- 高中信息技术选修算法与程序设计双重循环教学设计
- 初中数学九年级下册反比例函数图象与性质复习教学设计
- 八年级物理 熔化与凝固 教学设计
- 初中物理八年级上册 1.1 声音是什么 教学设计
- 小学五年级班队活动教学设计《做自己的舵手-从被管教到自觉的成长》
- 初中八年级信息技术《改变图像大小和方向》教学设计
- 学期教学工作总结
- CN119538297A 一种基于客户端分组的联邦学习隐私保护方法 (安徽工业大学)
- CN119537506A 一种异步式服务化信息检索和索引管理方法及系统 (中国石油天然气股份有限公司)
- 东营港东营港区环抱港池内航道维护性疏浚工程环境影响报告书
- 熔化焊接与热切割培训课件
- 12J9-1 室外工程图集
- ReFi动态养老财务模型目标基准点及养老财务相关知识测试题附答案
- GB/T 29911-2025汽车租赁服务规范
- 河大版小学信息技术课件教学
- 贝壳租房合同协议
- T-CALC 007-2025 重症监护病房成人患者人文关怀规范
- 《农村既有居住建筑抗震鉴定与加固技术标准》
- ABBdcs组态课件CONDUCTORVMS操作
- DB43T 833-2016 前(后)置微耕机
评论
0/150
提交评论