基于最大权值路径算法的DNA多序列比对方法

• 作者: 肖智伟 霍红卫
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 多序列比对 de Bruijn图 调和序列 最大权值路径
• 年，卷（期）: 2007,（2）
• 所属期刊栏目: 算法设计与分析
• 页码范围: 185-195
• 页数: 11页
• 分类号: TP301
• 字数: 9081字
• 语种: 中文

摘要

针对生物序列分析中的多序列比对问题,当输入数据量比较大时,人们提出了很多启发式的算法来改善计算速度和比对结果.提出了用于进行全局DNA多序列比对的一种方法:MWPAlign(maximum weighted path alignment).该算法把序列信息用de Bruijn图的形式表示,并将输入序列的信息记录在图的边上,这样,就将求调和序列的问题转化为求图的最大权值路径问题,使多序列比对问题的时间复杂度降低到几乎线性.实验结果显示:MWPAlign是可行的多序列比对算法,尤其对于变异率低于5.2%的大量序列数据,相对于CLUSTALW(cluster alignments weight),T-Coffee和HMMT(hidden Markov model training)有较好的比对结果和运算性能.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	霍红卫	西安电子科技大学计算机学院	29	436	11.0	20.0
2	肖智伟	西安电子科技大学计算机学院	1	22	1.0	1.0