de vez en cuando tengo que revisar un viejo script para actualizar mi copia local del Protein Data Bank (PDB). El programa descarga solamente las estructuras que han cambiado mediante rsync y otros ficheros de un servidor FTP.
Sin embargo, las rutas a las respectivas carpetas van cambiando y yo tengo que actualizarlas. En concreto, hoy habían cambiado las listas de secuencias no redundantes, que ahora se pueden encontrar en ftp://resources.rcsb.org/sequence/clusters
Leyendo descubro que en el PDB ahora agrupan sus secuencias usando MMseq2 / Linclust, dos métodos relacionados que calculan de manera muy eficiente la similitud entre secuencias a partir de su composición de K-meros con un alfabeto reducido, temas de los que ya hemos hablado por ejemplo aquí y aquí. Me centraré en Linclust.
Algoritmo de clustering de coste lineal. Fuente: https://www.nature.com/articles/s41467-018-04964-5 |
Según el banco de pruebas publicado por sus autores, a diferencia de otras alternativas, el algoritmo Linclust tiene un coste lineal pero un comportamiento parecido, con pérdidas controlables de sensibilidad. Consta de varias fases:
- Transformación de las secuencias originales a una alfabeto reducido de 13 letras. Obtienen resultados óptimos haciendo las siguientes simplificaciones: (L, M), (I, V), (K, R), (E, Q), (A, S, T), (N, D), (F, Y)
- Generación de una tabla de K-meros con K entre 10 y 14. De cada secuencia solamente guardan 20 K-meros, elegidos por su frecuencia alta con una función hash.
- Búsqueda de secuencias con idénticos K-meros
- Pre-clustering en varios pasos, de más a menos eficientes: distancia de Hamming con alfabeto completo, alineamientos locales sin y con gaps.
- Clustering voraz con las secuencias ordenadas por longitud
hasta pronto,
Bruno