资源描述：
《基于最大权值路径算法的dna多序列比对方法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、ISSN1000-9825,CODENRUXUEWE-mail:jos@iscas.ac.cnJournalofSoftware,Vol.18,No.2,February2007,pp.185−195http://www.jos.org.cnDOI:10.1360/jos180185Tel/Fax:+86-10-62562563©2007byJournalofSoftware.Allrightsreserved.∗基于最大权值路径算法的DNA多序列比对方法+霍红卫,肖智伟(西安电子科技大学计算机学院,陕西西安710071)AMultipleAlignment
2、ApproachforDNASequencesBasedontheMaximumWeightedPathAlgorithms+HUOHong-Wei,XIAOZhi-Wei(SchoolofComputerScienceandTechnology,XidianUniversity,Xi’an710071,China)+Correspondingauthor:Phn:+86-29-88202363,Fax:+86-29-88202837,E-mail:hwhuo@mail.xidian.edu.cnHuoHW,XiaoZW.Amultiplealignment
3、approachforDNAsequencesbasedonthemaximumweightedpathalgorithms.JournalofSoftware,2007,18(2):185−195.http://www.jos.org.cn/1000-9825/18/185.htmAbstract:Formultiplesequencesalignmentprobleminmolecularbiologicalsequenceanalysis,whentheinputsequencenumberisverylarge,manyheuristicalgori
4、thmshavebeenproposedtoimprovethecomputationspeedandthequalityofalignment.AnapproachcalledMWPAlign(maximumweightedpathalignment)ispresentedtodoglobalmultiplealignmentforDNAsequences.Inthismethod,adeBruijngraphisusedtoexpresstheinputsequencesinformation,whichisrecordedintheedgesofthe
5、graph.Asaresult,aconsensus-findingproblemcanbetransformedtoamaximumweightedpathproblemofthegraph.MWPAlignobtainsalmostlinearcomputationspeedofthemultiplesequencesalignmentproblem.Experimentalresultsshowthattheproposedalgorithmisfeasible,andforalargenumberofsequenceswithmutationrate
6、lowerthan5.2%,MWPALigncanobtainbetteralignmentresultsandhaslowercomputationaltimeascomparedtoCLUSTALW(clusteralignmentsweight),T-CoffeeandHMMT(hiddenMarkovmodeltraining).Keywords:multiplesequencealignment;deBruijngraph;consensussequence;maximumweightedpath摘要:针对生物序列分析中的多序列比对问题,当输入数据
7、量比较大时,人们提出了很多启发式的算法来改善计算速度和比对结果.提出了用于进行全局DNA多序列比对的一种方法:MWPAlign(maximumweightedpathalignment).该算法把序列信息用deBruijn图的形式表示,并将输入序列的信息记录在图的边上,这样,就将求调和序列的问题转化为求图的最大权值路径问题,使多序列比对问题的时间复杂度降低到几乎线性.实验结果显示:MWPAlign是可行的多序列比对算法,尤其对于变异率低于5.2%的大量序列数据,相对于CLUSTALW(clusteralignmentsweight),T-Coffee和HMM
8、T(hiddenMarkovmodeltrainin
