| Journal: | Revista mexicana de ingeniería biomédica |
| Database: | PERIÓDICA |
| System number: | 000404593 |
| ISSN: | 0188-9532 |
| Authors: | Alba, A1 Rubio Rincón, M1 Rodríguez Kessler, M1 Arce Santana, E.R1 Méndez, M.O1 |
| Institutions: | 1Universidad Autónoma de San Luis Potosí, Facultad de Ciencias, San Luis Potosí. México |
| Year: | 2012 |
| Season: | Dic |
| Volumen: | 33 |
| Number: | 2 |
| Pages: | 87-99 |
| Country: | México |
| Language: | Español |
| Document type: | Artículo |
| Approach: | Experimental, aplicado |
| Spanish abstract | En bioinformática, una de las principales herramientas que permiten la localización de características comunes en cadenas de proteínas o ADN de distintas especies es la búsqueda aproximada de cadenas. Desde el punto de vista computacional, la dificultad de la búsqueda aproximada de cadenas radica en encontrar medidas adecuadas para comparar dos cadenas de manera eficiente, dado que en muchos casos se desea realizar búsquedas en tiempo real, dentro de bases de datos de gran tamaño. En este artículo se propone un método novedoso para la búsqueda aproximada de cadenas basado en una generalización del algoritmo propuesto por Baeza-Yates y Perleberg en 1996 para calcular la distancia de Hamming entre dos secuencias, y una etapa de post-procesamiento que permite reducir de manera significativa el número de falsos positivos reportados por el algoritmo. El método propuesto ha sido evaluado a través de casos sintéticos con secuencias aleatorias, y con casos reales de secuencias de proteínas de plantas. Los resultados muestran que el algoritmo propuesto es altamente eficiente en términos computacionales y en especificidad, en particular al ser comparado con un método publicado anteriormente, basado en la correlación de fase |
| English abstract | In bioinformatics, one of the main tools which allow scientists to find common characteristics in protein or DNA sequences of different species is the approximate matching of strings. From the computational point of view, the difficulty of approximate string matching lies in finding adequate measures to efficiently compare two strings, since, in many cases, one is interested in performing searches in real time, within large databases. In this paper we propose a novel method for approximate string matching based on a generalization of the algorithm proposed by Baeza-Yates and Perleberg in 1996 for computing the Hamming distance between two sequences. In addition, a post-processing stage which significantly reduces the number of false positives is presented. The proposed method has been evaluated in synthetic cases of random sequences, and with real cases of plant protein sequences. Results show that the proposed algorithm is highly efficient in computational terms and in specificity, especially when compared against a previously published method, which is based on the phase correlation function |
| Disciplines: | Medicina, Ciencias de la computación |
| Keyword: | Procesamiento de datos, Bioquímica, Ingeniería biomédica, Secuencia proteica, Bioinformática, Búsqueda de secuencias, Algoritmos |
| Keyword: | Medicine, Computer science, Data processing, Biochemistry, Biomedical engineering, Protein sequence, Bioinformatics, Sequence searching, Algorithms |
| Full text: | Texto completo (Ver HTML) |
