生物信息学中一个优化的全局双序列比对算法

:2003-09-10;:2003-12-23:(H02072003053021):(1974-),(),,,:.:1001-9081(2004)06Z-0307-02(,100083):Needleman2Wunsch,,,,:;;;:TP301.6:A1,,,,,Needleman2Wunsch[1],,,,,,,OGP,,2[2]DNA,DNA4,DNA4;20,20-,DNAATGCAGTC,,,:ATG-C;A-GTC,:;Si,j=max{Si-1,j-1+s(ai,bj),maxxE1(Si-x,j-wx),maxyE1(Si,j-y-wy)}1,(i,j):,i,j:i-1,j-1,;j,i,a=a1a2anb=b1b2bn,si,j=s(a1a2an,b1b2bn),si,jaibj,s(ai,bj)aibj,wxax,wyby,si,jsi,j,13UHFNeedleman2WunschD,O(mn),2(a)Hirschberg[3],,()():D()Bs,,checkpoint;checkpoint;checkpointO(m+n),Ukkonen[4],DU,U[ab,d],ab=a-bD,dD,U[ab,d]a,Dabab+1ab-1d-12(b)O(n+d2)(n2420046ComputerApplicationsVol.24June,2004©1994-2008ChinaAcademicJournalElectronicPublishingHouse.Allrightsreserved.),O(n2),Divide2and2Conquer[5]HirschbergUkkonen,HirschbergUkkonenD,i()i-1(),FA[6],checkpoint,checkpoint,2(d)UkkonenU,dd-1abab+1ab-1,U,2(c)Divide2and2ConquerUFAcheckpoint,2UHFUHFU,chekpoint,;U,UHF:1)U,,;2)Uk,Ukcheckpointkcheckpoint,;3)UHF,k,Hirschberg;4)checkpointUUkkonen:{U[ab,d]=maxas.t.D[a,b]=dwhereab=a-b=-infinityifnosuchaexists}U[0,0]=maxas.t.As[1..a]=Bx[1..a]U[ab,d]=-infinity,if|ab|d{Outerloop,iterateduntilU[|As|-|Bs|,d]=|As|}U[ab,d]=max(U[ab+1,d-insertCost],U[ab,d-mismatchCost]+1,U[ab-1,d-deleteCost]+1){InnerLoop,extendsdiagonalonarunofmatches}while(As[U[ab,d]+1]=Bs[U[ab,d]-ab+1])U[ab,d]+=14Genbank1000500010000,Needleman2WunschDivide2and2ConquerHirschbergUkkonenUHF,UHFPentium4,CPU1.6GHz,RAM640MB,Windows2000PC121,1000,UHFNeedleman2WunschDivide2and2ConquerHirschberg,Ukkonen;500010000,UHF2,1000500010000,UHFNeedleman2WunschUkkonen,Divide2and2ConquerHirschberg,UHF,UHF1(s)1000500010000Needleman2Wunsch9.2236.5466.75Hirschberg18.4473.08133.50Divide2and2Conquer5.9924.3540.41Ukkonen4.5319.9835.62UHF4.9818.7332.5221000500010000Needleman2Wunsch19MB54MB101MBHirschberg20KB49KB87KBDivide2and2Conquer22KB52KB95KBUkkonen19MB54MB101MBUHF40KB141KB265KB[1]NeedlemanS,WunschC.Ageneralmethodapplicabletothesearchforsimilaritiesintheaminoacidsequencesoftwoproteins[J].JournalofMolecularBiology,1970,48.443-453.[2]MountDW.Bioinformatics:sequenceandgenomeanalysis[M].USA:ColdSpringHarborLaboratoryPress,2002.53-72.[3]HirschbergD.Alinearspacealgorithmforcomputingmaximalcommonsubsequences[J].CommACM,1975,18(6):341-343.[4]UkkonenE.Onapproximatestringmatching[A].ProceedingsIntCorfFoundComputTheory,1983,158.487-495[5]PowellDR,AllisonL,DixTI.Aversatiledivideandconquertechniqueforoptimalstringalignment[J].InformationProcessingLetters,1999,70(3):127-139.[6],,.[J].,2002,19(6):1-5.8032004©1994-2008ChinaAcademicJournalElectronicPublishingHouse.Allrightsreserved.