Cómo construir un mejor motor de búsqueda de ADN

BúsquedasLas técnicas para indexar sitios web en el idioma chino podrían mejorar drásticamente la velocidad de las búsquedas bioinformáticas, de acuerdo con una investigación realizada por SOSO, el tercer mayor motor de búsquedas de China.

Si hay algo que nos ha enseñado Google a la actual generación de usuarios de la red, es que las búsquedas por Internet son rápidas. La pequeña impresión encima de cada búsqueda ha marcado esta idea en la cultura de las búsquedas.

Escribe la palabra “física” en el motor de búsqueda, por ejemplo, y arroja 102 millones de resultados en 0,21 segundos. Eso es asombrosamente rápido.

Esto podrían ser buenas noticias para los investigadores que peinan las bases de datos bioinformáticas. Estas bases de datos son descomunales, y crecen exponencialmente. Contienen, por ejemplo, el número que crece incesantemente de especies distintas en el planeta, así como los genomas de distintos individuos de la misma especie.

Dada nuestra experiencia con la búsqueda en la red, es fácil imaginar que encontrar que un gen es común a más de un organismo o individuo sería tan rápido como una búsqueda en Google. Pero no lo es.

La razón, de acuerdo con Wang Liang, científico de la computación en SOSO.com, uno de los tres grandes motores de búsqueda de China, es que la bioinformática no ha tenido éxito al explotar las técnicas de búsqueda que han hecho tan rápidos a motores como Google.

La mayor parte de las búsquedas bioinformáticas usan los algoritmos BLAST o FASTA. Esencialmente comparan los datos de un genoma con los de otro, y así sucesivamente. Esto es satisfactorio cuando hay un número relativamente bajo de genomas, pero se hace inmanejable cuando el número aumenta exponencialmente.

Los motores de búsqueda se enfrentaron exactamente con el mismo problema hace 20 años, con el crecimiento de la red. Los motores de búsqueda inicialmente indexaban la red registrando palabras clave contenidas en cada documento. La búsqueda de una palabra específica significaba buscarla en una página web, luego en otra, etc. Esta aproximación se hizo cada vez más lenta conforme crecía el número de documentos.

Por lo que los motores tomaron otra aproximación: dieron la vuelta al proceso de indexado creando lo que se conoce como un índice invertido. “La idea del índice invertido es muy simple”, dice Liang.

En lugar de crear una lista de páginas web y las palabras de cada página, el proceso de indexado registra para cada palabra la lista de páginas web en las que aparece.

Por lo que ahora sólo se busca a través de la lista de palabras que el motor de búsqueda ha indexado. Cuando encuentra la palabra, esa entrada también registra las páginas web en las que aparece. En otras palabras, en lugar de buscar en un índice de páginas web para encontrar una palabra concreta, se busca a través de un índice de palabras para encontrar las páginas web en las que aparece.

Esto simplifica drásticamente las cosas pero hay varias complejidades que dificultan el proceso de indexado. Por ejemplo, en inglés, los espacios entre palabras muestran claramente dónde empieza y termina una palabra. Éste no es el caso para los datos genéticos. Por lo que una pregunta importante es qué constituye una palabra.

Liang dice que una pista importante procede de la forma en que los motores de búsqueda indexan lenguajes como el chino, donde no hay espacios entre palabras. Una forma de indexar un documento chino es segmentar el texto en n-gramas, palabras que tienen una longitud de n-letras. Por lo que se empieza segmentando en 1-gramas, palabras de una letra, y luego en 2-gramas, palabras de dos letras. Una búsqueda de una palabra de tres letras, tal como ABC, puede realizarse buscando los 2-gramas AB y BC.

De hecho, algunos motores de búsqueda chinos funcionan exactamente de esta forma, indexando todos los 2-gramas.

Pero, ¿cuántas letras hay en una palabra genética, cuántos n-gramas debería buscar un motor de búsqueda? Una segmentación de 1-gramas da sólo cuatro palabras, las bases de nucleótidos A, T, C y G. Pero eso no es bueno dado que las búsquedas combinadas que necesiten palabras más largas se harán inmanejables.

La respuesta procede de la distribución estadística de las palabras en las secuencias de ADN que Liang dice que sigue la Ley de Zipf. Esto básicamente afirma que en un documento de cualquier longitud, el 50 por ciento de las palabras aparecen sólo una vez. Esto puede usarse para encontrar un tipo de longitud media en las palabras del ADN.

En el chino, por ejemplo, el porcentaje de palabras de 1-gramas que aparecen sólo una vez es menor del 50%, el porcentaje de palabras de 2-gramas que aparecen sólo una vez es de aproximadamente el 50% y el de palabras 3-gramas es de menos del 50%. Por lo que las palabras de 2-gramas son una buena media.

Liang aplica el mismo criterio para encontrar la longitud media de palabras en los genomas de arabidopsis, aspergillus, la mosca de la fruta y el ratón. Y encontró que una buena longitud media de palabra es de unas 12 letras. Por lo que la mejor forma de indexar los datos del genoma es buscar 12-gramas, dice.

Nada de esto necesita que se complete una nueva tecnología. Liang dice que el motor de búsqueda de código abierto Lucene es el foro perfecto en el cual realizar el trabajo y, de forma impresionante, incluso lo ha usado para construir su propio motor de búsqueda bioinformático rudimentario.

Tiene sentido que los enormes avances realizados en las búsquedas que se han realizado mediante los motores de búsqueda comerciales, puedan encontrar una aplicación en el mundo de la bioinformática. Tal vez incluso hay un decente modelo de negocio en tal plan, por ejemplo mostrando anuncios orientados al tipo de persona que trabaja con las búsquedas bioinformáticas.

La única pregunta es quién llevará la cabeza en este área. Y si este trabajo es algo sobre lo que basarse, parece que el motor de búsqueda chino SOSO tiene el liderato.


Artículo de Referencia: arxiv.org/abs/1006.4114: How To Build A DNA Search Engine Like Google?
Fecha Original: 30 de junio de 2010
Enlace Original

Comparte:
  • Print
  • Digg
  • StumbleUpon
  • del.icio.us
  • Facebook
  • Twitter
  • Google Bookmarks
  • Bitacoras.com
  • Identi.ca
  • LinkedIn
  • Meneame
  • Netvibes
  • Orkut
  • PDF
  • Reddit
  • Tumblr
  • Wikio
This page is wiki editable click here to edit this page.

Like This Post? Share It

Comments (2)

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos necesarios están marcados *