fork download
copy 
  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. 	for (let i = 0; i < a.length; ++i) {
  10. 		let H11 = st === 0? xdrop - pen * i : H[st - 1]; // H[i-1,j-1]
  11. 		let H01 = H11 - pen; // H[i,j-1] = H[i-1,j-1] - pen
  12. 		if (H01 <= 0) ++st; // ignored dropped cells
  13. 		let max_row_sc = 0; // max score on row i
  14. 		for (let j = st; j < b.length; ++j) {
  15. 			let H00 = H11 + (a[i] == b[j]? 1 : -pen); // H[i,j] = H[i-1,j-1] + s(a[i], b[j])
  16. 			if (j < H.length)
  17. 				H00 = H00 > H[j] - pen? H00 : H[j] - pen; // H[i,j] = max(H[i,j], H[i-1,j] - pen)
  18. 			H00 = H00 > H01 - pen? H00 : H01 - pen; // H[i,j] = max(H[i,j], H[i,j-1] - pen)
  19. 			if (j >= H.length && H00 <= max_sc - xdrop) break;
  20. 			max_row_sc = max_row_sc > H00? max_row_sc : H00; // keep the max row score
  21. 			if (H00 > max_sc) // keep the overall max score and the cell position
  22. 				max_sc = H00, max_i = i, max_j = j;
  23. 			H01 = H00;
  24. 			H11 = j < H.length? H[j] : 0;
  25. 			H[j] = H00;
  26. 		}
  27. 		if (max_row_sc <= max_sc - xdrop) break;
  28. 	}
  29. 	return [max_sc - xdrop, max_i, max_j];
  30. }
  31.  
  32. let a =  "GTTGATGGTCTACAACGTTATCGTCACAGCCCATGCATTTGTAATAATCTTCTTCATAGTAATA";
  33. let b = "GATAGATGGTCTGAGCTATGATATCAATTGGCTTCCTAGGGTTTATCGTGTGAGCACACCATATT";
  34. let [max_sc, max_i, max_j] = aln_xdrop(a, b, 2, 10);
  35. 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 31712KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
6 10 11 'GTTGATGGTCT' 'GATAGATGGTCT'
https://ideone.com/68YYfz
X-drop alignment
language:
Node.js (node 11.12.0)
created:
7 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!