Los filtros Bloom son estructuras de datos probabilísticas eficientes en el espacio que se utilizan para probar si un elemento es parte de un conjunto. Los filtros Bloom requieren mucho menos espacio que otras estructuras de datos para representar conjuntos, sin embargo, la desventaja de los filtros Bloom es que hay una tasa de falsos positivosal consultar la estructura de datos. Dado que varios elementos pueden tener los mismos valores hash para varias funciones hash, existe la probabilidad de que la consulta de un elemento inexistente arroje un resultado positivo si se ha agregado otro elemento con los mismos valores hash al filtro Bloom. Suponiendo que la función hash tiene la misma probabilidad de seleccionar cualquier índice del filtro Bloom, la tasa de falsos positivos de consultar un filtro Bloom es una función del número de bits, el número de funciones hash y el número de elementos del filtro Bloom. Esto permite al usuario gestionar el riesgo de obtener un falso positivo al comprometer los beneficios de espacio del filtro Bloom.
Los filtros Bloom se utilizan principalmente en bioinformática para probar la existencia de un k-mer en una secuencia o conjunto de secuencias. Los k-meros de la secuencia se indexan en un filtro Bloom, y cualquier k-mer del mismo tamaño se puede consultar con el filtro Bloom. Esta es una alternativa preferible al hash de los k-mers de una secuencia con una tabla hash , particularmente cuando la secuencia es muy larga, ya que es muy exigente almacenar un gran número de k-mers en la memoria.
Aplicaciones
Caracterización de la secuencia
El paso de preprocesamiento en muchas aplicaciones bioinformáticas implica clasificar secuencias, principalmente clasificando lecturas de un experimento de secuenciación de ADN . Por ejemplo, en los estudios metagenómicos es importante saber si una lectura de secuenciación pertenece a una nueva especie. [1] y en los proyectos de secuenciación clínica es vital filtrar las lecturas de los genomas de los organismos contaminantes. Hay muchas herramientas bioinformáticas que utilizan filtros Bloom para clasificar lecturas consultando k-mers de una lectura a un conjunto de filtros Bloom generados a partir de genomas de referencia conocidos . Algunas herramientas que utilizan este método son las herramientas FACS [2] y BioBloom. [3] Si bien estos métodos pueden no superar a otras herramientas de clasificación bioinformática como Kraken, [4] ofrecen una alternativa de memoria eficiente.
Un área reciente de investigación con filtros Bloom en la caracterización de secuencias es el desarrollo de formas de consultar lecturas sin procesar de experimentos de secuenciación. Por ejemplo, ¿cómo se puede determinar qué lecturas contienen un 30-mer específico en todo el archivo de lectura de secuencia de NCBI ? Esta tarea es similar a la que realiza BLAST , sin embargo, implica consultar un conjunto de datos mucho más grande; mientras BLAST consulta contra una base de datos de genomas de referencia, esta tarea exige que se devuelvan lecturas específicas que contienen el k-mer. BLAST y herramientas similares no pueden manejar este problema de manera eficiente, por lo tanto, se han implementado estructuras de datos basadas en filtros Bloom para este fin. Los árboles de floración binaria [5] son árboles binarios de filtros de Bloom que facilitan la consulta de transcripciones en grandes experimentos de RNA-seq . BIGSI [6] toma prestadas firmas fragmentadas del campo de la recuperación de documentos para indexar y consultar la totalidad de los datos de secuenciación microbiana y viral en el Archivo Europeo de Nucleótidos . La firma de un conjunto de datos determinado se codifica como un conjunto de filtros Bloom de ese conjunto de datos.
Ensamblaje del genoma
La eficiencia de la memoria de los filtros Bloom se ha utilizado en el ensamblaje del genoma como una forma de reducir la huella de espacio de los k-mers a partir de la secuenciación de datos. La contribución de los métodos de ensamblaje basados en filtros Bloom es combinar filtros Bloom y gráficos de Bruijn en una estructura llamada gráfica probabilística de Bruijn, [7] que optimiza el uso de la memoria a costa de la tasa de falsos positivos inherentes a los filtros Bloom. En lugar de almacenar el gráfico de De Bruijn en una tabla hash, se almacena en un filtro Bloom.
El uso de un filtro Bloom para almacenar el gráfico de Bruijn complica el paso transversal del gráfico para construir el ensamblaje, ya que la información de los bordes no está codificada en el filtro Bloom. El recorrido del gráfico se logra consultando el filtro Bloom para cualquiera de los cuatro posibles k-mers posteriores del nodo actual. Por ejemplo, si el nodo actual es para k-mer ACT, entonces el siguiente nodo debe ser para uno de los k-mers CTA, CTG, CTC o CTT. Si existe una consulta k-mer en el filtro Bloom, entonces k-mer se agrega a la ruta. Por lo tanto, hay dos fuentes de falsos positivos al consultar el filtro de Bloom al atravesar el gráfico de Bruijn. Existe la probabilidad de que uno o más de los tres falsos k-mers existan en otra parte del conjunto de secuenciación para devolver un falso positivo, y existe la tasa de falsos positivos inherente mencionada anteriormente del filtro Bloom en sí. Las herramientas de ensamblaje que utilizan filtros Bloom deben tener en cuenta estas fuentes de falsos positivos en sus métodos. ABySS 2 [8] y Minia [9] son ejemplos de ensambladores que utilizan este enfoque para el ensamblaje de novo .
Corrección de errores de secuenciación
Los métodos de secuenciación de próxima generación (NGS) han permitido la generación de nuevas secuencias del genoma mucho más rápido y más barato que los métodos de secuenciación de Sanger anteriores . Sin embargo, estos métodos tienen una tasa de error más alta, [10] [11] lo que complica el análisis posterior de la secuencia e incluso puede dar lugar a conclusiones erróneas. Se han desarrollado muchos métodos para corregir los errores en las lecturas de NGS, pero utilizan grandes cantidades de memoria, lo que los hace poco prácticos para genomas grandes, como el genoma humano. Por lo tanto, se han desarrollado herramientas que utilizan filtros Bloom para abordar estas limitaciones, aprovechando su uso eficiente de la memoria. Musket [12] y BLESS [13] son ejemplos de tales herramientas. Ambos métodos utilizan el enfoque del espectro k-mer para la corrección de errores. El primer paso de este enfoque es contar la multiplicidad de k-mers, sin embargo, mientras BLESS solo usa filtros Bloom para almacenar los recuentos, Musket usa filtros Bloom solo para contar k-mers únicos y almacena k-mers no únicos en un tabla hash, como se describe en un trabajo anterior [14]
RNA-Seq
Los filtros Bloom también se emplean en algunas tuberías de RNA-Seq . RNA-Skim [15] agrupa las transcripciones de RNA y luego utiliza filtros Bloom para encontrar sig-mers: k-mers que solo se encuentran en uno de los grupos. Estos firmantes se utilizan luego para estimar los niveles de abundancia de la transcripción. Por lo tanto, no analiza todos los k-mer posibles, lo que da como resultado mejoras en el rendimiento y el uso de la memoria, y se ha demostrado que funciona tan bien como los métodos anteriores.
Referencias
- ^ Lundeberg, Joakim; Arvestad, Lars; Andersson, Björn; Allander, Tobias; Käller, Max; Stranneheim, Henrik (1 de julio de 2010). "Clasificación de secuencias de ADN mediante filtros Bloom" . Bioinformática . 26 (13): 1595-1600. doi : 10.1093 / bioinformatics / btq230 . ISSN 1367-4803 . PMC 2887045 . PMID 20472541 .
- ^ Lundeberg, Joakim; Arvestad, Lars; Andersson, Björn; Allander, Tobias; Käller, Max; Stranneheim, Henrik (1 de julio de 2010). "Clasificación de secuencias de ADN mediante filtros Bloom" . Bioinformática . 26 (13): 1595-1600. doi : 10.1093 / bioinformatics / btq230 . ISSN 1367-4803 . PMC 2887045 . PMID 20472541 .
- ^ Chu, Justin; Sadeghi, Sara; Raymond, Anthony; Jackman, Shaun D .; Nip, Ka Ming; Mar, Richard; Mohamadi, Hamid; Butterfield, Yaron S .; Robertson, A. Gordon (1 de diciembre de 2014). "Herramientas de BioBloom: detección de secuencias de especies hospedadoras rápida, precisa y eficiente en memoria mediante filtros de floración" . Bioinformática . 30 (23): 3402–3404. doi : 10.1093 / bioinformatics / btu558 . ISSN 1367-4811 . PMC 4816029 . PMID 25143290 .
- ^ Wood, Derrick E .; Salzberg, Steven L. (3 de marzo de 2014). "Kraken: clasificación de secuencia metagenómica ultrarrápida usando alineaciones exactas" . Biología del genoma . 15 (3): R46. doi : 10.1186 / gb-2014-15-3-r46 . ISSN 1474-760X . PMC 4053813 . PMID 24580807 .
- ^ Carl Kingsford; Solomon, Brad (marzo de 2016). "Búsqueda rápida de miles de experimentos de secuenciación de lectura corta" . Biotecnología de la naturaleza . 34 (3): 300–302. doi : 10.1038 / nbt.3442 . ISSN 1546-1696 . PMC 4804353 . PMID 26854477 .
- ^ Iqbal, Zamin; McVean, Gil; Rocha, Eduardo PC; Bakker, Henk C. den; Bradley, Phelim (febrero de 2019). "Búsqueda ultrarrápida de todos los datos genómicos bacterianos y virales depositados" . Biotecnología de la naturaleza . 37 (2): 152-159. doi : 10.1038 / s41587-018-0010-1 . ISSN 1546-1696 . PMC 6420049 . PMID 30718882 .
- ^ Brown, C. Titus; Tiedje, James M .; Howe, Adina; Canino-Koning, Rosangela; Hintze, Arend; Pell, Jason (14 de agosto de 2012). "Montaje de secuencia de metagenoma de escala con gráficos probabilísticos de Bruijn" . Actas de la Academia Nacional de Ciencias . 109 (33): 13272-13277. arXiv : 1112.4193 . Código bibliográfico : 2012PNAS..10913272P . doi : 10.1073 / pnas.1121464109 . ISSN 0027-8424 . PMC 3421212 . PMID 22847406 .
- ^ Birol, Inanc; Warren, Rene L .; Coombe, Lauren; Khan, Hamza; Jahesh, Golnaz; Hammond, S. Austin; Yeo, Sarah; Chu, Justin; Mohamadi, Hamid (1 de mayo de 2017). "ABySS 2.0: ensamblaje eficiente de recursos de genomas grandes utilizando un filtro Bloom" . Investigación del genoma . 27 (5): 768–777. doi : 10.1101 / gr.214346.116 . ISSN 1088-9051 . PMC 5411771 . PMID 28232478 .
- ^ Chikhi, Rayan; Rizk, Guillaume (16 de septiembre de 2013). "Representación gráfica de Bruijn exacta y eficiente en el espacio basada en un filtro Bloom" . Algoritmos de Biología Molecular . 8 (1): 22. doi : 10.1186 / 1748-7188-8-22 . ISSN 1748-7188 . PMC 3848682 . PMID 24040893 .
- ^ Loman, Nicholas J .; Misra, Raju V .; Dallman, Timothy J .; Constantinidou, Chrystala; Gharbia, Saheer E .; Wain, John; Pallen, Mark J. (mayo de 2012). "Comparación de rendimiento de plataformas de secuenciación de alto rendimiento de sobremesa". Biotecnología de la naturaleza . 30 (5): 434–439. doi : 10.1038 / nbt.2198 . ISSN 1546-1696 . PMID 22522955 . S2CID 5300923 .
- ^ Wang, Xin Victoria; Blades, Natalie; Ding, Jie; Sultana, Razvan; Parmigiani, Giovanni (30 de julio de 2012). "Estimación de las tasas de error de secuenciación en lecturas cortas" . BMC Bioinformática . 13 : 185. doi : 10.1186 / 1471-2105-13-185 . ISSN 1471-2105 . PMC 3495688 . PMID 22846331 .
- ^ Schmidt, Bertil; Schröder, Jan; Liu, Yongchao (1 de febrero de 2013). "Musket: un corrector de errores basado en el espectro k-mer de varias etapas para los datos de secuencia de Illumina" . Bioinformática . 29 (3): 308–315. doi : 10.1093 / bioinformatics / bts690 . ISSN 1367-4803 . PMID 23202746 .
- ^ Hwu, Wen-Mei; Ma, Jian; Chen, Deming; Wu, Xiao-Long; Heo, Yun (15 de mayo de 2014). "BLESS: solución de corrección de errores basada en filtros Bloom para lecturas de secuenciación de alto rendimiento" . Bioinformática . 30 (10): 1354-1362. doi : 10.1093 / bioinformatics / btu030 . ISSN 1367-4803 . PMC 6365934 . PMID 24451628 .
- ^ Pellow, David; Filippova, Darya; Kingsford, Carl (1 de junio de 2017). "Mejora del rendimiento del filtro Bloom en datos de secuencia utilizando filtros Bloom k-mer" . Revista de Biología Computacional . 24 (6): 547–557. doi : 10.1089 / cmb.2016.0155 . ISSN 1066-5277 . PMC 5467106 . PMID 27828710 .
- ^ Zhang, Zhaojun; Wang, Wei (15 de junio de 2014). "RNA-Skim: un método rápido para la cuantificación de RNA-Seq a nivel de transcripción" . Bioinformática . 30 (12): i283 – i292. doi : 10.1093 / bioinformatics / btu288 . ISSN 1367-4803 . PMC 4058932 . PMID 24931995 .