js 动态规划算法:DNA序列比对

　　JavaScript动态序列比对代码，随便 写着玩的，在网上见到用VC、VB写的比较多，这个算法以前在高中课本上见到过，我只是用Js写一下试试，或许还不是太准确。

<script><br /> function pairaln(seq1, seq2){<br /> // scoring scheme<br /> var MATCH = 1; // +1 for letters that match<br /> var MISMATCH = -1; // -1 for letters that mismatch<br /> var GAP = -1; // -1 for any gap<br /> // initialization<br /> var score=[[]];<br /> var pointer=[[]];<br /> score[0][0] = 0;<br /> pointer[0][0] = 0;<br /> var l1=seq1.length<br /> var l2=seq2.length<br /> for(var j = 1; j <= l1; j++) {<br /> score[0][j] = GAP * j;<br /> pointer[0][j] = 2;<br /> }<br /> for (var i = 1; i <= l2; i++) {<br /> score[i]=[];<br /> pointer[i]=[];<br /> score[i][0] = GAP * i;<br /> pointer[i][0] = 3;<br /> }<br /> // fill<br /> for(var i = 1; i <= l2; i++) {<br /> var letter2 = seq2.charAt(i-1);<br /> for(var j = 1; j <= l1; j++) {<br /> var diagonal_score, left_score, up_score;<br /> // calculate match score<br /> var letter1 = seq1.charAt(j-1);<br /> if (letter1 == letter2) {<br /> diagonal_score = score[i-1][j-1] + MATCH;<br /> }<br /> else {<br /> diagonal_score = score[i-1][j-1] + MISMATCH;<br /> }<br /> // calculate gap scores<br /> up_score = score[i-1][j] + GAP;<br /> left_score = score[i][j-1] + GAP;<br /> // choose best score<br /> if (diagonal_score >= up_score) {<br /> if (diagonal_score >= left_score) {<br /> score[i][j] = diagonal_score;<br /> pointer[i][j] = 1;<br /> }<br /> else {<br /> score[i][j] = left_score;<br /> pointer[i][j] = 2;<br /> }<br /> } else {<br /> if (up_score >= left_score) {<br /> score[i][j] = up_score;<br /> pointer[i][j] = 3;<br /> }<br /> else {<br /> score[i][j] = left_score;<br /> pointer[i][j] = 2;<br /> }<br /> }<br /> }<br /> }<br /> // trace-back<br /> var align1 = [];<br /> var align2 = [];<br /> // start at last cell of matrix<br /> var j = l1;<br /> var i = l2;<br /> while (1) {<br /> if(pointer[i][j] == 0)break // ends at first cell of matrix<br /> if (pointer[i][j] == 1) {<br /> align1[align1.length] = seq1.charAt(j-1);<br /> align2[align2.length] = seq2.charAt(i-1);<br /> i--;<br /> j--;<br /> }<br /> if (pointer[i][j] == 2) {<br /> align1[align1.length] = seq1.charAt(j-1);<br /> align2[align2.length] = "-";<br /> j--;<br /> }<br /> if (pointer[i][j] == 3) {<br /> align1[align1.length] = "-";<br /> align2[align2.length] = seq2.charAt(i-1);<br /> i--;<br /> }<br /> }<br /> align1 = align1.reverse();<br /> align2 = align2.reverse();<br /> return "序列：<p>"+seq1+"<br>"+seq2+"<p>比对结果：<table><tr><td>"+align1.join("</td><td>")+"</td></tr><tr><td>"+align2.join("</td><td>")+"</tr></table>"<br /> }<br /> document.write(pairaln('CTGGGCTGACTGA', 'GACTAGCTAGACTGA'))<br /> </script><br /><center>如不能显示效果，请按Ctrl+F5刷新本页，更多网页代码：<a href='http://www.veryhuo.com/' target='_blank'>http://www.veryhuo.com/</a></center>
提示：可修改后代码再运行!