生物资讯相关演算法.ppt_第1页
生物资讯相关演算法.ppt_第2页
生物资讯相关演算法.ppt_第3页
生物资讯相关演算法.ppt_第4页
生物资讯相关演算法.ppt_第5页
已阅读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. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论