En informática , un índice FM es un índice de subcadena de texto completo comprimido basado en la transformada de Burrows-Wheeler , con algunas similitudes con la matriz de sufijos . Fue creado por Paolo Ferragina y Giovanni Manzini, [1] quienes lo describen como una estructura de datos oportunista ya que permite la compresión del texto de entrada al mismo tiempo que permite consultas rápidas de subcadenas. El nombre significa índice de texto completo en espacio de minutos. [2]
Se puede usar para encontrar de manera eficiente el número de ocurrencias de un patrón dentro del texto comprimido, así como para ubicar la posición de cada ocurrencia. El tiempo de consulta, así como el espacio de almacenamiento requerido , tiene una complejidad sublineal con respecto al tamaño de los datos de entrada.
Los autores originales han ideado mejoras a su enfoque original y lo han denominado "FM-Index versión 2". [3] Una mejora adicional, el índice FM compatible con el alfabeto, combina el uso de aumento de compresión y árboles de ondas [4] para reducir significativamente el uso de espacio para alfabetos grandes.
El índice FM se ha utilizado, entre otros lugares, en bioinformática . [5]
Fondo
El uso de un índice es una estrategia común para buscar de manera eficiente un gran cuerpo de texto. Cuando el texto es más grande de lo que cabe razonablemente en la memoria principal de una computadora, es necesario comprimir no solo el texto sino también el índice. Cuando se introdujo el índice FM, se sugirieron varias soluciones que se basaban en métodos de compresión tradicionales y trataban de resolver el problema de correspondencia comprimida. Por el contrario, el índice FM es un índice propio comprimido, lo que significa que comprime los datos y los indexa al mismo tiempo.
Estructura de datos de índice FM
Un índice FM se crea tomando primero la transformada de Burrows-Wheeler (BWT) del texto de entrada. Por ejemplo, el BWT de la cadena T = "abracadabra $" es "ard $ rcaaaabb", y aquí está representado por la matriz M donde cada fila es una rotación del texto y las filas se han ordenado lexicográficamente. La transformación corresponde a la última columna denominada L .
I | F | L | |
---|---|---|---|
1 | PS | abracadabr | a |
2 | a | $ abracadab | r |
3 | a | sujetador $ abraca | D |
4 | a | bracadabra | PS |
5 | a | cadabra $ ab | r |
6 | a | dabra $ abra | C |
7 | B | ra $ abracad | a |
8 | B | racadabra $ | a |
9 | C | adabra $ abr | a |
10 | D | abra $ abrac | a |
11 | r | una $ abracada | B |
12 | r | acadabra $ a | B |
El BWT en sí mismo permite cierta compresión con, por ejemplo, mover al frente y codificación Huffman , pero la transformación tiene aún más usos. Las filas de la matriz son esencialmente los sufijos ordenados del texto y la primera columna F de la matriz comparte similitudes con las matrices de sufijos . La forma en que la matriz de sufijos se relaciona con el BWT se encuentra en el corazón del índice FM.
Es posible hacer un mapeo de la última a la primera columna LF (i) de un índice i a un índice j , tal que F [j] = L [i] , con la ayuda de una tabla C [c] y una función Occ (c, k) .
|
|
El mapeo del último al primero ahora se puede definir como LF (i) = C [L [i]] + Occ (L [i], i) . Por ejemplo, en la fila 9, L es a y la misma a se puede encontrar en la fila 5 en la primera columna F , por lo que LF (9) debería ser 5 y LF (9) = C [a] + Occ (a, 9 ) = 5 . Para cualquier fila i de la matriz, el carácter de la última columna L [i] precede al carácter de la primera columna F [i] también en T. Finalmente, si L [i] = T [k] , entonces L [LF (i)] = T [k - 1] , y el uso de la igualdad es posible extraer una cadena de T a partir de L . El índice FM en sí mismo es una compresión de la cadena L junto con C y Occ de alguna forma, así como información que asigna una selección de índices en L a posiciones en la cadena T original . |
|
Contar
La operación de recuento toma un patrón P [1..p] y devuelve el número de ocurrencias de ese patrón en el texto original T . Dado que las filas de la matriz M están ordenadas y contiene todos los sufijos de T , las apariciones del patrón P estarán una al lado de la otra en un solo rango continuo. La operación itera hacia atrás sobre el patrón. Para cada carácter del patrón, se encuentra el rango que tiene el carácter como sufijo. Por ejemplo, el recuento del patrón "sujetador" en "abracadabra" sigue estos pasos:
- El primer carácter que buscamos es a , el último carácter del patrón. El rango inicial se establece en [C [a] + 1..C [a + 1]] = [2..6] . Este rango sobre L representa cada carácter de T que tiene un sufijo que comienza con a .
- El siguiente carácter a buscar es r . El nuevo rango es [C [r] + Occ (r, start-1) + 1..C [r] + Occ (r, end)] = [10 + 0 + 1..10 + 2] = [11 ..12] , si start es el índice del comienzo del rango y end es el final. Este rango sobre L son todos los caracteres de T que tienen sufijos que comienzan con ra .
- El último carácter a mirar es b . El nuevo rango es [C [b] + Occ (b, start-1) + 1..C [b] + Occ (b, end)] = [6 + 0 + 1..6 + 2] = [7 ..8] . Este rango sobre L son todos los caracteres que tienen un sufijo que comienza con sujetador . Ahora que se ha procesado todo el patrón, el recuento es el mismo que el tamaño del rango: 8 - 7 + 1 = 2 .
Si el rango se vacía o los límites del rango se cruzan entre sí antes de que todo el patrón se ha mirado hacia arriba, el patrón no se produce en T . Debido a que Occ (c, k) se puede realizar en tiempo constante, el recuento se puede completar en tiempo lineal en la longitud del patrón: O (p) tiempo.
Localizar
La operación localizar toma como entrada un índice de un carácter en L y devuelve su posición i en T . Por ejemplo, ubique (7) = 8 . Para ubicar cada ocurrencia de un patrón, primero se encuentra el rango de carácter cuyo sufijo es el patrón de la misma manera que la operación de conteo encontró el rango. Entonces se puede ubicar la posición de cada carácter en el rango.
Para asignar un índice en L a uno en T , un subconjunto de los índices en L están asociados con una posición en T . Si L [j] tiene una posición asociada, localizar (j) es trivial. Si no está asociado, la cadena se sigue con LF (i) hasta que se encuentra un índice asociado. Al asociar un número adecuado de índices, se puede encontrar un límite superior. Localizar puede ser implementado para encontrar occ ocurrencias de un patrón P [1..p] en un texto T [1..u] en O (p + occ log ε u) tiempo conbits por símbolo de entrada para cualquier k ≥ 0 . [1]
Aplicaciones
Mapeo de lectura de ADN
El índice de FM con retroceso se ha aplicado con éxito (> 2000 citas) para la coincidencia aproximada de cadenas / alineación de secuencias, consulte Bowtie http://bowtie-bio.sourceforge.net/index.shtml
Ver también
Referencias
- ↑ a b c Paolo Ferragina y Giovanni Manzini (2000). "Estructuras de datos oportunistas con aplicaciones". Actas del 41º Simposio Anual sobre Fundamentos de las Ciencias de la Computación. p. 390.
- ^ Paolo Ferragina y Giovanni Manzini (2005). "Indexación de texto comprimido". Journal of the ACM, 52, 4 (julio de 2005). pag. 553
- ^ Ferragina, Paolo; Venturini, Rossano (septiembre de 2005). "Fm-index versión 2" . www.di.unipi.it . Dipartimento di Informatica, Universidad de Pisa, Italia . Consultado el 15 de agosto de 2018 .
- ↑ P. Ferragina, G. Manzini, V. Mäkinen y G. Navarro. Un índice FM compatible con el alfabeto. En Proc. SPIRE'04 , páginas 150-160. LNCS 3246.
- ^ Simpson, Jared T .; Durbin, Richard (15 de junio de 2010). "Construcción eficiente de un gráfico de cadena de ensamblaje utilizando el índice FM" . Bioinformática . 26 (12): i367 – i373. doi : 10.1093 / bioinformatics / btq217 . ISSN 1367-4803 . PMC 2881401 . PMID 20529929 .