Detectar subcadenas de ADN en O(n)

adn_subcadena.js

/*
* Dada una cadena de ADN (ej: GATACGATCGTACGAT) detectar en tiempo O(n) si una subcadena (ej: GACA) esta contenida.
*
*/

valores = {
  A: 1,
  C: 2,
  G: 3,
  T: 4
};

// Hash simple. Usando el mapa de valores (A=1, C=2, G=3, T=4), crea un numero.
function hash(str, largo = null){
  if(!largo)
    largo = str.length;
  val = 0;
  for(i=0; i<largo; i++){
    letra = str[i];
    val += Math.pow(4, i) * valores[letra];
  }
  return val;
}

console.assert(hash('AAA') == 21);
console.assert(hash('AA') == 5);
console.assert(hash('A') == 1);
console.assert(hash('C') == 2);
console.assert(hash('CG') == 14);
console.assert(hash('CGA') == 30);

// Obtiene el siguiente hash en una string, a partir del hash actual,
// y la posicion y largo de la ventana para hashear
function siguienteHash(hashActual, string, posActual, largo){
  hashActual = Math.floor(hashActual / 4);
  factor = Math.pow(4, largo - 1);
  nuevaLetra = string[posActual + largo];
  hashActual += factor * valores[nuevaLetra];
  return hashActual;
}

console.assert(siguienteHash(hash('AAA'), 'AAAG', 0, 3) == hash('AAG'));
console.assert(siguienteHash(hash('AGT'), 'AAGGTAGTAA', 5, 3) == hash('GTA'));
console.assert(siguienteHash(hash('G'), 'AAGGTAGTAA', 6, 1) == hash('T'));
console.assert(siguienteHash(hash('AGTAGA'), 'AAGGAGTAGATAGTAA', 4, 6) == hash('GTAGAT'));

// Realizar la busqueda completa moviendo la ventana de hashing
function contiene(todo, buscar){

  if(buscar.length > todo.length)
    return false;

  hashBuscar = hash(buscar);
  hashTodo = hash(todo, buscar.length);

  if(hashBuscar == hashTodo)
    return true;

  for(i=1; i<todo.length - buscar.length + 1; i++){
    hashTodo = siguienteHash(hashTodo, todo, i-1, buscar.length);
    if(hashBuscar == hashTodo)
      return true;
  }
  return false;
}

// Helper para las pruebas
function contieneTest(todo, buscar){
  a = contiene(todo, buscar);
  b = todo.indexOf(buscar) != 1;
  return a && b;
}

// Si esta contenido
console.assert(contieneTest('AAAAAAAAA', 'AAAA'));
console.assert(contieneTest('GATACA', 'TAC'));
console.assert(contieneTest('TAAATACA', 'ATAC'));
console.assert(contieneTest('AATT', 'TT'));
console.assert(contieneTest('ATAGCTAGCTAGCTAGCTAGTCATCA', 'GCTAGCTAGCTAGTCA'));
console.assert(contieneTest('ATAGCTAGCTAGCTAGCTAGTCATCA', 'ATAGCTAGCTAGCTAGCTAGTCATCA'));
console.assert(contieneTest('ATAGCTAGCTAGCTAGCTAGTCATCA', 'GCTAGCTAGTCATCA'));
console.assert(contieneTest('ATAGAAAAAAAAA', 'ATAG'));
console.assert(contieneTest('ATAGAAAAAAAAA', 'AAAAAAAAA'));
console.assert(contieneTest('AAAAAGGTTCC', 'GGTTCC'));

// No esta contenido

console.assert(!contieneTest('AAAAAAAAA', 'AAGAA'));
console.assert(!contieneTest('GATACA', 'AACA'));
console.assert(!contieneTest('AAAAA', 'AAGA'));
console.assert(!contieneTest('AATT', 'TAAATACA'));
console.assert(!contieneTest('ATAGCTAGCTAGCTAGCTAGTCATCA', 'GGGG'));
console.assert(!contieneTest('ATAGCTAGCTAGCTAGCTAGTCATCA', 'AA'));