基于最大权值路径算法的DNA多序列比对方法
针对生物序列分析中的多序列比对问题,当输入数据量比较大时,人们提出了很多启发式的算法来改善计算速度和比对结果.提出了用于进行全局DNA多序列比对的一种方法:MWPAlign(maximum weighted path alignment).该算法把序列信息用de Bruijn图的形式表示,并将输入序列的信息记录在图的边上,这样,就将求调和序列的问题转化为求图的最大权值路径问题,使多序列比对问题的时间复杂度降低到几乎线性.实验结果显示:MWPAlign是可行的多序列比对算法,尤其对于变异率低于5.2%的大量序列数据,相对于CLUSTALW(cluster alignments weight),T-Coffee和HMMT(hidden Markov model training)有较好的比对结果和运算性能.
多序列比对、de Bruijn图、调和序列、最大权值路径
18
TP301(计算技术、计算机技术)
国家自然科学基金69601003;陕西省自然科学基金2005F33
2007-04-02（万方平台首次上网日期，不代表论文的发表时间）
共11页
185-195
