多序列比对算法的研究进展

84201012ChinaJournalofBioinformaticsVol8No4Dec.,20101,2*,3,3(1.,361005;2.,150001;3.,,150030):多序列比对在阐明一组相关序列的重要生物学模式方面起着十分重要的作用自从计算机的出现,就有许多研究者致力于多序列比对算法人类基因组计划和单体型计划使多序列比对研究再次成为研究热点本文详细归纳了多序列比对的主要算法,总结了国内外近年来多序列比对的研究进展,同时也分析并预测了未来该问题的研究方向:多序列比对;SP值;NP难题;生物信息学:Q811:A:1672-5565(2010)-04-311-05:2009-11-11;:2010-03-17.:(60932008);(JC200611);(ZJG0705):,,,E-mai:[e-mail].*:,,,E-mai:[e-mail]uenceAlignmentAlgorithmsZOUQuan1,GUOMaozu2*,HANYingpeng3,LIWenbin3(1.SchoolofInformationScienceandTechnology,XiamenUnivercity,Xiamen360005,China;2.SchoolofComputerScienceandTechnology,HarbinInstituteofTechnology,Harbin,Harbin150001,China;3.SoybeanResearchInstitute,NortheastAgriculturalUniversity;ChineseEducationMinistrysKeyLaboratoryofSoybeanBiology,Harbin150030,China)Abstract:Multiplesequencealignment(MSA)isanimportanttoolforfindingbiologypatternsinbio-sequences.Sincetheappearanceofcomputer,lotsofresearchersdevoteattentiontoMSA.Futhermore,HumanGenomeProjectandHapMapProjectencouragethedevelopmentofMSA.Inthispaperweintroducethemainalgorithmsforthisproblemandsummarizethedevelopmentinrecentyears.Atlastsomevitalaspectsthatmaybeconductedinthefutureinvestigationsarediscussed.KeyWords:multiplesequencealignment;sum-of-pairvalue;NPhardproblem;bioinformatics1,,,(alignment),,PCR(SNP),():(sum-of-pairsfunctions)(consensusfunctions)(treefunctions)[1],,SPSP,WangNP;NP[2],::,,:,,生物信息学第8卷,NP,,,,HMM22000,,[3][4][5]A[6][7]pair-HMM[8]debruijn[9,10]SP,,,[11]HMM,,SP[12,13]GibbsBayes[14][15]FDOD[16],[17],[18,19],,[20-22]90,,clustal[23]T-coffee[24-26]2.1,,,n,n,2n,O(n2);kn,O(nk),,,FengDoolittle1987[27],clustal,,,(,)kk-1,,k1,k!(progressive),Kruskal,clustalO(k3n2),,,![28],,,!,,,,,O(k2n2)Dan,SPSP2[1],,,,[29],[30],!,,312第4期邹权,等:多序列比对算法的研究进展,,2.2,,SP,,[31-34],,[35,36],[37],,,[38],SP,,,,,[39,40]A*,[41]A*,A*,A*,(),A*,,,,,,SP,,,SP2.3,SP,,,:HMM()(CGTATA-box),[42]HMM:(1)HMM,1,,HMM[43]1HMMFig.1HMMformultiplesequencealignment(2)HMM,Baum-Welch(3)HMM,,ViterbiHMM:,HMM()HMM:,HMM,;HMM,313生物信息学第8卷,()2.4,,,,,,,,1,Cedric,[44]JulieBAliBASE[45,46],[47]3,,,:(1),;,,(),,,NP(2),(,RNA),,,[48](3):,,(),,SP,,,SP,1Table1ComparisonofmainsoftwareforMSAclustal[23],,[24,25,26],clustalwindows[40]HMM,[33]COFFEE20;400(References):[1]D.Gusfield.AlgorithmsonStrings,TreesandSequences.ComputerScienceandComputationalBiology[M].CambridgeUniversityPress,1997.[2]L.Wang,T.Jiang.OntheComplexityofMultipleSequenceAlignment[J].JournalofComputationalBiology,1994,1(4):337-348.[3].314第4期邹权,等:多序列比对算法的研究进展[D].:,2006.[4].[D].:,2005.[5].[D].:,2006.[6].A-StarDiAlign[D].:,2007.[7].FFTk-mer[D].:,2007.[8].[D].:,2007.[9].DNA[D].:,2006.[10],.DNA[J].,2007,18(2):185-195.[11].[D].:,2007.[12].[D].:,2006.[13],.[J].,2006,43(8):1330-1336.[14].GibbsBayes[D].:,2004.[15].[M].:,2004.[16]MinZhang,WeiwuFang,JunhuaZhang,ZhongxianCh.iMSAID:multiplesequencealignmentbasedonameasureofinformationdiscrepancy[J].ComputationalBiologyandChemistry,2005,29(2):175-181.[17].[D].:,2005.[18].[D].:,2005.[19],,.[J].,2006,31(1):81-87.[20],,.PHGA-COFFEE:[J].,2006,29(5):727-733.[21]GuangmingTan,LinXu,DongboBu,ShengzhongFeng,NinghuiSun.ImprovementofPerformanceofMegaBlastAlgorithmforDNASequenceAlignment[J].JournalofComputerScienceandTechnology,2006(6):973-978.[22],,,,.4000H[J].,2005,42(6):1053-1058.[23]ThomposonJ.D,GibsonT.J,HigginsD.CLUSTALW:improvingthesensitivityofprogressivemultiplesequencealignmentthroughsequenceweightingposition-specificgappenaltiesandweightmatrixchoice[J].NucleicAcidsResearch,1994,22:4673-4680.[24]NoredamaC,HolmL,HigginsD.G.COFFEE:anobjectivefunctionformultiplesequencealignments[J].Bioinformatics,1998,14(5):407-422.[25]NoredamaC,HigginsD.G,HeringaJ.T-COFFEE:anovelmethodforfastandaccuratemultiplesequencealignment[J].JournalofMolecularBiology,2000,302:205-217.[26]O.OS'ullivan,KSuhre,C.Aberge,lD.G.Higgins,C.Notredame.3DCoffee:CombiningProteinSequencesandStructureswithinMultipleSequenceAlignments[J].JournalofMolecularBiology,2004,340:385-395.[27]FengD.F,DoolittleR.F.Progressivesequencealignmentasaprerequisitetocorrectphylogenetictrees[J].JournalofMolecularEvolution,1987,25:351-360.[28]S.F.Altschu,lD.J.Lipman.Trees,starsandmultiplebiologicalsequencealignment[J].SIMAJournalonAppliedMathematics.1989,49(1):197-209.[29],,,...2009,37(8):1746-1750.[30],,.SNP.2009.20091023-24..[31]ThomsenR.,FogelG.B.,KrinkT.AClustalAlignmentImproverusingEvolutionaryAlgorithm[C].Proceedingsof4thCongressonEvolutionaryComputation(CEC2002),2002,1:121-126.[32]NotredameC,OBrienE.A,ANDHigginsD.G.RAGA:RNAsequencealignmentbygeneticalgorithm[J].NucleicAcidsResearch,1997,25:4570-4580.[33]ChingZhang,WongA.K.Towardefficientmultiplemolecularsequencealignment:asystemofgeneticalgorithmanddynamicprogramming[J].IEEETransactionsonSystems,ManandCybernetics,PartB,1997,27(6):918932.[34]ChingZhang,WongA.K.Ag