生物资讯相关演算法Algorithms in Bioinformatics概要课件

生物資訊相關演算法

AlgorithmsinBioinformatics呂學一(中央研究院資訊科學所).tw/~hil/2003/12/161AlgorithmsinBioinformatics,Lecture11生物資訊相關演算法

AlgorithmsinBioinfFinalexam&

FinalpresentationWhentohaveourfinalexam?12/30,20031/6,20041/13,2004Deadlineforfinalpresentation1/20,2004.2003/12/162AlgorithmsinBioinformatics,Lecture11Finalexam&

FinalpresentatiTodayShortestsuperstringproblemIntermissionVotingforthedateoffinalexam小巨’smagic:“final”.2003/12/163AlgorithmsinBioinformatics,Lecture11TodayShortestsuperstringprobSuperstring11001011101isasuperstringof0101110011011111012003/12/164AlgorithmsinBioinformatics,Lecture11Superstring1100101110ShortestSuperstringInput:kstringsA1,A2,…,Ak.Output:ashorteststringthatcontainseachAiasasubstring.MotivationSequencingbyshotgunmethodsDatacompression2003/12/165AlgorithmsinBioinformatics,Lecture11ShortestSuperstringInput:200HardnessoftheproblemNP-completeness[Maier+Storer,1977]MAX-SNP-complete[Blum+Jiang+Li+Tromp+Yannakakis,STOC1991andJACM1994].2003/12/166AlgorithmsinBioinformatics,Lecture11HardnessoftheproblemNP-compApproximability3:[Blum,Jiang,Li,Tromp,Yannakakis,STOC’91]2+8/9:[Teng,Yao,STOC’93]2+5/6:[Czumajetal.,SWAT’94]2+50/63:[Kosarju,Park,Stein,FOCS’94]2+3/4:[Armen,Stein,WADS’95]2+2/3:[Armen,Stein,CPM’96]2.596:[Breslaurev,Jiang,Jiang,JALG’97]2.5:[Sweedyk,Ph.D.Thesis1995,SICOMP’99]2003/12/167AlgorithmsinBioinformatics,Lecture11Approximability3:[Blum,JiangTodayA4-approximationforShortestSuperstringProblem2003/12/168AlgorithmsinBioinformatics,Lecture11TodayA4-approximationforShoAnaturalassumptionForanytwodistinctindicesiandjbetween1andk,AiisnotasubstringofAj.Why?Otherwise,Aicanberemovedfromtheinputsetwithoutaffectingthesolution.2003/12/169AlgorithmsinBioinformatics,Lecture11AnaturalassumptionForanytwTherefore,…IfSisasuperstringoftwodistinctinputstringsAiandAj,thenAiandAj

cannotoccuratthesamepositionofS.AiAjS2003/12/1610AlgorithmsinBioinformatics,Lecture11Therefore,…IfSisasuperstrNotation頭(i,j)and疊(i,j).AjAiThetightestwaytooverlapAiandAj.2003/12/1611AlgorithmsinBioinformatics,Lecture11Notation頭(i,j)and疊(i,j).LiningupasetofinputstringsLet排(i1,i2,…,id)betheconcatenation 頭(i1,i2)頭(i2,i3)…頭(id-1,id)Aid.Ai1Ai2Aid排(i1,i2,…,id)2003/12/1612AlgorithmsinBioinformatics,Lecture11Liningupasetofinputstrin隊長定理|排(i1,i2,…,id)|=A1到Ad的總長扣掉所有相鄰兩個字串的重疊長度之和.Ai1Ai2Aid排(i1,i2,…,id)2003/12/1613AlgorithmsinBioinformatics,Lecture11隊長定理|排(i1,i2,…,id)|=A1到AdAnobservationThereisapermutationΠ*over{1,2,…,k}suchthat排(Π*)isashortestsuperstringofA1,A2,…,Ak.2003/12/1614AlgorithmsinBioinformatics,Lecture11AnobservationThereisapermuProofLetS*beashortestsuperstringofA1,A2,…,Ak.Were-indexA1,A2,…,Aksuchthat現(1)<現(2)<…<現(k),where現(i)istheleftmostoccurrenceofAiinS*.A1A2AkAiS*2003/12/1615AlgorithmsinBioinformatics,Lecture11ProofLetS*beashortestsupeClaim:|排(1,2,…,k)|=|S*|“≤”:S*showsawaytolineupA1,A2,…,Akinorder,althoughitisnotnecessarilythemost“compact”waytodothat.“≥”:排(1,2,…,k)isasuperstringofA1,A2,…,Ak,andS*isashortestone.2003/12/1616AlgorithmsinBioinformatics,Lecture11Claim:|排(1,2,…,k)|=|S*|“≤”:24-approximationbyshortestcoveringcyclicstrings2003/12/1617AlgorithmsinBioinformatics,Lecture114-approximationbyshortestcoCyclicstringIfSisastring,let環(S)denotethecyclicstringobtainedfromSby頭尾相接.Comment:EvenifRandSaretwodistinctstrings,環(R)=環(S)isstillpossible,e.g.,環(bbabbaab)=環(abbaabbb).bbabbaab2003/12/1618AlgorithmsinBioinformatics,Lecture11CyclicstringIfSisastring,馴服字串(coveringcyclicstring)IfAiisasubstringofSSS…,thenwesay環(S)isa馴服字串(coveringcyclicstring)ofAi.Denoted:Ai

環(S).Forexample,0101環(10)11001環(1001)10111環(1101)1101環(10100100101)2003/12/1619AlgorithmsinBioinformatics,Lecture11馴服字串(coveringcyclicstring)IfCommentsForanyAiand環(S)withAi環(S),both|Ai|≥|環(S)|and|Ai|

≤|環(S)|arepossible.IfSisasuperstringofA1,A2,…,Ak,then環(S)isa馴服字串ofallinputstringsA1,A2,…,Ak,.However,wecanfindashortest馴服字串forallinputstringsA1,A2,…,Ak,inpolynomialtime.2003/12/1620AlgorithmsinBioinformatics,Lecture11CommentsForanyAiand環(S)wiObservationIfAi

環(S),thentheleftmostoccurrenceofAiinSSS…hastobeatmost|S|.SSSAiAi2003/12/1621AlgorithmsinBioinformatics,Lecture11ObservationIfAi環(S),then馴服術假設t個inputstringsAj1,…,Ajt,都被環(S)馴服,而且Aj1,…,Ajt在SSS…中的leftmostoccurrence也是按照Aj1,…,Ajt的順序由左到右排列.則|排(j1,j2,…,jt)|≤|S|+|Ajt|.2003/12/1622AlgorithmsinBioinformatics,Lecture11馴服術假設t個inputstringsAj1,…,AjWhy?SSSAjtAj2Aj1SAj32003/12/1623AlgorithmsinBioinformatics,Lecture11Why?SSSAjtAj2Aj1SAj32003/12/16重疊定理(待證)IfAjt

環(St)andAjt+1

環(St+1),thenwehave|疊(jt,jt+1)|<|St|+|St+1|.2003/12/1624AlgorithmsinBioinformatics,Lecture11重疊定理(待證)IfAjt環(St)andAj生物資訊相關演算法

AlgorithmsinBioinformatics呂學一(中央研究院資訊科學所).tw/~hil/2003/12/1625AlgorithmsinBioinformatics,Lecture11生物資訊相關演算法

AlgorithmsinBioinfFinalexam&

FinalpresentationWhentohaveourfinalexam?12/30,20031/6,20041/13,2004Deadlineforfinalpresentation1/20,2004.2003/12/1626AlgorithmsinBioinformatics,Lecture11Finalexam&

FinalpresentatiTodayShortestsuperstringproblemIntermissionVotingforthedateoffinalexam小巨’smagic:“final”.2003/12/1627AlgorithmsinBioinformatics,Lecture11TodayShortestsuperstringprobSuperstring11001011101isasuperstringof0101110011011111012003/12/1628AlgorithmsinBioinformatics,Lecture11Superstring1100101110ShortestSuperstringInput:kstringsA1,A2,…,Ak.Output:ashorteststringthatcontainseachAiasasubstring.MotivationSequencingbyshotgunmethodsDatacompression2003/12/1629AlgorithmsinBioinformatics,Lecture11ShortestSuperstringInput:200HardnessoftheproblemNP-completeness[Maier+Storer,1977]MAX-SNP-complete[Blum+Jiang+Li+Tromp+Yannakakis,STOC1991andJACM1994].2003/12/1630AlgorithmsinBioinformatics,Lecture11HardnessoftheproblemNP-compApproximability3:[Blum,Jiang,Li,Tromp,Yannakakis,STOC’91]2+8/9:[Teng,Yao,STOC’93]2+5/6:[Czumajetal.,SWAT’94]2+50/63:[Kosarju,Park,Stein,FOCS’94]2+3/4:[Armen,Stein,WADS’95]2+2/3:[Armen,Stein,CPM’96]2.596:[Breslaurev,Jiang,Jiang,JALG’97]2.5:[Sweedyk,Ph.D.Thesis1995,SICOMP’99]2003/12/1631AlgorithmsinBioinformatics,Lecture11Approximability3:[Blum,JiangTodayA4-approximationforShortestSuperstringProblem2003/12/1632AlgorithmsinBioinformatics,Lecture11TodayA4-approximationforShoAnaturalassumptionForanytwodistinctindicesiandjbetween1andk,AiisnotasubstringofAj.Why?Otherwise,Aicanberemovedfromtheinputsetwithoutaffectingthesolution.2003/12/1633AlgorithmsinBioinformatics,Lecture11AnaturalassumptionForanytwTherefore,…IfSisasuperstringoftwodistinctinputstringsAiandAj,thenAiandAj

cannotoccuratthesamepositionofS.AiAjS2003/12/1634AlgorithmsinBioinformatics,Lecture11Therefore,…IfSisasuperstrNotation頭(i,j)and疊(i,j).AjAiThetightestwaytooverlapAiandAj.2003/12/1635AlgorithmsinBioinformatics,Lecture11Notation頭(i,j)and疊(i,j).LiningupasetofinputstringsLet排(i1,i2,…,id)betheconcatenation 頭(i1,i2)頭(i2,i3)…頭(id-1,id)Aid.Ai1Ai2Aid排(i1,i2,…,id)2003/12/1636AlgorithmsinBioinformatics,Lecture11Liningupasetofinputstrin隊長定理|排(i1,i2,…,id)|=A1到Ad的總長扣掉所有相鄰兩個字串的重疊長度之和.Ai1Ai2Aid排(i1,i2,…,id)2003/12/1637AlgorithmsinBioinformatics,Lecture11隊長定理|排(i1,i2,…,id)|=A1到AdAnobservationThereisapermutationΠ*over{1,2,…,k}suchthat排(Π*)isashortestsuperstringofA1,A2,…,Ak.2003/12/1638AlgorithmsinBioinformatics,Lecture11AnobservationThereisapermuProofLetS*beashortestsuperstringofA1,A2,…,Ak.Were-indexA1,A2,…,Aksuchthat現(1)<現(2)<…<現(k),where現(i)istheleftmostoccurrenceofAiinS*.A1A2AkAiS*2003/12/1639AlgorithmsinBioinformatics,Lecture11ProofLetS*beashortestsupeClaim:|排(1,2,…,k)|=|S*|“≤”:S*showsawaytolineupA1,A2,…,Akinorder,althoughitisnotnecessarilythemost“compact”waytodothat.“≥”:排(1,2,…,k)isasuperstringofA1,A2,…,Ak,andS*isashortestone.2003/12/1640AlgorithmsinBioinformatics,Lecture11Claim:|排(1,2,…,k)|=|S*|“≤”:24-approximationbyshortestcoveringcyclicstrings2003/12/1641AlgorithmsinBioinformatics,Lecture114-approximationbyshortestcoCyclicstringIfSisastring,let環(S)denotethecyclicstringobtainedfromSby頭尾相接.Comment:EvenifRandSaretwodistinctstrings,環(R)=環(S)isstillpossible,e.g.,環(bbabbaab)=環(abbaabbb).bbabbaab2003/12/1642AlgorithmsinBioinformatics,Lecture11CyclicstringIfSisastring,馴服字串(coveringcyclicstring)IfAiisasubstringofSSS…,thenwesay環(S)isa馴服字串(coveringcyclicstring)ofAi.Denoted:Ai

環(S).Forexample,0101環(10)11001環(1001)10111環(1101)1101環(10100100101)2003/12/1643AlgorithmsinBioinformatics,Lecture11馴服字串(coveringcyclicstring)IfCommentsForanyAiand環(S)withAi環(S),both|A