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) {
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, 10);
console.log(max_sc, max_i, max_j, a.substr(0, max_i+1), b.substr(0, max_j+1));
ZnVuY3Rpb24gYWxuX3hkcm9wKGEsIGIsIHBlbiwgeGRyb3ApIHsKCWxldCBtYXhfc2MgPSB4ZHJvcCwgbWF4X2kgPSAtMSwgbWF4X2ogPSAtMTsKCWxldCBzdCA9IDAsIEggPSBbXTsKCWZvciAobGV0IGogPSAwOyBqIDwgYi5sZW5ndGg7ICsraikgeyAvLyBpbml0aWFsaXplIHJvdyAtMQoJCWNvbnN0IHNjID0geGRyb3AgLSBwZW4gKiAoaiArIDEpOwoJCWlmIChzYyA8PSAwKSBicmVhazsKCQlIW2pdID0gc2M7Cgl9CgkKCWZvciAobGV0IGkgPSAwOyBpIDwgYS5sZW5ndGg7ICsraSkgewoJCWxldCBIMTEgPSBzdCA9PT0gMD8geGRyb3AgLSBwZW4gKiBpIDogSFtzdCAtIDFdOyAvLyBIW2ktMSxqLTFdCgkJbGV0IEgwMSA9IEgxMSAtIHBlbjsgLy8gSFtpLGotMV0gPSBIW2ktMSxqLTFdIC0gcGVuCgkJaWYgKEgwMSA8PSAwKSArK3N0OyAvLyBpZ25vcmVkIGRyb3BwZWQgY2VsbHMKCQlsZXQgbWF4X3Jvd19zYyA9IDA7IC8vIG1heCBzY29yZSBvbiByb3cgaQoJCWZvciAobGV0IGogPSBzdDsgaiA8IGIubGVuZ3RoOyArK2opIHsKCQkJbGV0IEgwMCA9IEgxMSArIChhW2ldID09IGJbal0/IDEgOiAtcGVuKTsgLy8gSFtpLGpdID0gSFtpLTEsai0xXSArIHMoYVtpXSwgYltqXSkKCQkJaWYgKGogPCBILmxlbmd0aCkKCQkJCUgwMCA9IEgwMCA+IEhbal0gLSBwZW4/IEgwMCA6IEhbal0gLSBwZW47IC8vIEhbaSxqXSA9IG1heChIW2ksal0sIEhbaS0xLGpdIC0gcGVuKQoJCQlIMDAgPSBIMDAgPiBIMDEgLSBwZW4/IEgwMCA6IEgwMSAtIHBlbjsgLy8gSFtpLGpdID0gbWF4KEhbaSxqXSwgSFtpLGotMV0gLSBwZW4pCgkJCWlmIChqID49IEgubGVuZ3RoICYmIEgwMCA8PSBtYXhfc2MgLSB4ZHJvcCkgYnJlYWs7CgkJCW1heF9yb3dfc2MgPSBtYXhfcm93X3NjID4gSDAwPyBtYXhfcm93X3NjIDogSDAwOyAvLyBrZWVwIHRoZSBtYXggcm93IHNjb3JlCgkJCWlmIChIMDAgPiBtYXhfc2MpIC8vIGtlZXAgdGhlIG92ZXJhbGwgbWF4IHNjb3JlIGFuZCB0aGUgY2VsbCBwb3NpdGlvbgoJCQkJbWF4X3NjID0gSDAwLCBtYXhfaSA9IGksIG1heF9qID0gajsKCQkJSDAxID0gSDAwOwoJCQlIMTEgPSBqIDwgSC5sZW5ndGg/IEhbal0gOiAwOwoJCQlIW2pdID0gSDAwOwoJCX0KCQlpZiAobWF4X3Jvd19zYyA8PSBtYXhfc2MgLSB4ZHJvcCkgYnJlYWs7Cgl9CglyZXR1cm4gW21heF9zYyAtIHhkcm9wLCBtYXhfaSwgbWF4X2pdOwp9CgovLyBsZXQgYSA9ICAiR1RUR0FUR0dUQ1RBQ0FBQ0dUVEFUQ0dUQ0FDQUdDQ0NBVEdDQVRUVEdUQUFUQUFUQ1RUQ1RUQ0FUQUdUQUFUQSI7Ci8vIGxldCBiID0gIkdBVEFHQVRHR1RDVEdBR0NUQVRHQVRBVENBQVRUR0dDVFRDQ1RBR0dHVFRUQVRDR1RHVEdBR0NBQ0FDQ0FUQVRUIjsKCmxldCBhID0gIkNHQVRBVEFBR0NBQVRBVFRBVFRBVEFUVEFDR0NDQ0FBVEFBQUNHQVRBR0NUQUFUQVRHQ0NHQ0dHQUdDR0FUQ0dBQUNDR0NDQ0NHQVRBQUdBQ0NDQyI7CmxldCBiID0gIkNHQVRBVEFBR0NBQVRBVFRBYVRBVEFUVEFHQ0NDQUFUQUFBQ0dBVEFHQ1RBQVRBVEdnZ0dDR0dBR0NHQVRDR0FBQ0NHQ0NDQ0dBYWFUQUFHQUNDQ0MiOwoKbGV0IFttYXhfc2MsIG1heF9pLCBtYXhfal0gPSBhbG5feGRyb3AoYSwgYiwgMiwgMTApOwpjb25zb2xlLmxvZyhtYXhfc2MsIG1heF9pLCBtYXhfaiwgYS5zdWJzdHIoMCwgbWF4X2krMSksIGIuc3Vic3RyKDAsIG1heF9qKzEpKTs=