基于小波包变换的多序列比对方法
|
摘要
多序列比对是一种重要的生物信息学工具,在生物的进化分析以及蛋白质的结构预测方面有着积极的意义.以CLUSTAL W为代表的渐进式比对方法在此这个领域取得了很大的成功,但其固有的缺陷阻碍了其比对精度的进一步提高.本文提出了一种基于小波包变换的多序列比对方法,这种方法利用小波包对数字信号良好的分析能力来寻找序列之间的相似片断,从而达到提高精度、降低计算量的作用.最后,本文利用多序列比对平台BA lisBASE和仿真程序ROSE,给出了此方法与其他比对算法的效率比较结果和讨论.
Multiple sequence is one of the essential tools for studying bioinformatics,and it plays an important role in the evolution analysis and protein structure prediction.Progressive multiple sequence algorithms that represented by CLUSTAL W had achieved great success in this research field,and is most widely applied.However,the inherent disadvantage of the program has encumbered further improvement of alignment efficiency.In this paper,a novel method for multiple sequence alignment based on wavelet package transform is developed.This method can find homologous regions rapidly by wavelet package,so that the alignment efficiency is improved,and the computation time is reduced.A comparison result with other algorithms as well as some discussion with the help of a multiple alignment benchmark BALiBASE and a simulation program Rose are given.
Multiple sequence is one of the essential tools for studying bioinformatics,and it plays an important role in the evolution analysis and protein structure prediction.Progressive multiple sequence algorithms that represented by CLUSTAL W had achieved great success in this research field,and is most widely applied.However,the inherent disadvantage of the program has encumbered further improvement of alignment efficiency.In this paper,a novel method for multiple sequence alignment based on wavelet package transform is developed.This method can find homologous regions rapidly by wavelet package,so that the alignment efficiency is improved,and the computation time is reduced.A comparison result with other algorithms as well as some discussion with the help of a multiple alignment benchmark BALiBASE and a simulation program Rose are given.
引文
[1]OSAMU GOTOH.Mu ltip le sequence alignm ent:algorithm s and app lications[J].Adv.B iophys,1999,36,159-206.
[2]NEEDLEMAN S B,WUNSCH C D.A generalm ethod app licab le to the search for sim ilarities in the am ino ac id sequence oftwo prote ins[J].J.Mol.B iol.,1970,48,443-453.
[3]J K IM,S PRAMANIK,M J CHUNG.Mu ltip le Sequence A lignm ent using S imu lated Annealing[J].Comp.App lic.B iosc i.,1994,10,419-426.
[4]J K IM,J R COLE,S PRAMANIK.A lignm ent of possib le secondary structures in mu ltip le RNA sequences using simu lated an-nealing[J].Comp.App lic.B iosc i.,1996,12,259-267.
[5]L A ANABARASU.Mu ltip le Sequence A lignm ent using parallel genetic algorithm[A].The Second Asia-Pac ific Conferenceon S imu lated Annealing,Canberra,Australia 1998.
[6]R GONZALEZ.Mu ltip le Prote in Sequence comparison by genetic algorithm s[A].SPIE-98,1999.
[7]C ZHANG,A K WONG.A genetic algorithm for mu ltip le molecu lar sequence alignm ent[J].Comput App l B iosc i,1997,13,565-581.
[8]C NOTREDAME,D G H IGG INS.SAGA:sequence alignm ent by genetic algorithm[J].Nuc le ic Ac ids Res.,1996,24,1515-1524.
[9]JULIE D.Thompson,et al.CLUSTAL W:improving the sensitivity of progressive mu ltip le sequence alignm ent through se-quence we ighting,posit on-spec ific gap penalties and we ight m atrix choice[J].Nuc le ic.Ac ids.Research,1994,22,4673-4680.
[10]OSAMU GOTOH.S ign ificant Improvem ent in Accuracy ofMu ltip le Prote in Sequence A lignm ents by Iterative Refinem ent asAssessed by Reference to Structural A lignm ents[J].J.Mol.B iol,1996,264,823-838.
[11]KAZUTAKA KATOH,et al.MAFFT:a novelm ethod for rap id mu ltip le sequence alignm ent based on fast Fourier transform[J].Nuc le ic.Ac ids.Research,2002,30,3059-3066.
[12]ROBERT C.EDGAR.MUSCLE:mu ltip le sequence alignm ent w ith h igh accuracy and h igh throughput[J].Nuc le ic.Ac ids.Research,2004,32,1792-1797.
[13]彭玉华.小波变换与工程应用[M].北京:科学出版社,2000.
[14]GRANTHAM R.Am ino ac id d ifference formu la to help exp lain prote in evolution[J].Sc ience,1974,185,862-831.
[15]COFIMAN R,MEGER Y,W ICKERHAUSER.S ile properties of wavelet packets[M].preprint,cerem ade,Un iversity Paris-Pauph ine,1990.
[16]COFIMAN R R,W ICKERHAUSER M M.Best adapted wavelet packet bases[M].preprint,Yale Un iversity,1990.
[17]蒋忠进,等.小波包在可控震源地震信号延时估计中的应用[J].吉林大学学报,2003,21,105-109.
[18]ANNE BAHR,JULIE D THOMPSON,et al.BaliBASE(Benchm ark A lignm ent database):enhancem ents for repeats,trans-m embrance sequence and c ircu lar permutations[J].Nuc le ic.Ac ids.Research,2001,29,323-326.
[19]JENE STOYE,et al.Rose:generating sequence fam ilies[J].B ioinform atics,1998,14,157-163.
[2]NEEDLEMAN S B,WUNSCH C D.A generalm ethod app licab le to the search for sim ilarities in the am ino ac id sequence oftwo prote ins[J].J.Mol.B iol.,1970,48,443-453.
[3]J K IM,S PRAMANIK,M J CHUNG.Mu ltip le Sequence A lignm ent using S imu lated Annealing[J].Comp.App lic.B iosc i.,1994,10,419-426.
[4]J K IM,J R COLE,S PRAMANIK.A lignm ent of possib le secondary structures in mu ltip le RNA sequences using simu lated an-nealing[J].Comp.App lic.B iosc i.,1996,12,259-267.
[5]L A ANABARASU.Mu ltip le Sequence A lignm ent using parallel genetic algorithm[A].The Second Asia-Pac ific Conferenceon S imu lated Annealing,Canberra,Australia 1998.
[6]R GONZALEZ.Mu ltip le Prote in Sequence comparison by genetic algorithm s[A].SPIE-98,1999.
[7]C ZHANG,A K WONG.A genetic algorithm for mu ltip le molecu lar sequence alignm ent[J].Comput App l B iosc i,1997,13,565-581.
[8]C NOTREDAME,D G H IGG INS.SAGA:sequence alignm ent by genetic algorithm[J].Nuc le ic Ac ids Res.,1996,24,1515-1524.
[9]JULIE D.Thompson,et al.CLUSTAL W:improving the sensitivity of progressive mu ltip le sequence alignm ent through se-quence we ighting,posit on-spec ific gap penalties and we ight m atrix choice[J].Nuc le ic.Ac ids.Research,1994,22,4673-4680.
[10]OSAMU GOTOH.S ign ificant Improvem ent in Accuracy ofMu ltip le Prote in Sequence A lignm ents by Iterative Refinem ent asAssessed by Reference to Structural A lignm ents[J].J.Mol.B iol,1996,264,823-838.
[11]KAZUTAKA KATOH,et al.MAFFT:a novelm ethod for rap id mu ltip le sequence alignm ent based on fast Fourier transform[J].Nuc le ic.Ac ids.Research,2002,30,3059-3066.
[12]ROBERT C.EDGAR.MUSCLE:mu ltip le sequence alignm ent w ith h igh accuracy and h igh throughput[J].Nuc le ic.Ac ids.Research,2004,32,1792-1797.
[13]彭玉华.小波变换与工程应用[M].北京:科学出版社,2000.
[14]GRANTHAM R.Am ino ac id d ifference formu la to help exp lain prote in evolution[J].Sc ience,1974,185,862-831.
[15]COFIMAN R,MEGER Y,W ICKERHAUSER.S ile properties of wavelet packets[M].preprint,cerem ade,Un iversity Paris-Pauph ine,1990.
[16]COFIMAN R R,W ICKERHAUSER M M.Best adapted wavelet packet bases[M].preprint,Yale Un iversity,1990.
[17]蒋忠进,等.小波包在可控震源地震信号延时估计中的应用[J].吉林大学学报,2003,21,105-109.
[18]ANNE BAHR,JULIE D THOMPSON,et al.BaliBASE(Benchm ark A lignm ent database):enhancem ents for repeats,trans-m embrance sequence and c ircu lar permutations[J].Nuc le ic.Ac ids.Research,2001,29,323-326.
[19]JENE STOYE,et al.Rose:generating sequence fam ilies[J].B ioinform atics,1998,14,157-163.
版权所有：© 2023 中国地质图书馆 中国地质调查局地学文献中心