function aln_xdrop(a, b, pen, xdrop) {
let max_sc = xdrop, max_i = -1, max_j = -1;
let st = 0, H = [];
for (let j = 0; j < b.length; ++j) { // initialize row -1
const sc = xdrop - pen * (j + 1);
if (sc <= 0) break;
H[j] = sc;
}
for (let i = 0; i < a.length; ++i) {
// console.log(H)
let H11 = st === 0? xdrop - pen * i : H[st - 1]; // H[i-1,j-1]
let H01 = H11 - pen; // H[i,j-1] = H[i-1,j-1] - pen
if (H01 <= 0) ++st; // ignored dropped cells
let max_row_sc = 0; // max score on row i
for (let j = st; j < b.length; ++j) {
let H00 = H11 + (a[i] == b[j]? 1 : -pen); // H[i,j] = H[i-1,j-1] + s(a[i], b[j])
if (j < H.length)
H00 = H00 > H[j] - pen? H00 : H[j] - pen; // H[i,j] = max(H[i,j], H[i-1,j] - pen)
H00 = H00 > H01 - pen? H00 : H01 - pen; // H[i,j] = max(H[i,j], H[i,j-1] - pen)
if (j >= H.length && H00 <= max_sc - xdrop) break;
max_row_sc = max_row_sc > H00? max_row_sc : H00; // keep the max row score
if (H00 > max_sc) // keep the overall max score and the cell position
max_sc = H00, max_i = i, max_j = j;
H01 = H00;
H11 = j < H.length? H[j] : 0;
H[j] = H00;
}
if (max_row_sc <= max_sc - xdrop) break;
}
return [max_sc - xdrop, max_i, max_j];
}
// let a = "GTTGATGGTCTACAACGTTATCGTCACAGCCCATGCATTTGTAATAATCTTCTTCATAGTAATA";
// let b = "GATAGATGGTCTGAGCTATGATATCAATTGGCTTCCTAGGGTTTATCGTGTGAGCACACCATATT";
let a = "CGATATAAGCAATATTATTATATTACGCCCAATAAACGATAGCTAATATGCCGCGGAGCGATCGAACCGCCCCGATAAGACCCC";
let b = "CGATATAAGCAATATTAaTATATTAGCCCAATAAACGATAGCTAATATGggGCGGAGCGATCGAACCGCCCCGAaaTAAGACCCC";
let [max_sc, max_i, max_j] = aln_xdrop(a, b, 2, 5);
console.log(max_sc, max_i, max_j, a.substr(0, max_i+1), b.substr(0, max_j+1));
ZnVuY3Rpb24gYWxuX3hkcm9wKGEsIGIsIHBlbiwgeGRyb3ApIHsKCWxldCBtYXhfc2MgPSB4ZHJvcCwgbWF4X2kgPSAtMSwgbWF4X2ogPSAtMTsKCWxldCBzdCA9IDAsIEggPSBbXTsKCWZvciAobGV0IGogPSAwOyBqIDwgYi5sZW5ndGg7ICsraikgeyAvLyBpbml0aWFsaXplIHJvdyAtMQoJCWNvbnN0IHNjID0geGRyb3AgLSBwZW4gKiAoaiArIDEpOwoJCWlmIChzYyA8PSAwKSBicmVhazsKCQlIW2pdID0gc2M7Cgl9CgkKCWZvciAobGV0IGkgPSAwOyBpIDwgYS5sZW5ndGg7ICsraSkgewoJCS8vIGNvbnNvbGUubG9nKEgpCgkJbGV0IEgxMSA9IHN0ID09PSAwPyB4ZHJvcCAtIHBlbiAqIGkgOiBIW3N0IC0gMV07IC8vIEhbaS0xLGotMV0KCQlsZXQgSDAxID0gSDExIC0gcGVuOyAvLyBIW2ksai0xXSA9IEhbaS0xLGotMV0gLSBwZW4KCQlpZiAoSDAxIDw9IDApICsrc3Q7IC8vIGlnbm9yZWQgZHJvcHBlZCBjZWxscwoJCWxldCBtYXhfcm93X3NjID0gMDsgLy8gbWF4IHNjb3JlIG9uIHJvdyBpCgkJZm9yIChsZXQgaiA9IHN0OyBqIDwgYi5sZW5ndGg7ICsraikgewoJCQlsZXQgSDAwID0gSDExICsgKGFbaV0gPT0gYltqXT8gMSA6IC1wZW4pOyAvLyBIW2ksal0gPSBIW2ktMSxqLTFdICsgcyhhW2ldLCBiW2pdKQoJCQlpZiAoaiA8IEgubGVuZ3RoKQoJCQkJSDAwID0gSDAwID4gSFtqXSAtIHBlbj8gSDAwIDogSFtqXSAtIHBlbjsgLy8gSFtpLGpdID0gbWF4KEhbaSxqXSwgSFtpLTEsal0gLSBwZW4pCgkJCUgwMCA9IEgwMCA+IEgwMSAtIHBlbj8gSDAwIDogSDAxIC0gcGVuOyAvLyBIW2ksal0gPSBtYXgoSFtpLGpdLCBIW2ksai0xXSAtIHBlbikKCQkJaWYgKGogPj0gSC5sZW5ndGggJiYgSDAwIDw9IG1heF9zYyAtIHhkcm9wKSBicmVhazsKCQkJbWF4X3Jvd19zYyA9IG1heF9yb3dfc2MgPiBIMDA/IG1heF9yb3dfc2MgOiBIMDA7IC8vIGtlZXAgdGhlIG1heCByb3cgc2NvcmUKCQkJaWYgKEgwMCA+IG1heF9zYykgLy8ga2VlcCB0aGUgb3ZlcmFsbCBtYXggc2NvcmUgYW5kIHRoZSBjZWxsIHBvc2l0aW9uCgkJCQltYXhfc2MgPSBIMDAsIG1heF9pID0gaSwgbWF4X2ogPSBqOwoJCQlIMDEgPSBIMDA7CgkJCUgxMSA9IGogPCBILmxlbmd0aD8gSFtqXSA6IDA7CgkJCUhbal0gPSBIMDA7CgkJfQoJCWlmIChtYXhfcm93X3NjIDw9IG1heF9zYyAtIHhkcm9wKSBicmVhazsKCX0KCXJldHVybiBbbWF4X3NjIC0geGRyb3AsIG1heF9pLCBtYXhfal07Cn0KCi8vIGxldCBhID0gICJHVFRHQVRHR1RDVEFDQUFDR1RUQVRDR1RDQUNBR0NDQ0FUR0NBVFRUR1RBQVRBQVRDVFRDVFRDQVRBR1RBQVRBIjsKLy8gbGV0IGIgPSAiR0FUQUdBVEdHVENUR0FHQ1RBVEdBVEFUQ0FBVFRHR0NUVENDVEFHR0dUVFRBVENHVEdUR0FHQ0FDQUNDQVRBVFQiOwoKbGV0IGEgPSAiQ0dBVEFUQUFHQ0FBVEFUVEFUVEFUQVRUQUNHQ0NDQUFUQUFBQ0dBVEFHQ1RBQVRBVEdDQ0dDR0dBR0NHQVRDR0FBQ0NHQ0NDQ0dBVEFBR0FDQ0NDIjsKbGV0IGIgPSAiQ0dBVEFUQUFHQ0FBVEFUVEFhVEFUQVRUQUdDQ0NBQVRBQUFDR0FUQUdDVEFBVEFUR2dnR0NHR0FHQ0dBVENHQUFDQ0dDQ0NDR0FhYVRBQUdBQ0NDQyI7CgpsZXQgW21heF9zYywgbWF4X2ksIG1heF9qXSA9IGFsbl94ZHJvcChhLCBiLCAyLCA1KTsKY29uc29sZS5sb2cobWF4X3NjLCBtYXhfaSwgbWF4X2osIGEuc3Vic3RyKDAsIG1heF9pKzEpLCBiLnN1YnN0cigwLCBtYXhfaisxKSk7