La transformación de Burrows-Wheeler ( BWT , también llamada compresión por clasificación de bloques ) reordena 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 ejecuciones 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, que cuesta sólo algunos cálculos adicionales.
Clase | preprocesamiento para compresión sin pérdidas |
---|---|
Estructura de datos | cuerda |
Rendimiento en el peor de los casos | En) |
Complejidad espacial en el peor de los casos | En) |
Descripción
- Alineación
- La transformación 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 DEC Systems Research Center 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]
Cuando el 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, la cadena transformada tendrá varios lugares donde un solo carácter se repite varias veces seguidas.
Por ejemplo:
Aporte | SEIS.PIXIES.MIXTAS.SIFT.SESENTA.PIXIE.DUST.BOXES |
---|---|
Producción | TEXYDST.E.IXIXIXXSSMPPS.B..ESEUSFXDIIOIIIT [2] |
La salida es más fácil de comprimir porque tiene muchos caracteres repetidos. En este ejemplo, la cadena transformada contiene seis corridas de caracteres idénticos: XX , SS , PP , .. , II y III , que juntos suman 13 de los 44 caracteres.
Ejemplo
La transformación se realiza mediante la clasificación de todos los desplazamientos circulares de un texto en el orden lexicográfico y mediante la extracción de la última columna y el índice de la cadena original en el conjunto de permutaciones clasificadas de S .
Dada una cadena de entrada S = ^ BANANA | (paso 1 en la siguiente tabla), gírelo N veces (paso 2), donde N = 8 es la longitud de la cadena S considerando también el símbolo ^ que representa el inicio de la cadena y el rojo | carácter que representa el puntero ' EOF '; estas rotaciones, o turnos circulares, luego se ordenan lexicográficamente (paso 3). La salida de la fase de codificación es la última columna L = BNN ^ AA | A después del paso 3, y el índice (basado en 0) I de la fila que contiene la cadena original S , en este caso I = 6 .
Transformación | ||||
---|---|---|---|---|
1. Entrada | 2. Todas las rotaciones | 3. Clasificar en orden léxico | 4. Toma la última columna | 5. Salida |
^ BANANA | | ^ BANANA | | ^ PLÁTANOA | ^ BANANNA | ^ BANAANA | ^ BANNANA | ^ BAANANA | ^ BBANANA | ^ | A NANA | ^ B A NA | ^ BAN A | ^ BANAN B ANANA | ^ N ANA | ^ BA N A | ^ BANA ^ BANANA | | ^ PLÁTANO | ANANA | ^ B ANA | ^ BA N A | ^ BANA N BANANA | ^ NANA | ^ B A NA | ^ BAN A ^ BANANA | | ^ BANAN A | BNN ^ AA | A |
El siguiente pseudocódigo proporciona una forma simple (aunque ineficaz) de calcular el BWT y su inverso. Se asume que la cadena de entrada s
contiene un carácter especial 'EOF' que es el último carácter y no aparece en ninguna otra parte del texto.
función BWT ( cadena s) crear una tabla, donde las filas son todas las posibles rotaciones de s ordenar las filas alfabéticamente return (última columna de la tabla)
función inverseBWT ( cadena s) crear mesa vacía repetir longitud (s) 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 las 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 la posibilidad de transformar un texto largo en inglés que contenga frecuentemente la palabra "the". Al ordenar las rotaciones de este texto se agruparán las rotaciones que comienzan con "él", y el último carácter de esa rotación (que también es el carácter antes de "él") normalmente será "t", por lo que el resultado de la transformación contendría una cantidad de caracteres "t" junto con las excepciones quizás menos comunes (como si contiene "dolor") mezcladas. 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 (unos pocos kilobytes al menos) de datos apropiados (como texto).
Lo notable de BWT no es que genera una salida codificada más fácilmente (una clasificación ordinaria haría eso) sino que lo hace de manera reversible , lo que permite que el documento original se vuelva a generar a partir de los datos de la última columna.
La inversa se puede entender de esta manera. Tome la tabla final en el algoritmo BWT y borre todas las columnas excepto la última. Dada solo esta información, puede reconstruir fácilmente la primera columna. La última columna le dice todos los caracteres en el 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. Continuando de esta manera, puede reconstruir la lista completa. Luego, la fila con el carácter de "fin de archivo" al final es el texto original. Invertir el ejemplo anterior se hace así:
Transformación inversa | |||
---|---|---|---|
Aporte | |||
BNN ^ AA | A | |||
Agregar 1 | Clasificar 1 | Suma 2 | Ordenar 2 |
Bnortenorte^AA|A | AAABnortenorte^| | licenciado en LetrasN / AN / A^ BUNUN| ^A | | UNUNA |licenciado en LetrasN / AN / A^ B| ^ |
Suma 3 | Ordenar 3 | Suma 4 | Ordenar 4 |
PROHIBICIÓNYAYANA |^ BAANAANA| ^ BA | ^ | ANAANAA | ^PROHIBICIÓNYAYANA |^ BA| ^ B | BANANANANA | ^^ BANANANANA | | ^ BAA | ^ B | ANANANA | A | ^ BBANANANANA | ^^ BAN| ^ BA |
Suma 5 | Ordenar 5 | Suma 6 | Ordenar 6 |
BANANNANA | NA | ^ B^ BANAANANAANA | ^ | ^ BANA | ^ BA | ANANAANA | ^A | ^ BABANANNANA | NA | ^ B^ BANA| ^ BAN | PLÁTANONANA | ^NA | ^ BA^ BANANANANA | ANA | ^ B | ^ BANAA | ^ BAN | ANANA | ANA | ^ BA | ^ BANPLÁTANONANA | ^NA | ^ BA^ BANAN| ^ BANA |
Suma 7 | Ordenar 7 | Suma 8 | Ordenar 8 |
BANANA | NANA | ^ BNA | ^ BAN^ PLÁTANOANANA | ^ANA | ^ BA | ^ BANANA | ^ BANA | ANANA | ^ANA | ^ BAA | ^ BANABANANA | NANA | ^ BNA | ^ BAN^ PLÁTANO| ^ BANAN | BANANA | ^NANA | ^ BANA | ^ BANA^ BANANA | ANANA | ^ BANA | ^ BAN | ^ PLÁTANOA | ^ BANAN | ANANA | ^ BANA | ^ BANA | ^ BANANBANANA | ^NANA | ^ BANA | ^ BANA^ BANANA | | ^ PLÁTANO |
Producción | |||
^ BANANA | |
Mejoramiento
Varias optimizaciones pueden hacer que estos algoritmos se ejecuten de manera más eficiente sin cambiar la salida. No es necesario representar la tabla ni en el codificador ni en el descodificador. En el codificador, cada fila de la tabla se puede representar con un solo puntero en las cadenas, y la clasificación se puede realizar utilizando los índices. En el decodificador, tampoco es necesario almacenar la tabla y, de hecho, no se necesita ningún tipo de clasificación. En un tiempo proporcional al tamaño del alfabeto y la longitud de la cadena, la cadena decodificada se puede generar 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):
No es necesario tener un carácter 'EOF' real. En su lugar, se puede usar 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 da 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 se utilice EOF y en qué dirección se realizó la clasificación. De hecho, la formulación original no utilizó 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 permite distinguir la cadena de entrada de todas sus rotaciones. Aumentar el tamaño del alfabeto (agregando el carácter EOF) hace que los pasos de compresión posteriores resulten incómodos.
Existe una versión biyectiva de la transformación, mediante la cual la cadena transformada identifica de forma única al 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 de Lyndon ; tal factorización existe y es única por el teorema de Chen-Fox-Lyndon , [7] y puede encontrarse en tiempo lineal. [8] El algoritmo ordena las rotaciones de todas las palabras; como en la transformada de Burrows-Wheeler, esto produce una secuencia ordenada de n cadenas. 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 se ordenan de la forma habitual; las dos cadenas se repiten para siempre y las repeticiones infinitas se ordenan. Por ejemplo, "ORO" precede a "O" 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 adecuado en el archivo.
La cadena se divide en palabras de Lyndon, por lo que las palabras de la secuencia disminuyen utilizando el método de comparación anterior. (Tenga en cuenta que estamos ordenando '^' como sucesos de otros caracteres). "^ BANANA" se convierte en (^) (B) (AN) (AN) (A).
Transformación biyectiva | ||||
---|---|---|---|---|
Aporte | Todas las rotaciones | Ordenados alfabéticamente | Última columna de la palabra Lyndon rotada | Producción |
^ BANANA | | ^ ^^^^^^^ ... (^) B BBBBBBB ... (B) ANAN ANAN ... (AN) NANA NANA ... (NA) ANAN ANAN ... (AN) NANA NANA .. . (NA) A AAAAAAA ... (A) | A AAAAAAA ... (A) A NANANAN ... (AN) A NANANAN ... (AN) B BBBBBBB ... (B) N ANANANA ... (NA) N ANANANA ... (NA) ^ ^ ^^^^^^ ... (^) | A AAAAAAA ... ( A )A N ANANAN ... (A N )A N ANANAN ... (A N ) B BBBBBBB ... ( B )N A NANANA ... (N A )N A NANANA ... (N A ) ^ ^^^^^^^ ... ( ^ ) | ANNBAA ^ | |
Transformada biyectiva inversa | |||
---|---|---|---|
Aporte | |||
ANNBAA ^ | |||
Agregar 1 | Clasificar 1 | Suma 2 | Ordenar 2 |
AnortenorteBAA^ | AAABnortenorte^ | Automóvil club británicoN / AN / Acama y desayunoUNUN^^ | Automóvil club británicoUNUNcama y desayunoN / AN / A^^ |
Suma 3 | Ordenar 3 | Suma 4 | Ordenar 4 |
AAAYAYAYAYABBBANAANA^^^ | AAAANAANABBBYAYAYAYA^^^ | AAAANANANANABBBBANANANAN^^^^ | AAAAANANANANBBBBNANANANA^^^^ |
Producción | |||
^ PLÁTANO |
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, da 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). Estos 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 introducción tradicional de una nueva letra de fuera de nuestro alfabeto para denotar el final de la cadena, podemos introducir una nueva letra que se compara como precedente a todas las letras existentes que se coloca al principio de la cadena. Toda la cadena es ahora una palabra Lyndon, y ejecutarla a través del proceso biyectivo dará como resultado un resultado transformado que, cuando se invierte, devuelve la palabra Lyndon, sin necesidad de volver a ensamblar 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, la aplicación de la transformación biyectiva da:
Aporte | SEIS.PIXIES.MIXTAS.SIFT.SESENTA.PIXIE.DUST.BOXES |
---|---|
Palabras de Lyndon | S IX .PIXIES.MIXTAS.SIFT.SIXTY.PIXIE .CUADROS DE POLVO |
Producción | STEYDST.E.IXXIIXXSMPPXS.B..EE..SUSFXDIOIIIIT |
La transformación biyectiva incluye ocho ejecuciones de caracteres idénticos. Estas ejecuciones son, en orden: XX , II , XX , PP , .. , EE , .. y IIII .
En total, se utilizan 18 caracteres en estas ejecuciones.
Transformada dinámica de Burrows-Wheeler
Cuando se edita un texto, su transformación Burrows-Wheeler cambiará. Salson y col. [9] proponen un algoritmo que deduce la transformada de Burrows-Wheeler de un texto editado del texto original, haciendo 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 toma 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 i
rotación de s
, la transformación hacia adelante toma el último carácter de cada una de las filas ordenadas:
def bwt ( s : str ) -> str : "" "Aplicar Burrows-Wheeler transformar a la cadena de entrada" "" afirman " \ 002 " no en s y " \ 003 " no en s , "cadena de entrada no puede contener STX y Caracteres ETX " s = " \ 002 " + s + " \ 003 " # Agregar el inicio y el final de la tabla de marcadores de texto = ordenados ( s [ i :] + s [: i ] para i en el rango ( len ( s ))) # Tabla de rotaciones de la cadena last_column = [ fila [ - 1 :] para la fila en la tabla ] # Los últimos caracteres de cada fila devuelven "" . join ( last_column ) # Convertir lista de caracteres en cadena
La transformación inversa se inserta repetidamente r
como la columna izquierda de la tabla y ordena la tabla. Una vez construida toda la tabla, devuelve la fila que termina con ETX, menos STX y ETX.
def ibwt ( r : str ) -> str : "" "Aplicar la transformación inversa de Burrows-Wheeler." "" table = [ "" ] * len ( r ) # Hacer una tabla vacía para i en el rango ( len ( r )): table = sorted ( r [ i ] + table [ i ] para i en rango ( len ( r ))) # Agregar una columna de r s = [ fila para fila en tabla si fila . termina con ( " \ 003 " )] [ 0 ] # Encuentra la fila correcta (terminando en ETX) return s . rstrip ( " \ 003 " ) . strip ( " \ 002 " ) # Deshazte de los marcadores de inicio y fin
Siguiendo las notas de implementación de Manzini, es equivalente usar un sufijo de carácter nulo simple en su lugar. La clasificación debe realizarse en orden colexicográfico (cadena leída de derecha a izquierda), es decir, sorted(..., key=lambda s: s[::-1])
en Python. [4] (Los códigos de control anteriores en realidad no satisfacen que EOF sea el último carácter; los dos códigos son en realidad el primero . No obstante, la rotación se mantiene).
Aplicaciones BWT
Como algoritmo de compresión sin pérdidas , Burrows-Wheeler Transform ofrece la importante calidad de que su codificación es reversible y, por lo tanto, los datos originales pueden recuperarse 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, Burrows Wheeler Transform se usa en algoritmos para alineación de secuencias , compresión de imágenes , compresión de datos , etc. La siguiente es una compilación de algunos usos dados a Burrows-Wheeler Transform.
BWT para alineación de secuencia
El advenimiento de las técnicas de secuenciación de próxima generación (NGS) a fines 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 trozos, de los cuales se secuencian las primeras bases , produciendo varios millones de "lecturas", cada una de 30 a 500 pares de bases ("caracteres de ADN") de longitud. 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, 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 las aplicaciones de compresión de imágenes . Por ejemplo, [15] mostró una tubería de compresión basada en la aplicación de la transformación Burrows-Wheeler seguida de codificadores de inversión, longitud de ejecución y aritmética. La tubería desarrollada en este caso se conoce como Transformación de Burrows-Wheeler con un codificador de inversión (BWIC). Se muestra que 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 Lossless_JPEG y JPEG_2000 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 pre-BWIC de la imagen en un 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 Transformada Move-to-front (MTF) logran una compresión de imágenes casi sin pérdidas.
BWT para la compresión de bases de datos genómicas
Cox y col. [17] presentó 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 mediante la inclusión de un mecanismo de compresión de segunda etapa llamado "SAP" o codificación igual a la anterior que hace uso del 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. Demostró que en la base de datos genómica ERA015743, que tiene un tamaño de 135,5 Gb, el esquema de compresión BWT-SAP logra una reducción de ~ 94% del espacio al llevar el tamaño del conjunto de datos ERA015743 a 8,2 Gb de espacio en disco.
BWT para compresión de datos
Se han realizado varios trabajos en relación con el cálculo de versiones comprimidas de texto común utilizando la Transformada de Burrows-Wheeler. Por ejemplo, Rahman y Hamada [18] desarrollaron una metodología novedosa que implementa una partición de archivos en piezas más pequeñas de igual longitud que en una primera etapa se comprimen mediante BWT. Luego, dependiendo de la repetición de los caracteres en cualquier archivo de texto dado, el algoritmo decide reemplazar los caracteres repetidos por dos claves diferentes que son recuentos y el carácter en sí. El resultado de la codificación del texto en claves se analiza para identificar patrones que luego se explotan comprimiendo aún más los patrones con la ayuda de la codificación Huffman . En su trabajo, Rahman y Hamada muestran cómo su esquema de compresión propuesto supera a los algoritmos de última generación en términos de relación de compresión de datos .
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 común de estudio en el aprendizaje automático y el procesamiento del lenguaje natural . En particular, Ktistakis et al. [19] propuso 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 llamadas backwardSearch, forwardSearch, neighbourExpansion y getConsequents para buscar predicciones con un sufijo . Luego, las predicciones se clasifican en función de un peso y se colocan en una matriz a partir de la cual se da el elemento con el peso más alto como la predicción del algoritmo SuBSeq. Se ha demostrado que SuBSeq supera a los algoritmos de vanguardia para la predicción de secuencias tanto en términos de tiempo de entrenamiento como de precisión.
Referencias
- ^ a b Burrows, Michael ; Wheeler, David J. (1994), algoritmo de compresión de datos sin pérdida de clasificación de bloques , Informe técnico 124, Digital Equipment Corporation
- ^ "adrien-mogenet / scala-bwt" . GitHub . Consultado el 19 de abril de 2018 .
- ^ 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 .
- ^ a b 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, Actas del 6 al 10 de septiembre de 1999 . Springer Science & Business Media. ISBN 9783540664086.
- ^ Gil, J .; Scott, DA (2009), Una transformación de clasificación de cadenas biyectiva (PDF)
- ^ Kufleitner, Manfred (2009), "Sobre variantes biyectivas de la transformada de Burrows-Wheeler", en Holub, Jan; Žďárek, Jan (eds.), Prague Stringology Conference , págs. 65–69, arXiv : 0908.0239 , Bibcode : 2009arXiv0908.0239K.
- ^ * Lothaire, M. (1997), Combinatoria en palabras , Enciclopedia de las matemáticas y sus aplicaciones, 17 , Perrin, D .; Reutenauer, C .; Berstel, J .; Pin, JE; Pirillo, G .; Foata, D .; Sakarovitch, J .; Simon, I .; 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
- ^ Duval, Jean-Pierre (1983), "Factorizar 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.
- ^ Salson M, Lecroq T, Léonard M, Mouchard L (2009). "Un algoritmo de cuatro etapas para actualizar una transformación Burrows-Wheeler". Informática Teórica . 410 (43): 4350–4359. doi : 10.1016 / j.tcs.2009.07.016 .
- ^ Li R; et al. (2008). "SOAP: programa de alineación de oligonucleótidos corto" . Bioinformática . 24 (5): 713–714. doi : 10.1093 / bioinformatics / btn025 . PMID 18227114 .
- ^ Li H, Ruan J, Durbin R (19 de agosto de 2008). "Mapeo de lecturas de secuenciación de ADN cortas y variantes de llamada utilizando puntuaciones de calidad de mapeo" . Investigación del genoma . 18 (11): 1851–1858. doi : 10.1101 / gr.078212.108 . PMC 2577856 . PMID 18714091 .
- ^ Langmead B, Trapnell C, Pop M, Salzberg SL (2009). "Alineación ultrarrápida y eficiente para la memoria 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 .
- ^ Li H, Durbin R (2009). "Alineación de lectura corta rápida y precisa con Burrows-Wheeler Transform" . Bioinformática . 25 (14): 1754-1760. doi : 10.1093 / bioinformatics / btp324 . PMC 2705234 . PMID 19451168 .
- ^ Li R; et al. (2009). "SOAP2: una herramienta ultrarrápida mejorada para alineación de lectura corta" . Bioinformática . 25 (15): 1966–1967. doi : 10.1093 / bioinformatics / btp336 . PMID 19497933 .
- ^ Collin P, Arnavut Z, Koc B (2015). "Compresión sin pérdida de imágenes médicas mediante la transformación de Burrows-Wheeler con Inversion Coder" . 2015 37th Annual International Conference of the IEEE Engineering in Medicine and Biology Society (EMBC) . 2015 : 2956–2959. doi : 10.1109 / EMBC.2015.7319012 . PMID 26736912 .
- ^ Devadoss CP, Sankaragomathi B (2019). "Compresión de imágenes médicas casi sin pérdidas utilizando técnicas de compresión fractal híbrida y BWT-MTF de bloque" . Computación en clúster . 22 : 12929–12937. doi : 10.1007 / s10586-018-1801-3 .
- ^ Cox AJ, Bauer MJ, Jakobi T, Rosone G (2012). "Compresión sin pérdida de imágenes médicas mediante la transformación de Burrows-Wheeler con Inversion Coder" . Bioinformática . 28 (11): 1415-1419. doi : 10.1109 / EMBC.2015.7319012 .
- ^ Rahman MA, Hamada M (2020). "Compresión de texto sin pérdidas basada en la transformación de Burrows-Wheeler usando claves y codificación Huffman" . Simetría . 12 (10): 1654. doi : 10.3390 / sym12101654 .
- ^ Ktistakis R, Fournier-Viger P, Puglisi SJ, Raman R (2019). "Predicción sucinta de secuencia basada en BWT" . Aplicaciones de bases de datos y sistemas expertos: notas de clase en informática . 11707 (10): 91–101. doi : 10.1007 / 978-3-030-27618-8_7 .
enlaces externos
- Artículo de Mark Nelson en BWT
- Una transformación biyectiva de clasificación de cadenas, por Gil y Scott
- Openbwt-v1.5.zip de Yuta contiene código fuente para varias rutinas BWT, incluido BWTS para la versión biyectiva
- Sobre variantes biyectivas de la transformación Burrows-Wheeler, por Kufleitner
- Publicación de blog y página del proyecto para un programa de compresión de código abierto y una biblioteca basados en el algoritmo de Burrows-Wheeler
- Conferencia de material didáctico abierto del MIT sobre BWT (Fundamentos de la biología computacional y de sistemas)
- Clasificación de la tabla de clasificación (LTS) o el algoritmo de ponderación para BWT de Abderrahim Hechachena (afirma ser más rápido, pero la corrección no está probada)