Skip to content

Instantly share code, notes, and snippets.

@ChrisVilches
Last active September 15, 2017 02:07
Show Gist options
  • Save ChrisVilches/679d65298b4fd663fdac6a95668cb45f to your computer and use it in GitHub Desktop.
Save ChrisVilches/679d65298b4fd663fdac6a95668cb45f to your computer and use it in GitHub Desktop.
Detectar subcadenas de ADN en O(n)
/*
* 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'));
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment