stringtranslate.com

Análisis de secuencia sin alineamiento

En bioinformática , los enfoques de análisis de secuencias sin alineación para datos de secuencias y estructuras moleculares brindan alternativas a los enfoques basados ​​en alineación. [1]

El surgimiento y la necesidad del análisis de diferentes tipos de datos generados a través de la investigación biológica ha dado lugar al campo de la bioinformática . [2] Los datos de secuencia y estructura molecular de ADN , ARN y proteínas , perfiles de expresión génica o datos de microarrays , datos de vías metabólicas son algunos de los principales tipos de datos que se analizan en bioinformática. Entre ellos, los datos de secuencia están aumentando a un ritmo exponencial debido al advenimiento de las tecnologías de secuenciación de próxima generación. Desde el origen de la bioinformática, el análisis de secuencias ha seguido siendo la principal área de investigación con una amplia gama de aplicaciones en la búsqueda de bases de datos, anotación del genoma , genómica comparativa , filogenia molecular y predicción de genes . Los enfoques pioneros para el análisis de secuencias se basaron en la alineación de secuencias, ya sea global o local, alineación de secuencias por pares o múltiple . [3] [4] Los enfoques basados ​​en la alineación generalmente dan excelentes resultados cuando las secuencias en estudio están estrechamente relacionadas y se pueden alinear de manera confiable, pero cuando las secuencias son divergentes, no se puede obtener una alineación confiable y, por lo tanto, las aplicaciones de la alineación de secuencias son limitadas. Otra limitación de los métodos basados ​​en alineamiento es su complejidad computacional y su consumo de tiempo, por lo que resultan limitados cuando se trabaja con datos de secuencias a gran escala. [5] La aparición de tecnologías de secuenciación de última generación ha dado lugar a la generación de datos de secuenciación voluminosos. El tamaño de estos datos de secuencia plantea desafíos a los algoritmos basados ​​en alineamiento en su ensamblaje, anotación y estudios comparativos.

Métodos sin alineación

Los métodos sin alineamiento se pueden clasificar en cinco categorías: a) métodos basados ​​en la frecuencia de k -meros/palabras, b) métodos basados ​​en la longitud de subcadenas comunes, c) métodos basados ​​en el número de coincidencias de palabras (espaciadas), d) métodos basados ​​en microalineamientos , e) métodos basados ​​en la teoría de la información y f) métodos basados ​​en la representación gráfica. Los enfoques sin alineamiento se han utilizado en búsquedas de similitud de secuencias, [6] agrupamiento y clasificación de secuencias, [7] y más recientemente en filogenética [8] [9] ( Figura 1 ).

Se dice que estos análisis de filogenia molecular que emplean enfoques sin alineamiento son parte de la filogenómica de próxima generación . [9] Varios artículos de revisión proporcionan una revisión en profundidad de los métodos sin alineamiento en el análisis de secuencias. [1] [10] [11] [12] [13] [14] [15]

El AFproject es una colaboración internacional para evaluar y comparar herramientas de software para la comparación de secuencias sin alineación. [16]

Métodos basados ​​ena-mer/frecuencia de palabras

Los métodos populares basados ​​en frecuencias de k -meros/palabras incluyen el perfil de frecuencia de características (FFP), [17] [18] el vector de composición (CV), [19] [20] la distribución del tiempo de retorno (RTD), [21] la representación del juego de caos de frecuencias (FCGR), [22] y las palabras espaciadas. [23]

Perfil de frecuencia de características (FFP)

La metodología involucrada en el método basado en FFP comienza calculando el recuento de cada k -mero posible (número posible de k -meros para la secuencia de nucleótidos: 4 k , mientras que para la secuencia de proteína: 20 k ) en secuencias. Cada recuento de k -meros en cada secuencia se normaliza luego dividiéndolo por el total de todos los k -meros en esa secuencia. Esto conduce a la conversión de cada secuencia en su perfil de frecuencia característica. Luego se calcula la distancia por pares entre dos secuencias mediante la divergencia de Jensen-Shannon (JS) entre sus respectivos FFP. La matriz de distancia así obtenida se puede utilizar para construir un árbol filogenético utilizando algoritmos de agrupamiento como neighbor-joining , UPGMA , etc.

Vector de composición (CV)

En este método se calcula la frecuencia de aparición de cada k -mero posible en una secuencia dada. El siguiente paso característico de este método es la sustracción del fondo aleatorio de estas frecuencias utilizando el modelo de Markov para reducir la influencia de mutaciones neutrales aleatorias para resaltar el papel de la evolución selectiva. Las frecuencias normalizadas se colocan en un orden fijo para formar el vector de composición (CV) de una secuencia dada. La función de distancia del coseno se utiliza luego para calcular la distancia por pares entre los CV de las secuencias. La matriz de distancia así obtenida se puede utilizar para construir un árbol filogenético utilizando algoritmos de agrupamiento como neighbor-joining , UPGMA , etc. Este método se puede ampliar mediante el recurso a algoritmos eficientes de coincidencia de patrones para incluir en el cálculo de los vectores de composición: (i) todos los k -meros para cualquier valor de k , (ii) todas las subcadenas de cualquier longitud hasta un valor k máximo establecido arbitrariamente , (iii) todas las subcadenas máximas, donde una subcadena es máxima si extenderla por cualquier carácter causaría una disminución en su recuento de ocurrencias. [24] [25]

Distribución del tiempo de retorno (RTD)

El método basado en RTD no calcula el recuento de k -meros en secuencias, en su lugar calcula el tiempo necesario para la reaparición de k -meros. El tiempo se refiere al número de residuos en la aparición sucesiva de k -mero particular. Por lo tanto, la aparición de cada k -mero en una secuencia se calcula en forma de RTD, que luego se resume utilizando dos parámetros estadísticos media (μ) y desviación estándar (σ). Por lo tanto, cada secuencia se representa en forma de vector numérico de tamaño 2⋅4 k que contiene μ y σ de 4 k RTD. La distancia por pares entre secuencias se calcula utilizando la medida de distancia euclidiana . La matriz de distancia así obtenida se puede utilizar para construir un árbol filogenético utilizando algoritmos de agrupamiento como neighbor-joining , UPGMA , etc. Un enfoque reciente, Pattern Extraction through Entropy Retrieval (PEER), proporciona una detección directa de la longitud de k-meros y resume el intervalo de aparición utilizando la entropía.

Representación del juego del caos de frecuencias (FCGR)

Los métodos FCGR han evolucionado a partir de la técnica de representación de juegos de caos (CGR), que proporciona una representación independiente de la escala para las secuencias genómicas. [26] Los CGR se pueden dividir mediante líneas de cuadrícula donde cada cuadrado de la cuadrícula denota la aparición de oligonucleótidos de una longitud específica en la secuencia. Esta representación de los CGR se denomina Representación de juegos de caos de frecuencia (FCGR). Esto conduce a la representación de cada secuencia en FCGR. La distancia por pares entre FCGR de secuencias se puede calcular utilizando la distancia de Pearson, la distancia de Hamming o la distancia euclidiana. [27]

Frecuencias de palabras espaciadas

Mientras que la mayoría de los algoritmos sin alineación comparan la composición de palabras de secuencias, Spaced Words utiliza un patrón de posiciones de cuidado e indiferencia. La ocurrencia de una palabra espaciada en una secuencia se define entonces por los caracteres en las posiciones de coincidencia solamente, mientras que los caracteres en las posiciones de indiferencia se ignoran. En lugar de comparar las frecuencias de palabras contiguas en las secuencias de entrada, este enfoque compara las frecuencias de las palabras espaciadas de acuerdo con el patrón predefinido. [23] Nótese que el patrón predefinido puede seleccionarse mediante el análisis de la varianza del número de coincidencias, [28] la probabilidad de la primera ocurrencia en varios modelos, [29] o el coeficiente de correlación de Pearson entre la frecuencia esperada de la palabra y la distancia de alineación real. [30]

Métodos basados ​​en la longitud de subcadenas comunes

Los métodos de esta categoría emplean la similitud y las diferencias de subcadenas en un par de secuencias. Estos algoritmos se utilizaron principalmente para el procesamiento de cadenas en informática . [31]

Subcadena común promedio (ACS)

En este enfoque, para un par elegido de secuencias (A y B de longitudes n y m respectivamente), se identifica la subcadena más larga que comienza en alguna posición en una secuencia (A) que coincide exactamente en la otra secuencia (B) en cualquier posición. De esta manera, se calculan las longitudes de las subcadenas más largas que comienzan en diferentes posiciones en la secuencia A y que tienen coincidencias exactas en algunas posiciones en la secuencia B. Todas estas longitudes se promedian para derivar una medida . Intuitivamente, cuanto mayor sea , más similares son las dos secuencias. Para tener en cuenta las diferencias en la longitud de las secuencias, se normaliza [es decir ]. Esto da la medida de similitud entre las secuencias.

Para obtener una medida de distancia, se toma la medida inversa de similitud y se le resta un término de corrección para asegurar que sea cero.

Esta medida no es simétrica, por lo que hay que calcular , que da la medida ACS final entre las dos cadenas (A y B). [32] La búsqueda de subsecuencias/subcadenas se puede realizar de manera eficiente utilizando árboles de sufijos . [33] [34] [35]

a-enfoque de subcadena común promedio de desajuste (kmacs)

Este enfoque es una generalización del enfoque ACS. Para definir la distancia entre dos secuencias de ADN o proteínas, kmacs estima para cada posición i de la primera secuencia la subcadena más larga que comienza en i y coincide con una subcadena de la segunda secuencia con hasta k desajustes. Define el promedio de estos valores como una medida de similitud entre las secuencias y lo convierte en una medida de distancia simétrica. Kmacs no calcula las k subcadenas de desajustes exactas, ya que esto sería computacionalmente demasiado costoso, pero aproxima dichas subcadenas. [36]

Distancias de mutación (Kr)

Este enfoque está estrechamente relacionado con el ACS, que calcula el número de sustituciones por sitio entre dos secuencias de ADN utilizando la subcadena ausente más corta (denominada shustring). [37]

Distribución de longitud de subcadenas comunes con k desajustes

Este enfoque utiliza el programa kmacs [36] para calcular las subcadenas comunes más largas con hasta k desajustes para un par de secuencias de ADN. La distancia filogenética entre las secuencias se puede estimar a partir de un máximo local en la distribución de longitud de las subcadenas comunes con k desajustes. [38]

Métodos basados ​​en el número de coincidencias de palabras (espaciadas)

y

Estos enfoques son variantes de las estadísticas que cuentan el número de coincidencias de -meros entre dos secuencias. Mejoran las estadísticas simples al tener en cuenta la distribución de fondo de las secuencias comparadas. [39]

MEZCLA

Este es un método extremadamente rápido que utiliza la estrategia de boceto inferior MinHash para estimar el índice Jaccard de los conjuntos múltiples de -meros de dos secuencias de entrada. Es decir, estima la relación de coincidencias de -meros con el número total de -meros de las secuencias. Esto se puede utilizar, a su vez, para estimar las distancias evolutivas entre las secuencias comparadas, medidas como el número de sustituciones por posición de secuencia desde que las secuencias evolucionaron a partir de su último ancestro común. [40]

Árbol de ladera

Este enfoque calcula un valor de distancia entre dos secuencias de proteínas basándose en la disminución del número de coincidencias de -meros a medida que aumenta. [41]

Pendiente-SpaM

Este método calcula el número de coincidencias de -meros o palabras espaciadas ( SpaM ) para diferentes valores de la longitud de palabra o el número de posiciones de coincidencia en el patrón subyacente, respectivamente. La pendiente de una función lineal afín que depende de se calcula para estimar la distancia de Jukes-Cantor entre las secuencias de entrada. [42]

Esqueleto

Skmer calcula distancias entre especies a partir de lecturas de secuenciación no ensambladas. De manera similar a MASH , utiliza el índice Jaccard en los conjuntos de -meros de las secuencias de entrada. A diferencia de MASH , el programa sigue siendo preciso para una cobertura de secuenciación baja, por lo que se puede utilizar para el skimming del genoma . [43]

Métodos basados ​​en microalineaciones

En sentido estricto, estos métodos no son libres de alineamiento . Utilizan microalineamientos simples sin espacios en blanco en los que se requiere que las secuencias coincidan en ciertas posiciones predefinidas. Las posiciones alineadas en las posiciones restantes de los microalineamientos en las que se permiten desajustes se utilizan luego para la inferencia filogenética.

Co-filólogo

Este método busca las denominadas estructuras , que se definen como pares de coincidencias de k -meros entre dos secuencias de ADN que están separadas por una posición en ambas secuencias. Las dos coincidencias de k -meros se denominan contexto y la posición entre ellas se denomina objeto . El cofilog define entonces la distancia entre dos secuencias, es decir, la fracción de dichas estructuras para las que los dos nucleótidos en el objeto son diferentes. El enfoque se puede aplicar a lecturas de secuenciación no ensambladas. [44]

y yo

andi estima distancias filogenéticas entre secuencias genómicas basándose en alineaciones locales sin espacios flanqueadas por coincidencias de palabras exactas máximas. Dichas coincidencias de palabras se pueden encontrar de manera eficiente utilizando matrices de sufijos. Las alineaciones sin espacios entre las coincidencias de palabras exactas se utilizan luego para estimar distancias filogenéticas entre secuencias genómicas. Las estimaciones de distancia resultantes son precisas hasta aproximadamente 0,6 sustituciones por posición. [45]

Coincidencias de palabras espaciadas filtradas (FSWM)

FSWM utiliza un patrón binario predefinido P que representa las llamadas posiciones de coincidencia y posiciones de no importa . Para un par de secuencias de ADN de entrada, busca coincidencias de palabras espaciadas con respecto a P , es decir, alineaciones locales sin espacios con nucleótidos coincidentes en las posiciones de coincidencia de P y posibles desajustes en las posiciones de no importa . Las coincidencias de palabras espaciadas de baja puntuación espurias se descartan, las distancias evolutivas entre las secuencias de entrada se estiman en función de los nucleótidos alineados entre sí en las posiciones de no importa de las coincidencias de palabras espaciadas homólogas restantes. [46] FSWM se ha adaptado para estimar distancias en función de lecturas NGS no ensambladas, esta versión del programa se llama Read-SpaM . [47]

Prot-SpaM

Prot-SpaM ( Proteome -based Spaced -word Matches ) es una implementación del algoritmo FSWM para secuencias de proteoma parciales o completas. [48]

Multi-spam

Multi-SpaM ( Multi ple Spa ced-word Matches ) es un enfoque para la reconstrucción de filogenia basada en el genoma que extiende la idea FSWM a la comparación de secuencias múltiples. [49] Dado un patrón binario P de posiciones coincidentes y posiciones no importantes , el programa busca bloques P , es decir, alineaciones cuádruples locales sin espacios con nucleótidos coincidentes en las posiciones coincidentes de P y posibles desajustes en las posiciones no importantes . Dichas alineaciones cuádruples se muestrean aleatoriamente de un conjunto de secuencias de genoma de entrada. Para cada bloque P , se calcula una topología de árbol sin raíz utilizando RAxML . [50] Luego se utiliza el programa Quartet MaxCut para calcular un superárbol a partir de estos árboles.

Métodos basados ​​en la teoría de la información

La teoría de la información ha proporcionado métodos exitosos para el análisis y comparación de secuencias sin alineamiento. Las aplicaciones existentes de la teoría de la información incluyen la caracterización global y local del ADN, ARN y proteínas, la estimación de la entropía del genoma para la clasificación de motivos y regiones. También es prometedora en el mapeo genético , el análisis de secuenciación de próxima generación y la metagenómica . [51]

Correlación base-base (BBC)

La correlación base-base (BBC) convierte la secuencia del genoma en un vector numérico único de 16 dimensiones utilizando la siguiente ecuación:

El y denota las probabilidades de las bases i y j en el genoma. El indica la probabilidad de las bases i y j a una distancia en el genoma. El parámetro K indica la distancia máxima entre las bases i y j . La variación en los valores de 16 parámetros refleja la variación en el contenido y la longitud del genoma. [52] [53] [54]

Correlación de información y correlación de información parcial (IC-PIC)

El método basado en IC-PIC (correlación de información y correlación de información parcial) emplea la propiedad de correlación de base de la secuencia de ADN. La IC y la PIC se calcularon utilizando las siguientes fórmulas:

El vector final se obtiene de la siguiente manera:

que define el rango de distancia entre bases. [55]

La distancia por pares entre secuencias se calcula utilizando la medida de distancia euclidiana . La matriz de distancia así obtenida se puede utilizar para construir un árbol filogenético utilizando algoritmos de agrupamiento como neighbor-joining , UPGMA , etc.

Compresión

Los ejemplos son aproximaciones efectivas a la complejidad de Kolmogorov , por ejemplo la complejidad de Lempel-Ziv . En general, los métodos basados ​​en compresión utilizan la información mutua entre las secuencias. Esto se expresa en la complejidad de Kolmogorov condicional , es decir, la longitud del programa autodelimitante más corto requerido para generar una cadena dado el conocimiento previo de la otra cadena. Esta medida tiene una relación con la medición de k -palabras en una secuencia, ya que se pueden usar fácilmente para generar la secuencia. A veces es un método computacionalmente intensivo. La base teórica para el enfoque de la complejidad de Kolmogorov fue establecida por Bennett, Gacs, Li, Vitanyi y Zurek (1998) al proponer la distancia de información . [56] La complejidad de Kolmogorov al ser incalculable se aproximó mediante algoritmos de compresión. Cuanto mejor comprimen, mejores son. Li, Badger, Chen, Kwong, Kearney y Zhang (2001) utilizaron una forma no óptima pero normalizada de este enfoque, [57] y la forma normalizada óptima de Li, Chen, Li, Ma y Vitanyi (2003) apareció en [58] y de manera más extensa y probada por Cilibrasi y Vitanyi (2005) en. [59] Otu y Sayood (2003) utilizaron el método de complejidad Lempel-Ziv para construir cinco medidas de distancia diferentes para la construcción de árboles filogenéticos . [60]

Compresión de modelado de contexto

En el contexto de la complejidad del modelado, las predicciones del siguiente símbolo de uno o más modelos estadísticos se combinan o compiten para producir una predicción basada en eventos registrados en el pasado. El contenido de información algorítmica derivada de cada predicción de símbolo se puede utilizar para calcular perfiles de información algorítmica con un tiempo proporcional a la longitud de la secuencia. El proceso se ha aplicado al análisis de secuencias de ADN. [61]

Métodos basados ​​en representación gráfica

Mapas iterados

El uso de mapas iterados para el análisis de secuencias fue introducido por primera vez por HJ Jefferey en 1990 [26] cuando propuso aplicar el Juego del Caos para mapear secuencias genómicas en un cuadrado unitario. Ese informe acuñó el procedimiento como Representación del Juego del Caos (CGR). Sin embargo, solo 3 años después este enfoque fue descartado por primera vez como una proyección de una tabla de transición de Markov por N. Goldman. [62] Esta objeción fue rechazada a fines de esa década cuando se descubrió que el caso era el opuesto: que CGR mapea biyectivamente la transición de Markov en una representación fractal sin orden (sin grado). [63] La comprensión de que los mapas iterados proporcionan un mapa biyectivo entre el espacio simbólico y el espacio numérico condujo a la identificación de una variedad de enfoques sin alineamiento para la comparación y caracterización de secuencias. Estos desarrollos fueron revisados ​​a fines de 2013 por JS Almeida en [64] . Varias aplicaciones web como https://github.com/usm/usm.github.com/wiki, [65] están disponibles para demostrar cómo codificar y comparar secuencias simbólicas arbitrarias de una manera que aproveche al máximo la distribución moderna de MapReduce desarrollada para la computación en la nube.

Comparación de métodos basados ​​en alineación y sin alineación

Aplicaciones de los métodos sin alineación

Lista de servidores web/software para métodos sin alineación

Véase también

Referencias

  1. ^ ab Vinga S, Almeida J (marzo de 2003). "Comparación de secuencias sin alineamiento: una revisión". Bioinformática . 19 (4): 513–523. doi : 10.1093/bioinformatics/btg005 . PMID  12611807.
  2. ^ Rothberg J, Merriman B, Higgs G (septiembre de 2012). "Bioinformática. Introducción". The Yale Journal of Biology and Medicine . 85 (3): 305–308. PMC 3447194 . PMID  23189382. 
  3. ^ Batzoglou S (marzo de 2005). "Las múltiples caras del alineamiento de secuencias". Briefings in Bioinformatics . 6 (1): 6–22. doi : 10.1093/bib/6.1.6 . PMID  15826353.
  4. ^ Mullan L (marzo de 2006). "Alineamiento de secuencias por pares: ¡todo depende de nosotros!". Briefings in Bioinformatics . 7 (1): 113–115. doi :10.1093/bib/bbk008. PMID  16761368.
  5. ^ Kemena C, Notredame C (octubre de 2009). "Próximos desafíos para los métodos de alineamiento de secuencias múltiples en la era del alto rendimiento". Bioinformática . 25 (19): 2455–2465. doi :10.1093/bioinformatics/btp452. PMC 2752613 . PMID  19648142. 
  6. ^ Hide W, Burke J, Davison DB (1994). "Evaluación biológica de d2, un algoritmo para la comparación de secuencias de alto rendimiento". Journal of Computational Biology . 1 (3): 199–215. doi :10.1089/cmb.1994.1.199. PMID  8790465.
  7. ^ Miller RT, Christoffels AG, Gopalakrishnan C, Burke J, Ptitsyn AA, Broveak TR, Hide WA (noviembre de 1999). "Un enfoque integral para la agrupación de secuencias de genes humanos expresados: la alineación de etiquetas de secuencia y la base de conocimiento de consenso". Genome Research . 9 (11): 1143–1155. doi :10.1101/gr.9.11.1143. PMC 310831 . PMID  10568754. 
  8. ^ abc Domazet-Lošo M, Haubold B (junio de 2011). "Detección sin alineamiento de similitud local entre genomas virales y bacterianos". Bioinformática . 27 (11): 1466–1472. doi : 10.1093/bioinformatics/btr176 . PMID  21471011.
  9. ^ abc Chan CX, Ragan MA (enero de 2013). "Filogenómica de próxima generación". Biology Direct . 8 : 3. doi : 10.1186/1745-6150-8-3 . PMC 3564786 . PMID  23339707. 
  10. ^ Song K, Ren J, Reinert G , Deng M, Waterman MS, Sun F (mayo de 2014). "Nuevos desarrollos de la comparación de secuencias sin alineamiento: medidas, estadísticas y secuenciación de próxima generación". Briefings in Bioinformatics . 15 (3): 343–353. doi :10.1093/bib/bbt067. PMC 4017329 . PMID  24064230. 
  11. ^ ab Haubold B (mayo de 2014). "Filogenética sin alineamiento y genética de poblaciones". Briefings in Bioinformatics . 15 (3): 407–418. doi : 10.1093/bib/bbt083 . PMID  24291823.
  12. ^ Bonham-Carter O, Steele J, Bastola D (noviembre de 2014). "Comparaciones de secuencias genéticas sin alineamiento: una revisión de enfoques recientes mediante análisis de palabras". Briefings in Bioinformatics . 15 (6): 890–905. doi :10.1093/bib/bbt052. PMC 4296134 . PMID  23904502. 
  13. ^ Zielezinski A, Vinga S, Almeida J, Karlowski WM (octubre de 2017). "Comparación de secuencias sin alineamiento: beneficios, aplicaciones y herramientas". Genome Biology . 18 (1): 186. doi : 10.1186/s13059-017-1319-7 . PMC 5627421 . PMID  28974235. 
  14. ^ ab Bernard G, Chan CX, Chan YB, Chua XY, Cong Y, Hogan JM, et al. (marzo de 2019). "Inferencia sin alineamiento de relaciones filogenómicas jerárquicas y reticuladas". Briefings in Bioinformatics . 20 (2): 426–435. doi :10.1093/bib/bbx067. PMC 6433738 . PMID  28673025. 
  15. ^ Ren J, Bai X, Lu YY, Tang K, Wang Y, Reinert G, Sun F (julio de 2018). "Análisis y aplicaciones de secuencias sin alineamiento". Revisión anual de ciencia de datos biomédicos . 1 : 93–114. arXiv : 1803.09727 . Código Bibliográfico :2018arXiv180309727R. doi :10.1146/annurev-biodatasci-080917-013431. PMC 6905628 . PMID  31828235. 
  16. ^ Zielezinski A, Girgis HZ, Bernard G, Leimeister CA, Tang K, Dencker T, et al. (julio de 2019). "Evaluación comparativa de métodos de comparación de secuencias sin alineamiento". Genome Biology . 20 (1): 144. doi : 10.1186/s13059-019-1755-7 . PMC 6659240 . PMID  31345254. 
  17. ^ ab Sims GE, Jun SR, Wu GA, Kim SH (octubre de 2009). "Filogenia del genoma completo de los mamíferos: información evolutiva en regiones génicas y no génicas". Actas de la Academia Nacional de Ciencias de los Estados Unidos de América . 106 (40): 17077–17082. Bibcode :2009PNAS..10617077S. doi : 10.1073/pnas.0909377106 . PMC 2761373 . PMID  19805074. 
  18. ^ Sims GE, Kim SH (mayo de 2011). "Filogenia del genoma completo del grupo Escherichia coli/Shigella mediante perfiles de frecuencia de características (FFP)". Actas de la Academia Nacional de Ciencias de los Estados Unidos de América . 108 (20): 8329–8334. Bibcode :2011PNAS..108.8329S. doi : 10.1073/pnas.1105168108 . PMC 3100984 . PMID  21536867. 
  19. ^ Gao L, Qi J (marzo de 2007). "Filogenia molecular del genoma completo de virus de ADN de doble cadena de gran tamaño utilizando el método del vector de composición". BMC Evolutionary Biology . 7 (1): 41. Bibcode :2007BMCEE...7...41G. doi : 10.1186/1471-2148-7-41 . PMC 1839080 . PMID  17359548. 
  20. ^ Wang H, Xu Z, Gao L, Hao B (agosto de 2009). "Una filogenia fúngica basada en 82 genomas completos utilizando el método del vector de composición". BMC Evolutionary Biology . 9 (1): 195. Bibcode :2009BMCEE...9..195W. doi : 10.1186/1471-2148-9-195 . PMC 3087519 . PMID  19664262. 
  21. ^ abcd Kolekar P, Kale M, Kulkarni-Kale U (noviembre de 2012). "Medida de distancia sin alineamiento basada en la distribución del tiempo de retorno para el análisis de secuencias: aplicaciones a la agrupación, la filogenia molecular y la subtipificación". Filogenética molecular y evolución . 65 (2): 510–522. doi :10.1016/j.ympev.2012.07.003. PMID  22820020.
  22. ^ Hatje K, Kollmar M (2012). "Un análisis filogenético del clado de las brasicales basado en un método de comparación de secuencias sin alineamiento". Frontiers in Plant Science . 3 : 192. doi : 10.3389/fpls.2012.00192 . PMC 3429886 . PMID  22952468. 
  23. ^ abc Leimeister CA, Boden M, Horwege S, Lindner S, Morgenstern B (julio de 2014). "Comparación rápida de secuencias sin alineamiento utilizando frecuencias de palabras espaciadas". Bioinformática . 30 (14): 1991–1999. doi :10.1093/bioinformatics/btu177. PMC 4080745 . PMID  24700317. 
  24. ^ Apostolico A, Denas O (octubre de 2008). "Algoritmos rápidos para calcular distancias de secuencias mediante composición exhaustiva de subcadenas". Algorithms for Molecular Biology . 3 : 13. doi : 10.1186/1748-7188-3-13 . PMC 2615014 . PMID  18957094. 
  25. ^ Apostolico A, Denas O, Dress A (septiembre de 2010). "Herramientas eficientes para el análisis comparativo de subcadenas". Revista de biotecnología . 149 (3): 120–126. doi :10.1016/j.jbiotec.2010.05.006. PMID  20682467.
  26. ^ ab Jeffrey HJ (abril de 1990). "Representación de la estructura genética mediante un juego de caos". Nucleic Acids Research . 18 (8): 2163–2170. doi :10.1093/nar/18.8.2163. PMC 330698 . PMID  2336393. 
  27. ^ Wang Y, Hill K, Singh S, Kari L (febrero de 2005). "El espectro de las firmas genómicas: desde los dinucleótidos hasta la representación del juego del caos". Gene . 346 : 173–185. doi :10.1016/j.gene.2004.10.021. PMID  15716010.
  28. ^ Hahn L, Leimeister CA, Ounit R, Lonardi S, Morgenstern B (octubre de 2016). "rasbhari: optimización de semillas espaciadas para búsquedas en bases de datos, mapeo de lecturas y comparación de secuencias sin alineamiento". PLOS Computational Biology . 12 (10): e1005107. arXiv : 1511.04001 . Bibcode :2016PLSCB..12E5107H. doi : 10.1371/journal.pcbi.1005107 . PMC 5070788 . PMID  27760124. 
  29. ^ Noé L (14 de febrero de 2017). "Mejores resultados de 11110110111: selección sin modelo y cálculo de sensibilidad sin parámetros de semillas espaciadas". Algoritmos para biología molecular . 12 (1): 1. doi : 10.1186/s13015-017-0092-1 . PMC 5310094 . PMID  28289437. 
  30. ^ ab Noé L, Martin DE (diciembre de 2014). "Un criterio de cobertura para semillas espaciadas y sus aplicaciones para soportar núcleos de cadenas de máquinas vectoriales y distancias k-mer". Journal of Computational Biology . 21 (12): 947–963. arXiv : 1412.2587 . Bibcode :2014arXiv1412.2587N. doi :10.1089/cmb.2014.0173. PMC 4253314 . PMID  25393923. 
  31. ^ Gusfield D (1997). Algoritmos sobre cadenas, árboles y secuencias: informática y biología computacional (Reimpreso (con correcciones) ed.). Cambridge [ua]: Cambridge Univ. Press. ISBN 9780521585194.
  32. ^ Ulitsky I, Burstein D, Tuller T, Chor B (marzo de 2006). "El enfoque de la subcadena común promedio para la reconstrucción filogenómica". Revista de biología computacional . 13 (2): 336–350. CiteSeerX 10.1.1.106.5122 . doi :10.1089/cmb.2006.13.336. PMID  16597244. 
  33. ^ Weiner P (1973). "Algoritmos de coincidencia de patrones lineales". 14.º Simposio anual sobre conmutación y teoría de autómatas (SWAT 1973) . págs. 1–11. CiteSeerX 10.1.1.474.9582 . doi :10.1109/SWAT.1973.13. 
  34. ^ He D (2006). "Uso de árboles de sufijos para descubrir patrones repetitivos complejos en secuencias de ADN". Conferencia internacional de 2006 de la IEEE Engineering in Medicine and Biology Society . Vol. 1. págs. 3474–7. doi :10.1109/IEMBS.2006.260445. ISBN 978-1-4244-0032-4. Número de identificación personal  17945779. Número de identificación personal  5953866.
  35. ^ Välimäki N, Gerlach W, Dixit K, Mäkinen V (marzo de 2007). "Árbol de sufijos comprimido: una base para el análisis de secuencias a escala del genoma". Bioinformática . 23 (5): 629–630. doi : 10.1093/bioinformatics/btl681 . PMID  17237063.
  36. ^ abc Leimeister CA, Morgenstern B (julio de 2014). "Kmacs: el enfoque de subcadena común promedio de k-desajustes para la comparación de secuencias sin alineamiento". Bioinformática . 30 (14): 2000–2008. doi :10.1093/bioinformatics/btu331. PMC 4080746 . PMID  24828656. 
  37. ^ Haubold B, Pfaffelhuber P, Domazet-Loso M, Wiehe T (octubre de 2009). "Estimación de distancias de mutación a partir de genomas no alineados". Journal of Computational Biology . 16 (10): 1487–1500. doi :10.1089/cmb.2009.0106. hdl : 11858/00-001M-0000-000F-D624-D . PMID  19803738.
  38. ^ Morgenstern B, Schöbel S, Leimeister CA (2017). "Reconstrucción filogenética basada en la distribución de longitud de subcadenas comunes con k-desajustes". Algorithms for Molecular Biology . 12 : 27. doi : 10.1186/s13015-017-0118-8 . PMC 5724348 . PMID  29238399. 
  39. ^ Reinert G, Chew D, Sun F, Waterman MS (diciembre de 2009). "Comparación de secuencias sin alineamiento (I): estadísticas y potencia". Journal of Computational Biology . 16 (12): 1615–1634. doi :10.1089/cmb.2009.0198. PMC 2818754 . PMID  20001252. 
  40. ^ Ondov BD, Treangen TJ, Melsted P, Mallonee AB, Bergman NH, Koren S, Phillippy AM (junio de 2016). "Mash: estimación rápida de la distancia entre el genoma y el metagenoma utilizando MinHash". Genome Biology . 17 (1): 132. doi : 10.1186/s13059-016-0997-x . PMC 4915045 . PMID  27323842. 
  41. ^ Bromberg R, Grishin NV, Otwinowski Z (junio de 2016). "Reconstrucción de la filogenia con un método sin alineamiento que corrige la transferencia horizontal de genes". PLOS Computational Biology . 12 (6): e1004985. Bibcode :2016PLSCB..12E4985B. doi : 10.1371/journal.pcbi.1004985 . PMC 4918981 . PMID  27336403. 
  42. ^ Röhling S, Linne A, Schellhorn J, Hosseini M, Dencker T, Morgenstern B (2020). "El número de coincidencias de k-meros entre dos secuencias de ADN en función de k y aplicaciones para estimar distancias filogenéticas". PLOS ONE . ​​15 (2): e0228070. Bibcode :2020PLoSO..1528070R. doi : 10.1371/journal.pone.0228070 . PMC 7010260 . PMID  32040534. 
  43. ^ Sarmashghi S, Bohmann K, P Gilbert MT, Bafna V, Mirarab S (febrero de 2019). "Skmer: identificación de muestras sin ensamblaje ni alineamiento mediante desnatado del genoma". Genome Biology . 20 (1): 34. doi : 10.1186/s13059-019-1632-4 . PMC 6374904 . PMID  30760303. 
  44. ^ ab Yi H, Jin L (abril de 2013). "Co-phylog: un enfoque filogenómico sin ensamblaje para organismos estrechamente relacionados". Nucleic Acids Research . 41 (7): e75. doi :10.1093/nar/gkt003. PMC 3627563 . PMID  23335788. 
  45. ^ Haubold B, Klötzl F, Pfaffelhuber P (abril de 2015). «andi: estimación rápida y precisa de distancias evolutivas entre genomas estrechamente relacionados». Bioinformática . 31 (8): 1169–1175. doi : 10.1093/bioinformatics/btu815 . PMID  25504847.
  46. ^ ab Leimeister CA, Sohrabi-Jahromi S, Morgenstern B (abril de 2017). "Reconstrucción filogenética rápida y precisa utilizando coincidencias de palabras espaciadas filtradas". Bioinformática . 33 (7): 971–979. doi :10.1093/bioinformatics/btw776. PMC 5409309 . PMID  28073754. 
  47. ^ Lau AK, Dörrer S, Leimeister CA, Bleidorn C, Morgenstern B (diciembre de 2019). "Read-SpaM: comparación sin ensamblaje ni alineamiento de genomas bacterianos con baja cobertura de secuenciación". BMC Bioinformatics . 20 (Supl 20): 638. doi : 10.1186/s12859-019-3205-7 . PMC 6916211 . PMID  31842735. 
  48. ^ ab Leimeister CA, Schellhorn J, Dörrer S, Gerth M, Bleidorn C, Morgenstern B (marzo de 2019). "Prot-SpaM: reconstrucción rápida de filogenia sin alineamiento basada en secuencias de proteoma completo". GigaScience . 8 (3): giy148. doi :10.1093/gigascience/giy148. PMC 6436989 . PMID  30535314. 
  49. ^ Dencker T, Leimeister CA, Gerth M, Bleidorn C, Snir S, Morgenstern B (marzo de 2020). "'Multi-SpaM': un enfoque de máxima verosimilitud para la reconstrucción de la filogenia utilizando múltiples coincidencias de palabras espaciadas y árboles de cuarteto". NAR Genomics and Bioinformatics . 2 (1): lqz013. doi : 10.1093/nargab/lqz013 . PMC 7671388 . PMID  33575565. 
  50. ^ Stamatakis A (noviembre de 2006). "RAxML-VI-HPC: análisis filogenéticos basados ​​en máxima verosimilitud con miles de taxones y modelos mixtos". Bioinformática . 22 (21): 2688–2690. doi : 10.1093/bioinformatics/btl446 . PMID  16928733.
  51. ^ Vinga S (mayo de 2014). "Aplicaciones de la teoría de la información para el análisis de secuencias biológicas". Briefings in Bioinformatics . 15 (3): 376–389. doi : 10.1093/bib/bbt068 . PMC 7109941 . PMID  24058049. 
  52. ^ Liu Z, Meng J, Sun X (abril de 2008). "Un nuevo método basado en características para el análisis filogenético del genoma completo sin alineamiento: aplicación a la genotipificación y subtipificación del virus de la hepatitis E". Biochemical and Biophysical Research Communications . 368 (2): 223–230. doi :10.1016/j.bbrc.2008.01.070. PMID  18230342.
  53. ^ Liu ZH, Sun X (2008). "Filogenia del coronavirus basada en correlación base-base". Revista internacional de investigación y aplicaciones bioinformáticas . 4 (2): 211–220. doi :10.1504/ijbra.2008.018347. PMID  18490264.
  54. ^ Cheng J, Zeng X, Ren G, Liu Z (marzo de 2013). "CGAP: una nueva plataforma integral para el análisis comparativo de genomas de cloroplastos". BMC Bioinformatics . 14 : 95. doi : 10.1186/1471-2105-14-95 . PMC 3636126 . PMID  23496817. 
  55. ^ Gao Y, Luo L (enero de 2012). "Filogenia basada en el genoma de virus dsDNA mediante un nuevo método sin alineamiento". Gene . 492 (1): 309–314. doi :10.1016/j.gene.2011.11.004. PMID  22100880.
  56. ^ Bennett, CH, Gacs, P., Li, M., Vitanyi, P. y Zurek, W., Distancia de información, IEEE Trans. Inform. Theory, 44, 1407-1423
  57. ^ Li, M., Badger, JH, Chen, X., Kwong, S., Kearney, P. y Zhang, H. (2001) Una distancia de secuencia basada en información y su aplicación a la filogenia del genoma mitocondrial completo. Bioinformática, 17:(2001), 149--154
  58. ^ M. Li, X. Chen, X. Li, B. Ma, PMB Vitanyi. La métrica de similitud, IEEE Trans. Inform. Th., 50:12(2004), 3250--3264
  59. ^ RL Cilibrasi y PMB Vitanyi, Agrupamiento por compresión, IEEE Trans. Informat. Th., 51:4(2005), 1523--1545
  60. ^ Otu HH, Sawood K (noviembre de 2003). "Una nueva medida de distancia de secuencia para la construcción de árboles filogenéticos". Bioinformática . 19 (16): 2122–2130. doi : 10.1093/bioinformatics/btg295 . PMID  14594718.
  61. ^ Pinho AJ, Garcia SP, Pratas D, Ferreira PJ (21 de noviembre de 2013). "Secuencias de ADN de un vistazo". PLOS ONE . ​​8 (11): e79922. Bibcode :2013PLoSO...879922P. doi : 10.1371/journal.pone.0079922 . PMC 3836782 . PMID  24278218. 
  62. ^ Goldman N (mayo de 1993). "Las frecuencias de nucleótidos, dinucleótidos y trinucleótidos explican los patrones observados en las representaciones de secuencias de ADN en juegos de caos". Nucleic Acids Research . 21 (10): 2487–2491. doi :10.1093/nar/21.10.2487. PMC 309551 . PMID  8506142. 
  63. ^ Almeida JS, Carriço JA, Maretzek A, Noble PA, Fletcher M (mayo de 2001). "Análisis de secuencias genómicas mediante representación de juegos del caos". Bioinformática . 17 (5): 429–437. doi : 10.1093/bioinformatics/17.5.429 . PMID  11331237.
  64. ^ Almeida JS (mayo de 2014). "Análisis de secuencias mediante mapas iterados, una revisión". Briefings in Bioinformatics . 15 (3): 369–375. doi :10.1093/bib/bbt072. PMC 4017330 . PMID  24162172. 
  65. ^ ab Almeida JS, Grüneberg A, Maass W, Vinga S (mayo de 2012). "Descomposición fractal de alineamiento de secuencias con MapReduce". Algoritmos para biología molecular . 7 (1): 12. doi : 10.1186/1748-7188-7-12 . PMC 3394223 . PMID  22551205. 
  66. ^ Vinga S, Carvalho AM, Francisco AP, Russo LM, Almeida JS (mayo de 2012). "Correspondencia de patrones mediante representación de juegos de caos: uniendo estructuras de datos numéricos y discretos para el análisis de secuencias biológicas". Algorithms for Molecular Biology . 7 (1): 10. doi : 10.1186/1748-7188-7-10 . PMC 3402988 . PMID  22551152. 
  67. ^ ab Pratas D, Silva RM, Pinho AJ, Ferreira PJ (mayo de 2015). "Un método sin alineamiento para encontrar y visualizar reordenamientos entre pares de secuencias de ADN". Scientific Reports . 5 (10203): 10203. Bibcode :2015NatSR...510203P. doi :10.1038/srep10203. PMC 4434998 . PMID  25984837. 
  68. ^ ab Hosseini M, Pratas D, Morgenstern B, Pinho AJ (mayo de 2020). "Smash++: una herramienta sin alineamiento y con uso eficiente de la memoria para encontrar reordenamientos genómicos". GigaScience . 9 (5): giaa048. doi : 10.1093/gigascience/giaa048 . PMC 7238676 . PMID  32432328. 
  69. ^ Bernard G, Greenfield P, Ragan MA, Chan CX (20 de noviembre de 2018). "Similitud de k-mer, redes de genomas microbianos y rango taxonómico". mSystems . 3 (6): e00257–18. doi :10.1128/mSystems.00257-18. PMC 6247013 . PMID  30505941. 
  70. ^ ab Song K, Ren J, Reinert G, Deng M, Waterman MS, Sun F (mayo de 2014). "Nuevos desarrollos de la comparación de secuencias sin alineamiento: medidas, estadísticas y secuenciación de próxima generación". Briefings in Bioinformatics . 15 (3): 343–353. doi :10.1093/bib/bbt067. PMC 4017329 . PMID  24064230. 
  71. ^ Břinda K, Sykulski M, Kucherov G (noviembre de 2015). "Las semillas espaciadas mejoran la clasificación metagenómica basada en k-mer". Bioinformática . 31 (22): 3584–3592. arXiv : 1502.06256 . Código Bibliográfico :2015arXiv150206256B. doi :10.1093/bioinformatics/btv419. PMID  26209798. S2CID  8626694.
  72. ^ Ounit R, Lonardi S (diciembre de 2016). "Mayor sensibilidad de clasificación de lecturas metagenómicas cortas con CLARK-S". Bioinformática . 32 (24): 3823–3825. doi : 10.1093/bioinformatics/btw542 . PMID  27540266.
  73. ^ ab Pratas D, Pinho AJ, Silva RM, Rodrigues JM, Hosseini M, Caetano T, Ferreira PJ (febrero de 2018). "FALCON: un método para inferir la composición metagenómica del ADN antiguo". bioRxiv 10.1101/267179 . 
  74. ^ ab Wood DE, Salzberg SL (marzo de 2014). "Kraken: clasificación de secuencias metagenómicas ultrarrápidas utilizando alineaciones exactas". Genome Biology . 15 (3): R46. doi : 10.1186/gb-2014-15-3-r46 . PMC 4053813 . PMID  24580807. 
  75. ^ Pinello L, Lo Bosco G, Yuan GC (mayo de 2014). "Aplicaciones de métodos sin alineamiento en epigenómica". Briefings in Bioinformatics . 15 (3): 419–430. doi :10.1093/bib/bbt078. PMC 4017331 . PMID  24197932. 
  76. ^ La Rosa M, Fiannaca A, Rizzo R, Urso A (2013). "Análisis sin alineamiento de secuencias de códigos de barras mediante métodos basados ​​en compresión". BMC Bioinformatics . 14 (Suppl 7): S4. doi : 10.1186/1471-2105-14-S7-S4 . PMC 3633054 . PMID  23815444. 
  77. ^ ab Kolekar P, Hake N, Kale M, Kulkarni-Kale U (marzo de 2014). "WNV Typer: un servidor para la genotipificación de virus del Nilo Occidental utilizando un método sin alineamiento basado en una distribución de tiempo de retorno". Journal of Virological Methods . 198 : 41–55. doi : 10.1016/j.jviromet.2013.12.012 . PMID  24388930.
  78. ^ ab Struck D, Lawyer G, Ternes AM, Schmit JC, Bercoff DP (octubre de 2014). "COMET: modelado adaptativo basado en el contexto para la identificación ultrarrápida del subtipo del VIH-1". Nucleic Acids Research . 42 (18): e144. doi :10.1093/nar/gku739. PMC 4191385 . PMID  25120265. 
  79. ^ ab Dimitrov I, Naneva L, Doytchinova I, Bangov I (marzo de 2014). "AllergenFP: predicción de alergenicidad mediante huellas digitales de descriptores". Bioinformática . 30 (6): 846–851. doi : 10.1093/bioinformatics/btt619 . PMID  24167156.
  80. ^ ab Gardner SN, Hall BG (9 de diciembre de 2013). "Cuando las alineaciones de todo el genoma simplemente no funcionan: software kSNP v2 para el descubrimiento de SNP sin alineamiento y la filogenética de cientos de genomas microbianos". PLOS ONE . ​​8 (12): e81760. Bibcode :2013PLoSO...881760G. doi : 10.1371/journal.pone.0081760 . PMC 3857212 . PMID  24349125. 
  81. ^ ab Haubold B, Krause L, Horn T, Pfaffelhuber P (diciembre de 2013). "Una prueba sin alineamiento para la recombinación". Bioinformática . 29 (24): 3121–3127. doi :10.1093/bioinformatics/btt550. PMC 5994939 . PMID  24064419. 
  82. ^ Silva JM, Pratas D, Caetano T, Matos S (agosto de 2022). "El panorama de la complejidad de los genomas virales". GigaScience . 11 : 1–16. doi :10.1093/gigascience/giac079. PMC 9366995 . PMID  35950839. 
  83. ^ Silva JM, Pratas D, Caetano T, Matos S (2022), Pinho AJ, Georgieva P, Teixeira LF, Sánchez JA (eds.), "Clasificación basada en características de secuencias arqueológicas utilizando métodos basados ​​en compresión", Reconocimiento de patrones y análisis de imágenes , Lecture Notes in Computer Science, vol. 13256, Cham: Springer International Publishing, págs. 309–320, doi :10.1007/978-3-031-04881-4_25, ISBN 978-3-031-04880-7, consultado el 31 de agosto de 2022
  84. ^ ab Silva JM, Qi W, Pinho AJ, Pratas D (diciembre de 2022). "AlcoR: simulación, mapeo y visualización sin alineamiento de regiones de baja complejidad en datos biológicos". GigaScience . 12 . doi :10.1093/gigascience/giad101. PMC 10716826 . PMID  38091509. 
  85. ^ Di Biasi L, Piotto S. ARISE: Motor de búsqueda semántico de inteligencia artificial . WIVACE2021.
  86. ^ Xu Z, Hao B (julio de 2009). "Actualización de CV Tree: una plataforma de estudio filogenético de nuevo diseño que utiliza vectores de composición y genomas completos". Nucleic Acids Research . 37 (número de servidor web): W174–W178. doi :10.1093/nar/gkp278. PMC 2703908 . PMID  19398429. 
  87. ^ Cheng J, Cao F, Liu Z (mayo de 2013). "AGP: un servidor web multimétodos para la filogenia del genoma sin alineamiento". Biología molecular y evolución . 30 (5): 1032–1037. doi : 10.1093/molbev/mst021 . PMC 7574599 . PMID  23389766. 
  88. ^ Höhl M, Rigoutsos I, Ragan MA (febrero de 2007). "Estimación de distancia filogenética basada en patrones y reconstrucción de árboles". Evolutionary Bioinformatics Online . 2 : 359–375. arXiv : q-bio/0605002 . Código Bibliográfico :2006q.bio.....5002H. PMC 2674673 . PMID  19455227. 
  89. ^ Wang Y, Liu L, Chen L, Chen T, Sun F (2 de enero de 2014). "Comparación de muestras metatranscriptómicas basadas en frecuencias de k-tuplas". PLOS ONE . ​​9 (1): e84348. Bibcode :2014PLoSO...984348W. doi : 10.1371/journal.pone.0084348 . PMC 3879298 . PMID  24392128. 
  90. ^ "Módulo de genómica microbiana CLC". Bioinformática QIAGEN . 2019.
  91. ^ Pratas D, Silva JM (enero de 2021). "Secuencias mínimas persistentes del SARS-CoV-2". Bioinformática . 36 (21): 5129–5132. doi : 10.1093/bioinformatics/btaa686 . PMC 7559010 . PMID  32730589.