stringtranslate.com

Transformación de Burrows-Wheeler

La transformación de Burrows-Wheeler ( BWT , también llamada compresión de clasificación de bloques ) reorganiza una cadena de caracteres en series de caracteres similares. Esto es útil para la compresión, ya que tiende a ser fácil comprimir una cadena que tiene series de caracteres repetidos mediante técnicas como la transformación de movimiento al frente y la codificación de longitud de ejecución . Más importante aún, la transformación es reversible , sin necesidad de almacenar ningún dato adicional excepto la posición del primer carácter original. El BWT es, por tanto, un método "gratuito" para mejorar la eficiencia de los algoritmos de compresión de texto, y sólo cuesta un poco de cálculo adicional. La transformada de Burrows-Wheeler es un algoritmo que se utiliza para preparar datos para su uso con técnicas de compresión de datos como bzip2 . Fue inventado por Michael Burrows y David Wheeler en 1994 mientras Burrows trabajaba en el Centro de Investigación de Sistemas DEC en Palo Alto , California. Se basa en una transformación inédita descubierta por Wheeler en 1983. El algoritmo se puede implementar de manera eficiente utilizando una matriz de sufijos, alcanzando así una complejidad de tiempo lineal. [1]

Descripción

Cuando BWT transforma una cadena de caracteres , la transformación permuta el orden de los caracteres. Si la cadena original tenía varias subcadenas que ocurrían con frecuencia, entonces la cadena transformada tendrá varios lugares donde un solo carácter se repite varias veces seguidas.

Por ejemplo:

La salida es más fácil de comprimir porque tiene muchos caracteres repetidos. En este ejemplo, la cadena transformada contiene seis series de caracteres idénticos: XX, SS, PP, .., IIy III, que en conjunto suman 13 de los 44 caracteres.

Ejemplo

La transformación se realiza ordenando todos los desplazamientos circulares de un texto en orden lexicográfico y extrayendo la última columna y el índice de la cadena original en el conjunto de permutaciones ordenadas de S.

Dada una cadena de entrada (paso 1 en la siguiente tabla), gírela N veces (paso 2), donde está la longitud de la cadena considerando también el carácter rojo que representa el inicio de la cadena y el carácter rojo que representa el puntero ' EOF ' ; Estas rotaciones, o desplazamientos circulares, se ordenan luego lexicográficamente (paso 3). La salida de la fase de codificación es la última columna después del paso 3 y el índice (basado en 0) de la fila que contiene la cadena original , en este caso . S = ^BANANA$N = 8S^$L = BNN^AA$AISI = 6

No es necesario usar ambos $y ^, pero se debe usar al menos uno; de lo contrario, no podemos invertir la transformada, ya que todas las permutaciones circulares de una cadena tienen la misma transformada de Burrows-Wheeler.

El siguiente pseudocódigo proporciona una forma sencilla (aunque ineficiente) de calcular el BWT y su inverso. Se supone que la cadena de entrada scontiene un carácter especial 'EOF' que es el último carácter y no aparece en ningún otro lugar del texto.

función BWT ( cadena s) crear una tabla, donde las filas son todas las rotaciones posibles de s ordenar filas alfabéticamente retorno (última columna de la tabla)
función inversaBWT ( cadena s) crear tabla vacía repetir longitud(es) veces // la primera inserción crea la primera columna inserte s como una columna de la tabla antes de la primera columna de la tabla ordenar filas de la tabla alfabéticamente return (fila que termina con el carácter 'EOF')

Explicación

Para comprender por qué esto crea datos más fáciles de comprimir, considere transformar un texto largo en inglés que frecuentemente contenga la palabra "the". Ordenar las rotaciones de este texto agrupará las rotaciones que comiencen con "él", y el último carácter de esa rotación (que también es el carácter antes de "él") generalmente será "t", por lo que el resultado de la transformación contendrá una cantidad de caracteres "t" junto con excepciones quizás menos comunes (como si contiene "ache") mezclados. Por lo tanto, se puede ver que el éxito de esta transformación depende de que un valor tenga una alta probabilidad de ocurrir antes una secuencia, de modo que en general necesita muestras bastante largas (al menos unos pocos kilobytes) de datos apropiados (como texto).

Lo destacable del BWT no es que genera una salida codificada más fácilmente (una clasificación normal haría eso) sino que lo hace de manera reversible , permitiendo que el documento original se vuelva a generar a partir de los datos de la última columna.

Lo inverso se puede entender de esta manera. Tome la tabla final del algoritmo BWT y borre toda la columna excepto la última. Con solo esta información, puedes reconstruir fácilmente la primera columna. La última columna le indica todos los caracteres del texto, así que simplemente ordene estos caracteres alfabéticamente para obtener la primera columna. Luego, la última y la primera columna (de cada fila) juntas le brindan todos los pares de caracteres sucesivos en el documento, donde los pares se toman cíclicamente para que el último y el primer carácter formen un par. Al ordenar la lista de pares se obtienen la primera y la segunda columna. Siguiendo de esta manera, podrás reconstruir la lista completa. Entonces, la fila con el carácter "fin de archivo" al final es el texto original. Revertir el ejemplo anterior se hace así:

Mejoramiento

Varias optimizaciones pueden hacer que estos algoritmos se ejecuten de manera más eficiente sin cambiar el resultado. No es necesario representar la tabla ni en el codificador ni en el decodificador. En el codificador, cada fila de la tabla se puede representar mediante un único puntero en las cadenas y la clasificación se puede realizar mediante índices. En el decodificador, tampoco es necesario almacenar la tabla y, de hecho, no es necesario ordenarla en absoluto. En un tiempo proporcional al tamaño del alfabeto y la longitud de la cadena, la cadena decodificada puede generarse un carácter a la vez, de derecha a izquierda. Un "carácter" en el algoritmo puede ser un byte, un bit o cualquier otro tamaño conveniente.

También se puede hacer la observación de que matemáticamente, la cadena codificada se puede calcular como una simple modificación de la matriz de sufijos , y las matrices de sufijos se pueden calcular con tiempo lineal y memoria. El BWT se puede definir con respecto a la matriz de sufijos SA del texto T como (indexación basada en 1):

[3]

No es necesario tener un carácter 'EOF' real. En su lugar, se puede utilizar un puntero que recuerde en qué parte de una cadena estaría el 'EOF' si existiera. En este enfoque, la salida del BWT debe incluir tanto la cadena transformada como el valor final del puntero. La transformación inversa luego lo reduce al tamaño original: se le proporciona una cadena y un puntero, y devuelve solo una cadena.

Se puede encontrar una descripción completa de los algoritmos en el artículo de Burrows y Wheeler, o en varias fuentes en línea. [1] Los algoritmos varían un poco según si se utiliza EOF y en qué dirección se realizó la clasificación. De hecho, la formulación original no utilizaba un marcador EOF. [4]

Variante biyectiva

Dado que cualquier rotación de la cadena de entrada conducirá a la misma cadena transformada, el BWT no se puede invertir sin agregar un marcador EOF al final de la entrada o hacer algo equivalente, lo que permitirá distinguir la cadena de entrada de todas sus rotaciones. Aumentar el tamaño del alfabeto (añadiendo el carácter EOF) hace que los pasos de compresión posteriores sean incómodos.

Existe una versión biyectiva de la transformación, mediante la cual la cadena transformada identifica de forma única la original, y las dos tienen la misma longitud y contienen exactamente los mismos caracteres, solo que en un orden diferente. [5] [6]

La transformada biyectiva se calcula factorizando la entrada en una secuencia no creciente de palabras Lyndon ; tal factorización existe y es única según el teorema de Chen-Fox-Lyndon , [7] y puede encontrarse en tiempo lineal y espacio constante. [8] El algoritmo ordena las rotaciones de todas las palabras; Al igual que en la transformada de Burrows-Wheeler, esto produce una secuencia ordenada de n cadenas. Luego, la cadena transformada se obtiene seleccionando el carácter final de cada cadena en esta lista ordenada. La única advertencia importante aquí es que las cadenas de diferentes longitudes no están ordenadas de la forma habitual; las dos cadenas se repiten para siempre y las repeticiones infinitas se ordenan. Por ejemplo, "ORO" precede a "OR" porque "OROORO..." precede a "OROROR...".

Por ejemplo, el texto " ^ BANANA $ " se transforma en "ANNBAA ^ $ " mediante estos pasos (el carácter $ rojo indica el puntero EOF ) en la cadena original. El carácter EOF no es necesario en la transformación biyectiva, por lo que se elimina durante la transformación y se vuelve a agregar a su lugar apropiado en el archivo.

La cadena se divide en palabras Lyndon, por lo que las palabras de la secuencia disminuyen utilizando el método de comparación anterior. (Tenga en cuenta que estamos clasificando ' ^ ' como caracteres posteriores a otros caracteres). " ^ BANANA" se convierte en ( ^ ) (B) (AN) (AN) (A).

Hasta el último paso, el proceso es idéntico al proceso inverso de Burrows-Wheeler, pero aquí no necesariamente dará rotaciones de una sola secuencia; en su lugar, proporciona rotaciones de palabras de Lyndon (que comenzarán a repetirse a medida que continúe el proceso). Aquí podemos ver (repeticiones de) cuatro palabras Lyndon distintas: (A), (AN) (dos veces), (B) y ( ^ ). (NANA... no representa una palabra distinta, ya que es un ciclo de ANAN....) En este punto, estas palabras están ordenadas en orden inverso: ( ^ ), (B), (AN), ( AN), (A). Luego se concatenan para obtener

^ PLÁTANO

De hecho, la transformada de Burrows-Wheeler puede verse como un caso especial de esta transformada biyectiva; en lugar de la tradicional introducción de una nueva letra fuera de nuestro alfabeto para indicar el final de la cadena, podemos introducir una nueva letra que se compare como precedente a todas las letras existentes que se colocan al principio de la cadena. La cadena completa ahora es una palabra de Lyndon y, al ejecutarla a través del proceso biyectivo, se obtendrá un resultado transformado que, cuando se invierte, devuelve la palabra de Lyndon, sin necesidad de volver a ensamblarla al final.

De manera relacionada, el texto transformado solo diferirá del resultado de BWT en un carácter por palabra Lyndon; por ejemplo, si la entrada se descompone en seis palabras Lyndon, la salida solo diferirá en seis caracteres. Por ejemplo, aplicando la transformación biyectiva se obtiene:

La transformación biyectiva incluye ocho series de caracteres idénticos. Estas ejecuciones son, en orden: XX, II, XX, PP, .., EE, ..y IIII.

En total, en estas ejecuciones se utilizan 18 caracteres.

Transformación dinámica de Burrows-Wheeler

Cuando se edita un texto, su transformación de Burrows-Wheeler cambiará. Salson et al. [9] proponen un algoritmo que deduce la transformada de Burrows-Wheeler de un texto editado a partir del texto original, realizando un número limitado de reordenamientos locales en la transformada de Burrows-Wheeler original, que puede ser más rápido que construir la transformada de Burrows-Wheeler. del texto editado directamente.

Implementación de muestra

Esta implementación de Python sacrifica la velocidad por la simplicidad: el programa es corto, pero requiere más tiempo que el lineal que se desearía en una implementación práctica. Básicamente hace lo que hace la sección de pseudocódigo.

Usando los códigos de control STX/ETX para marcar el inicio y el final del texto, y usando s[i:] + s[:i]para construir la ienésima rotación de s, la transformación directa toma el último carácter de cada una de las filas ordenadas:

def  bwt ( s :  str )  ->  str : """Aplicar la transformación de Burrows-Wheeler a la cadena de entrada.""" afirmar " \002 " no en s y " \003 " no en s , "La cadena de entrada no puede contener STX y Caracteres ETX" s = " \002 " + s + " \003 " # Agregar inicio y final de la tabla de marcadores de texto = ordenado ( s [ i :] + s [: i ] para i en el rango ( len ( s ))) # Tabla de rotaciones de cadena last_column = [ fila [ - 1 :] para fila en la tabla ] # Los últimos caracteres de cada fila devuelven "" . unirse ( última_columna ) # Convertir lista de caracteres en cadena

La transformación inversa se inserta repetidamente rcomo la columna izquierda de la tabla y ordena la tabla. Una vez creada toda la tabla, devuelve la fila que termina con ETX, menos STX y ETX.

def  inverse_bwt ( r :  str )  ->  str : """Aplicar la transformación inversa de Burrows-Wheeler.""" table = [ "" ] * len ( r ) # Crear una tabla vacía para _ en el rango ( len ( r )): tabla = ordenado ( r [ i ] + tabla [ i ] para i en el rango ( len ( r ))) # Agregar una columna de r                      s  =  next (( fila  por  fila  en  la tabla  si  la fila . termina con ( " \003 " )),  "" )  # Iterar y verificar si el último carácter termina con ETX o no  devolver  s . rstrip ( " \003 " ) . strip ( " \002 " )  # Recuperar datos de la matriz y eliminar los marcadores de inicio y fin

Siguiendo las notas de implementación de Manzini, es equivalente a utilizar un sufijo de carácter nulo simple . La clasificación debe realizarse en orden colexicográfico (la cadena se lee de derecha a izquierda), es decir, sorted(..., key=lambda s: s[::-1])en Python. [4] (Los códigos de control anteriores en realidad no cumplen con que EOF sea el último carácter; los dos códigos son en realidad el primero . Sin embargo, la rotación se mantiene).

Aplicaciones BWT

Como algoritmo de compresión sin pérdidas, la transformada de Burrows-Wheeler ofrece la importante cualidad de que su codificación es reversible y, por tanto, los datos originales pueden recuperarse a partir de la compresión resultante. La calidad sin pérdidas del algoritmo de Burrows ha proporcionado diferentes algoritmos con diferentes propósitos en mente. Por nombrar algunos, la transformada de Burrows-Wheeler se utiliza en algoritmos de alineación de secuencias , compresión de imágenes , compresión de datos , etc. La siguiente es una recopilación de algunos usos dados a la transformada de Burrows-Wheeler.

BWT para alineación de secuencias

La llegada de las técnicas de secuenciación de próxima generación (NGS) a finales de la década de 2000 ha llevado a otra aplicación de la transformación de Burrows-Wheeler. En NGS, el ADN se fragmenta en pequeños fragmentos, de los cuales se secuencian las primeras bases , lo que produce varios millones de "lecturas", cada una de 30 a 500 pares de bases ("caracteres de ADN") de largo. En muchos experimentos, por ejemplo en ChIP-Seq , la tarea ahora es alinear estas lecturas con un genoma de referencia , es decir, con la secuencia conocida y casi completa del organismo en cuestión (que puede tener hasta varios miles de millones de pares de bases de largo). . Se publicaron varios programas de alineación especializados para esta tarea, que inicialmente se basaban en hash (por ejemplo, Eland, SOAP, [10] o Maq [11] ). En un esfuerzo por reducir el requisito de memoria para la alineación de secuencias, se desarrollaron varios programas de alineación ( Bowtie , [12] BWA, [13] y SOAP2 [14] ) que utilizan la transformada de Burrows-Wheeler.

BWT para compresión de imágenes

La transformación de Burrows-Wheeler ha demostrado ser fundamental para aplicaciones de compresión de imágenes . Por ejemplo, [15] mostró un proceso de compresión basado en la aplicación de la transformación de Burrows-Wheeler seguida de codificadores aritméticos, de longitud de ejecución y de inversión. El proceso desarrollado en este caso se conoce como transformada de Burrows-Wheeler con codificador de inversión (BWIC). Los resultados mostrados por BWIC superan el rendimiento de compresión de algoritmos conocidos y ampliamente utilizados como Lossless JPEG y JPEG 2000 . Se ha demostrado que BWIC supera a aquellos en términos de tamaño de compresión final de imágenes médicas de radiografía del orden de 5,1% y 4,1% respectivamente. Las mejoras se logran combinando BWIC y un escaneo previo a BWIC de la imagen en orden de serpiente vertical. Más recientemente, trabajos adicionales como el de [16] han demostrado que la implementación de la Transformada de Burrows-Wheeler junto con la conocida transformación de movimiento hacia el frente (MTF) logra una compresión de imágenes casi sin pérdidas.

BWT para la compresión de bases de datos genómicas.

Cox y cols. [17] presentaron un esquema de compresión genómica que utiliza BWT como algoritmo aplicado durante la primera etapa de compresión de varios conjuntos de datos genómicos, incluida la información genómica humana. Su trabajo propuso que la compresión BWT podría mejorarse incluyendo un mecanismo de compresión de segunda etapa llamado codificación igual que la anterior ("SAP"), que aprovecha el hecho de que los sufijos de dos o más letras de prefijo podrían ser iguales. Con el mecanismo de compresión BWT-SAP, Cox et al. mostró que en la base de datos genómica ERA015743, de 135,5 GB de tamaño, el esquema de compresión BWT-SAP comprime el conjunto de datos ERA015743 en aproximadamente un 94%, a 8,2 GB.

BWT para predicción de secuencias

También se ha demostrado que BWT es útil en la predicción de secuencias, que es un área de estudio común en el aprendizaje automático y el procesamiento del lenguaje natural . En particular, Ktistakis et al. [18] propusieron un esquema de predicción de secuencia llamado SuBSeq que explota la compresión sin pérdidas de datos de la transformada de Burrows-Wheeler. SuBSeq explota BWT extrayendo el índice FM y luego realizando una serie de operaciones denominadas backSearch, forwardSearch, neighbourExpansion y getConsequents para buscar predicciones dado un sufijo . Luego, las predicciones se clasifican en función de un peso y se colocan en una matriz a partir de la cual el elemento con el peso más alto se proporciona como predicción del algoritmo SuBSeq. Se ha demostrado que SuBSeq supera a los algoritmos de última generación para la predicción de secuencias tanto en términos de tiempo de entrenamiento como de precisión.

Referencias

  1. ^ ab Burrows, Michael ; Wheeler, David J. (10 de mayo de 1994), Un algoritmo de compresión de datos sin pérdidas de clasificación por bloques, Informe técnico 124, Digital Equipment Corporation, archivado desde el original el 5 de enero de 2003.
  2. ^ "adrien-mogenet/scala-bwt". GitHub . Consultado el 19 de abril de 2018 .
  3. ^ Simpson, Jared T.; Durbin, Richard (15 de junio de 2010). "Construcción eficiente de un gráfico de cadenas de ensamblaje utilizando el índice FM". Bioinformática . 26 (12): i367-i373. doi : 10.1093/bioinformática/btq217. ISSN  1367-4803. PMC 2881401 . PMID  20529929. 
  4. ^ ab Manzini, Giovanni (18 de agosto de 1999). "La transformación de Burrows-Wheeler: teoría y práctica" (PDF) . Fundamentos matemáticos de la informática 1999: 24º Simposio internacional, MFCS'99 Szklarska Poreba, Polonia, 6 al 10 de septiembre de 1999 Actas . Medios de ciencia y negocios de Springer. ISBN 9783540664086. Archivado (PDF) desde el original el 9 de octubre de 2022.
  5. ^ Gil, J.; Scott, DA (2009), Una transformación de clasificación de cadenas biyectivas (PDF) , archivado desde el original (PDF) el 8 de octubre de 2011 , consultado el 9 de julio de 2009.
  6. ^ Kufleitner, Manfred (2009), "Sobre variantes biyectivas de la transformada de Burrows-Wheeler", en Holub, enero; Žďárek, Jan (eds.), Conferencia de Stringología de Praga, págs. 65–69, arXiv : 0908.0239 , Bibcode :2009arXiv0908.0239K.
  7. ^ * Lothaire, M. (1997), Combinatoria de palabras , Enciclopedia de las matemáticas y sus aplicaciones, vol. 17, Perrin, D.; Reutenauer, C.; Berstel, J.; Alfiler, JE; Pirillo, G.; Foata, D.; Sakarovich, J.; Simón, yo; Schützenberger, diputado; Choffrut, C.; Cori, R.; Lyndon, Roger; Rota, Gian-Carlo. Prólogo de Roger Lyndon (2ª ed.), Cambridge University Press , pág. 67, ISBN 978-0-521-59924-5, Zbl  0874.20040
  8. ^ Duval, Jean-Pierre (1983), "Factorización de palabras sobre un alfabeto ordenado", Journal of Algorithms , 4 (4): 363–381, doi :10.1016/0196-6774(83)90017-2, ISSN  0196-6774 , Zbl  0532.68061.
  9. ^ Salson M, Lecroq T, Léonard M, Mouchard L (2009). "Un algoritmo de cuatro etapas para actualizar una transformada de Burrows-Wheeler". Informática Teórica . 410 (43): 4350–4359. doi : 10.1016/j.tcs.2009.07.016 .
  10. ^ Li R; et al. (2008). "SOAP: programa corto de alineación de oligonucleótidos". Bioinformática . 24 (5): 713–714. doi : 10.1093/bioinformática/btn025 . PMID  18227114.
  11. ^ Li H, Ruan J, Durbin R (19 de agosto de 2008). "Mapeo de lecturas cortas de secuenciación de ADN y llamadas de variantes utilizando puntuaciones de calidad de mapeo". Investigación del genoma . 18 (11): 1851–1858. doi :10.1101/gr.078212.108. PMC 2577856 . PMID  18714091. 
  12. ^ Langmead B, Trapnell C, Pop M, Salzberg SL (2009). "Alineamiento ultrarrápido y con memoria eficiente de secuencias cortas de ADN con el genoma humano". Biología del genoma . 10 (3): R25. doi : 10.1186/gb-2009-10-3-r25 . PMC 2690996 . PMID  19261174. 
  13. ^ Li H, Durbin R (2009). "Alineación de lectura breve rápida y precisa con Burrows-Wheeler Transform". Bioinformática . 25 (14): 1754-1760. doi : 10.1093/bioinformática/btp324. PMC 2705234 . PMID  19451168. 
  14. ^ Li R; et al. (2009). "SOAP2: una herramienta ultrarrápida mejorada para alineación de lecturas breves". Bioinformática . 25 (15): 1966-1967. doi : 10.1093/bioinformática/btp336. PMID  19497933.
  15. ^ Collin P, Arnavut Z, Koc B (2015). "Compresión sin pérdidas de imágenes médicas mediante la transformación de Burrows-Wheeler con Inversion Coder". 2015 37ª Conferencia Internacional Anual de la Sociedad de Ingeniería en Medicina y Biología (EMBC) del IEEE . vol. 2015. págs. 2956–2959. doi :10.1109/EMBC.2015.7319012. ISBN 978-1-4244-9271-8. PMID  26736912. S2CID  4460328.
  16. ^ Devadoss CP, Sankaragomathi B (2019). "Compresión de imágenes médicas casi sin pérdidas utilizando bloques BWT-MTF y técnicas de compresión fractal híbrida". Computación en clúster . 22 : 12929–12937. doi :10.1007/s10586-018-1801-3. S2CID  33687086.
  17. ^ Cox AJ, Bauer MJ, Jakobi T, Rosone G (2012). "Compresión a gran escala de bases de datos de secuencias genómicas con la transformada de Burrows-Wheeler". Bioinformática . 28 (11). Prensa de la Universidad de Oxford: 1415-1419. arXiv : 1205.0192 . doi : 10.1093/bioinformática/bts173. PMID  22556365.
  18. ^ Ktistakis R, Fournier-Viger P, Puglisi SJ, Raman R (2019). "Predicción de secuencia sucinta basada en BWT". Aplicaciones de bases de datos y sistemas expertos . Apuntes de conferencias sobre informática. vol. 11707. págs. 91-101. doi :10.1007/978-3-030-27618-8_7. ISBN 978-3-030-27617-1. S2CID  201058996.

enlaces externos