Skip to content

Instantly share code, notes, and snippets.

@3ki5tj

3ki5tj/salign.html

Last active August 29, 2015 14:09
Show Gist options
  • Save 3ki5tj/f268693d7d8a464fd6ca to your computer and use it in GitHub Desktop.
Save 3ki5tj/f268693d7d8a464fd6ca to your computer and use it in GitHub Desktop.
Download ZIP
Align two strings by dynamic programming (HTML/CSS/JavaScript)
Raw
salign.html
<!DOCTYPE html>
<html>
<head>
<style type="text/css">
.score_table {
background-color: #ffffd0;
font-family: "Courier New", monospace;
border-collapse: collapse;
border: 5px #ffffff groove;
}
.score_table td {
width: 32px;
height: 32px;
border: 2px #ffffff ridge;
margin: 0px;
padding: 0px;
text-align: center;
font-size: 14px;
font-weight: bold;
}
td.score_col { /* colomn */
color: #ff0000;
background-color: #ffffff;
border: 2px #ffffff ridge;
font-family: "Tahoma", "Verdana", sans-serif;
font-weight: bold;
}
td.score_row {
color: #00a000;
background-color: #ffffff;
border: 2px #ffffff ridge;
font-family: "Tahoma", "Verdana", sans-serif;
font-weight: bold;
}
td.score_trace {
color: #ffffff;
background-color: #0080ff;
border: 2px #80c0ff groove;
}
table.smtable {
border-collapse: collapse;
border: 0px #ffffff solid;
}
table.smtable td {
height: 16px;
padding: 0px;
border: 0px #ffffff solid;
font-size: 12px;
}
div#match_strings {
font-family: "Courier New", monospace;
font-size: 120%;
font-weight:bold;
margin: 5px;
}
div#match_strings span {
color: #000000;
padding: 0px 2px;
border: 1px solid;
}
span.match { background-color: #a0ffa0; }
span.okay { background-color:#ffffa0; }
span.miss { background-color:#ffa0a0; }
span.gap { background-color:#ffffff; }
td.match { background-color: #a0ffa0; }
td.miss { background-color: #ffa0a0; }
td.gap { background-color: #ffffff; }
</style>
<script type="text/javascript">
function strip(s) { return s.replace(/^\s+|\s+$/g, ''); }
// define a table element structure
function Elem(dir, score) {
this.dir = dir;
this.score = score;
this.trace = false;
}
// return the best match of two strings
function stralign()
{
var i, j, len, d, c = new Array(3);
var s = strip(document.getElementById("word1").value);
var t = strip(document.getElementById("word2").value);
var match = parseInt(strip(document.getElementById("pmatch").value));
var mis = parseInt(strip(document.getElementById("pmiss").value));
var gap = parseInt(strip(document.getElementById("pgap").value));
var n = s.length;
var m = t.length;
var tab = new Array();
for (i = 0; i <= n; i++) tab[i] = new Array();
// dynamic programming to fill to matching table
for (i = 0; i <= n; i++) tab[i][0] = new Elem(1, gap*i);
for (j = 0; j <= m; j++) tab[0][j] = new Elem(2, gap*j);
for (i = 1; i <= n; i++)
for (j = 1; j <= m; j++) {
c[0] = tab[i-1][j-1].score + ((s.charAt(i-1) == t.charAt(j-1)) ? match : mis);
c[1] = tab[i-1][j].score + gap;
c[2] = tab[i][j-1].score + gap;
if (c[1] > c[0]) {
d = (c[1] > c[2]) ? 1 : 2;
} else {
d = (c[0] > c[2]) ? 0 : 2;
}
tab[i][j] = new Elem(d, c[d]);
}
// back trace
var sm = new Array(), tm = new Array();
tagmatch0 = '<span class="match">';
tagmatch1 = '</span>';
tagmiss0 = '<span class="miss">';
tagmiss1 = '</span>';
taggap0 = '<span class="gap">';
taggap1 = '</span>';
for (len = n+m, i = n, j = m; i > 0 || j > 0; len--) {
d = tab[i][j].dir;
tab[i][j].trace = true;
if (d == 0) {
var ch1 = s.charAt(--i);
var ch2 = t.charAt(--j);
if (ch1 == ch2) {
tag0 = tagmatch0;
tag1 = tagmatch1;
} else {
tag0 = tagmiss0;
tag1 = tagmiss1;
}
sm[len] = tag0 + ch1.toString() + tag1;
tm[len] = tag0 + ch2.toString() + tag1;
} else if (d == 1) {
sm[len] = taggap0 + s.charAt(--i).toString() + taggap1;
tm[len] = taggap0 + "&nbsp;" + taggap1;
} else {
sm[len] = taggap0 + "&nbsp;" + taggap1;
tm[len] = taggap0 + t.charAt(--j).toString() + taggap1;
}
}
tab[0][0].trace = true;
for (sm1 = "", tm1 = "", i = len+1; i <= n+m; i++) {
sm1 += sm[i];
tm1 += tm[i];
}
document.getElementById("match_strings").innerHTML =
"" + sm1 + "<br>" + tm1;
// print the matching table
str = '<table class="score_table"><tr>';
for (j = 0; j < 2; j++) str += '<td class="score_row"></td>';
for (j = 1; j <= m; j++)
str += '<td class="score_row">' + t.charAt(j-1) + "</td>";
str += "</tr>\n";
for (i = 0; i <= n; i++) {
str += "<tr><td class='score_col'>"
if (i == 0) str += "&nbsp;";
else str += s.charAt(i-1);
str += "</td>";
for (j = 0; j <= m; j++) {
// small 2x2 table for each grid
smtab = '<table class="smtable"><tr>'
+ '<td>' + (tab[i][j].dir == 0 ? "&#8598;" : "&nbsp;") + '</td>'
+ '<td>' + (tab[i][j].dir == 1 ? "&#8593;" : "&nbsp;") + '</td></tr><tr>'
+ '<td>' + (tab[i][j].dir == 2 ? "&#8592;" : "&nbsp;") + '</td>'
+ '<td>' + tab[i][j].score + '</td></tr></table>';
str += (tab[i][j].trace ? '<td class="score_trace">' : "<td>") + smtab + '</td>';
}
str += "</tr>\n";
}
str += "</table>\n"
document.getElementById("score_table").innerHTML = str;
return tab[n][m].score;
}
</script>
</head>
<body>
<h2>Javascript demonstration of aligning two strings</h2>
Word 1:
<input type="text" id="word1" value="exponential" size="40"><br>
Word 2:
<input type="text" id="word2" value="polynomial" size="40"><br>
Scores:<br>
Match:
<input type="text" id="pmatch" value="0" size="4">
Mismatch:
<input type="text" id="pmiss" value="-1" size="4">
Gap:
<input type="text" id="pgap" value="-1" size="4">
<br>
<input type="button" onClick="stralign()" value="Match"><br>
<hr>
Score table: <br>
<div id="score_table"></div>
The score at the bottom-right corner of the table is
that of the optimal alignment
(whose absolute value is equal to the number of mismatches and gaps
by the default score, match=0, mismatch=-1, gap=-1).
<br>
<hr>
Best alignment: <br>
<div id="match_strings"></div>
</div>
</body>
</html>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment