fork(1) download
  1. function aln_xdrop(a, b, pen, xdrop) {
  2. let max_sc = xdrop, max_i = -1, max_j = -1;
  3. let st = 0, H = [];
  4. for (let j = 0; j < b.length; ++j) { // initialize row -1
  5. const sc = xdrop - pen * (j + 1);
  6. if (sc <= 0) break;
  7. H[j] = sc;
  8. }
  9.  
  10. for (let i = 0; i < a.length; ++i) {
  11. let H11 = st === 0? xdrop - pen * i : H[st - 1]; // H[i-1,j-1]
  12. let H01 = H11 - pen; // H[i,j-1] = H[i-1,j-1] - pen
  13. if (H01 <= 0) ++st; // ignored dropped cells
  14. let max_row_sc = 0; // max score on row i
  15. for (let j = st; j < b.length; ++j) {
  16. let H00 = H11 + (a[i] == b[j]? 1 : -pen); // H[i,j] = H[i-1,j-1] + s(a[i], b[j])
  17. if (j < H.length)
  18. H00 = H00 > H[j] - pen? H00 : H[j] - pen; // H[i,j] = max(H[i,j], H[i-1,j] - pen)
  19. H00 = H00 > H01 - pen? H00 : H01 - pen; // H[i,j] = max(H[i,j], H[i,j-1] - pen)
  20. if (j >= H.length && H00 <= max_sc - xdrop) break;
  21. max_row_sc = max_row_sc > H00? max_row_sc : H00; // keep the max row score
  22. if (H00 > max_sc) // keep the overall max score and the cell position
  23. max_sc = H00, max_i = i, max_j = j;
  24. H01 = H00;
  25. H11 = j < H.length? H[j] : 0;
  26. H[j] = H00;
  27. }
  28. if (max_row_sc <= max_sc - xdrop) break;
  29. }
  30. return [max_sc - xdrop, max_i, max_j];
  31. }
  32.  
  33. // let a = "GTTGATGGTCTACAACGTTATCGTCACAGCCCATGCATTTGTAATAATCTTCTTCATAGTAATA";
  34. // let b = "GATAGATGGTCTGAGCTATGATATCAATTGGCTTCCTAGGGTTTATCGTGTGAGCACACCATATT";
  35.  
  36. let a = "CGATATAAGCAATATTATTATATTACGCCCAATAAACGATAGCTAATATGCCGCGGAGCGATCGAACCGCCCCGATAAGACCCC";
  37. let b = "CGATATAAGCAATATTAaTATATTAGCCCAATAAACGATAGCTAATATGggGCGGAGCGATCGAACCGCCCCGAaaTAAGACCCC";
  38.  
  39. let [max_sc, max_i, max_j] = aln_xdrop(a, b, 2, 10);
  40. console.log(max_sc, max_i, max_j, a.substr(0, max_i+1), b.substr(0, max_j+1));
Success #stdin #stdout 0.09s 31292KB
stdin
Standard input is empty
stdout
68 83 84 'CGATATAAGCAATATTATTATATTACGCCCAATAAACGATAGCTAATATGCCGCGGAGCGATCGAACCGCCCCGATAAGACCCC' 'CGATATAAGCAATATTAaTATATTAGCCCAATAAACGATAGCTAATATGggGCGGAGCGATCGAACCGCCCCGAaaTAAGACCCC'