En informática , un árbol de sufijos generalizados es un árbol de sufijos para un conjunto de cadenas . Dado el conjunto de cuerdas de longitud total , es un árbol de Patricia que contiene todos sufijos de las cadenas. Se utiliza principalmente en bioinformática . [1]
Funcionalidad
Se puede construir en tiempo y espacio, y se puede utilizar para encontrar todos apariciones de una cadena de longitud en tiempo, que es asintóticamente óptimo (asumiendo que el tamaño del alfabeto es constante [2] : 119 ).
Al construir un árbol de este tipo, cada cadena debe rellenarse con un símbolo de marcador (o cadena) único fuera del alfabeto para garantizar que ningún sufijo sea una subcadena de otro, garantizando que cada sufijo esté representado por un nodo hoja único.
Los algoritmos para construir un GST incluyen el algoritmo de Ukkonen (1995) y el algoritmo de McCreight (1976).
Ejemplo
Un árbol de sufijos para las cadenas ABAB
y BABA
se muestra en una figura de arriba. Están acolchados con las exclusivas cadenas de terminación $0
y $1
. Los números en los nodos hoja son el número de cadena y la posición inicial. Observe cómo un recorrido de izquierda a derecha de los nodos hoja corresponde al orden de clasificación de los sufijos. Los terminadores pueden ser cadenas o símbolos únicos únicos. Los bordes $
desde la raíz se omiten en este ejemplo.
Alternativas
Una alternativa a la construcción de un árbol de sufijos generalizados es concatenar las cadenas y construir un árbol de sufijos regular o una matriz de sufijos para la cadena resultante. Cuando se evalúan los aciertos después de una búsqueda, las posiciones globales se mapean en documentos y posiciones locales con algún algoritmo y / o estructura de datos, como una búsqueda binaria en las posiciones inicial / final de los documentos.
Referencias
- ^ Paul Bieganski; John Riedl; John Carlis; Ernest F. Retzel (1994). "Árboles de sufijo generalizado para datos de secuencia biológica". Computación biotecnológica, actas de la vigésimo séptima conferencia internacional de Hawái sobre . págs. 35–44. doi : 10.1109 / HICSS.1994.323593 .
- ^ Gusfield, Dan (1999) [1997]. Algoritmos sobre cadenas, árboles y secuencias: informática y biología computacional . Estados Unidos: Cambridge University Press. ISBN 978-0-521-58519-4.
enlaces externos
- Medios relacionados con el árbol de sufijos generalizados en Wikimedia Commons
- Implementación de CA del árbol de sufijo generalizado para dos cadenas