-
Notifications
You must be signed in to change notification settings - Fork 3
/
nwunsch.js
109 lines (100 loc) · 3.11 KB
/
nwunsch.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
function stringalign(ainstr, binstr, mispen, gappen, skwpen)
{
ain = ainstr.split('');
bin = binstr.split('');
var i, j ,k;
var dn,rt,dg;
var ia = ain.length, ib = bin.length;
var aout=[]; // .resize(ia+ib);
var bout=[];
var summary=[];
var cost=[];
var marked=[];
for(n=0 ; n < ia+1 ;++n) {
cost[n] = new Array(ib+1);
marked[n] = new Array(ib+1);
}
cost[0][0] = 0.;
for (i=1;i<=ia;i++) cost[i][0] = cost[i-1][0] + skwpen;
for (i=1;i<=ib;i++) cost[0][i] = cost[0][i-1] + skwpen;
for (i=1;i<=ia;i++) for (j=1;j<=ib;j++) {
dn = cost[i-1][j] + ((j == ib)? skwpen : gappen);
rt = cost[i][j-1] + ((i == ia)? skwpen : gappen);
dg = cost[i-1][j-1] + ((ain[i-1] == bin[j-1])? -1. : mispen);
cost[i][j] = Math.min(dn,rt,dg);
}
i=ia; j=ib; k=0;
while (i > 0 || j > 0) {
marked[i][j]=1;
dn = rt = dg = 9.99e99;
if (i>0) dn = cost[i-1][j] + ((j==ib)? skwpen : gappen);
if (j>0) rt = cost[i][j-1] + ((i==ia)? skwpen : gappen);
if (i>0 && j>0) dg = cost[i-1][j-1] +
((ain[i-1] == bin[j-1])? -1. : mispen);
if (dg <= Math.min(dn,rt)) {
aout[k] = ain[i-1];
bout[k] = bin[j-1];
summary[k++] = ((ain[i-1] == bin[j-1])? '=' : '!');
i--; j--;
}
else if (dn < rt) {
aout[k] = ain[i-1];
bout[k] = ' ';
summary[k++] = ' ';
i--;
}
else {
aout[k] = ' ';
bout[k] = bin[j-1];
summary[k++] = ' ';
j--;
}
marked[i][j]=1;
}
for (i=0;i<k/2;i++) {
var t = aout[k-1-i];
aout[k-1-i] = aout[i];
aout[i]=t;
t=bout[k-1-i];
bout[k-1-i] = bout[i];
bout[i]=t;
t=summary[k-1-i];
summary[k-1-i]=summary[i];
summary[i]=t;
}
aout.size=k; bout.size=k; summary.size=k;
// console.log(aout.join(''));
// console.log(bout.join(''));
// console.log(summary.join(''));
var table="";
table+="<tr><td></td>";
for(n=0; n<bin.length;++n)
table+="<th>"+bin[n]+"</th>";
table+="</tr>";
for(n=0; n < cost.length; ++n) {
table+="<tr>";
if(n < cost.length - 1)
table+="<th>"+ain[n]+"</th>";
else
table+="<td></td>";
for(m=0; m < cost[n].length; ++m) {
if(marked[n][m]==1)
table+='<td align="center" bgcolor="#ff0000">'+cost[n][m] +"</td>";
else
table+='<td align="center">'+cost[n][m] +"</td>";
}
table+="</tr>";
}
$("#mat").html(table);
$("#newA").html(aout.join("").replace(/ /g, " "));
$("#newB").html(bout.join("").replace(/ /g, " "));
$("#summary").html(summary.join("").replace(/ /g, " "));
}
function update()
{
// console.log("update called");
stringalign($("#a").val(), $("#b").val(), 1.0*$("#mispen").val(), 1.0*$("#gappen").val(), 1.0*$("#skwpen").val());
}
$(function() {
// console.log( "ready!" );
});