Um sistema para auxiliar na seleção de regiões específicas de sequências biológicas
Palavras-chave:
segmento específico, primers, sondas, probes, bioinformática, casamento inexato, w3sResumo
O Problema da Seleção de Segmentos Específicos recebe como entrada duas ou mais sequências de DNA e devolve como saída o menor segmento de uma das sequências que possui pelo menos k diferenças com relação a todos os segmentos das outras sequências. Esse problema é recorrente na Biologia, e sua solução pode ser utilizada, por exemplo, no desenho de primers específicos, que permite, usando a técnica de PCR, uma amplificação exata de regiões específicas de DNA em laboratório. Dada a importância dessas regiões específicas na detecção e no diagnóstico de doenças infecciosas, nós apresentamos neste artigo o desenvolvimento de uma aplicação WEB cliente/servidor que pode ajudar pessoas interessadas na seleção de segmentos específico de sequências genômicas. Nossa aplicação usa dois algoritmos que resolvem o Problema do Primer com k diferenças, escolhidos experimentalmente dentre quatro que foram implementados e avaliados por nós.Downloads
Referências
Abd-Elsalam, K. A. (2003). Bioinformatic tools and guideline for pcr primer design. african Journal of biotechnology, 2(5):91–95.
Adi, S. S., Rocha, L. B., and Araujo, F. E. S. (2018). Specific substring problem: an application in bioinformatics. In 11th Brazilian Symposium on Bioinformatics.
Alberts, B., Johnson, A., Lewis, J., Raff, M., Roberts, K., and Walter, P. (2009). Biologia Molecular da Célula. Artmed Editora.
Baeza-Yates, R. A. and Perleberg, C. H. (1992). Fast and practical approximate string matching. In Annual Symposium on Combinatorial Pattern Matching, pages 185–192. Springer.
Chang, W. I. and Lawler, E. L. (1990). Approximate string matching in sublinear expected time. In Foundations of Computer Science, 1990. Proceedings., 31st Annual Symposium on, pages 116–124. IEEE.
Cormen, T., Leiserson, C., Rivest, R. L., and Stein, C. (2012). Algoritmos: Teoria e Pratica. Campus, Rio de Janeiro, 3 edition.
de Castro Miranda, R. C., Ayala-Rincón, M., and Solon, L. (2005). Modifications of the Landau-Vishkin Algorithm Computing Longest Common Extensions via Suffix Arrays and Efficient RMQ Computations.
de Lima, L. I. S. (2013). O Problema do Alinhamento de Segmentos. Master’s thesis, FACOM-UFMS.
Deitel, M. and Deitel, P. (2005). C++ como programar. 5a edição. Editora Pearson, São Paulo.
Gusfield, D. (1997). Algoritms on strings, trees, and sequences: Computer Science and Computational Biology. Cambridge University Press.
Hennessy, J. L. and Patterson, D. A. (2014). Organizacão e Projeto de Computadores: a interface hardware/software, volume 4. Elsevier Brasil
Huynh, T. N., Hon, W.-K., Lam, T.-W., and Sung, W.-K. (2006). Approximate string matching using compressed suffix arrays. Theoretical Computer Science, 352(1):240–249.
Ito, M., Shimizu, K., Nakanishi, M., and hashimoto, A. (1995). Polynomial-time Algorithms for Computing Characteristic Strings. Systems and Computers in Japan, 26(3):30–38.
Landau, G. M. and Vishkin, U. (1989). Fast parallel and serial approximate string matching. Journal of Algorithms, 10(2):157–169.
Loudon, K. (2000). Dominando algoritmos com C. Editora Ciencia Moderna Ltda, São Paulo.
Marshall, O. J. (2004). Perlprimer: cross-platform, graphical primer design for standard, bisulphite and real-time pcr. Bioinformatics, 20(15):2471–2472.
Masek,W. J. and Paterson, M. S. (1980). A faster algorithm computing string edit distances. Journal of Computer and System sciences, 20(1):18–31.
Montera, L. and Nicoletti, M. (2008). The pcr primer design as a metaheuristic search process.Artificial Intelligence and Soft Computing–ICAISC 2008, pages 963–973.
Mullis, K. B., Ferre, F., Gibbs, R., and Morley, B. J. (1995). PCR-the polymerase chain reaction. Trends in Genetics, 11(6):249–249.
Myers, E. W. (1994). A sublinear algorithm for approximate keyword searching. Algorithmica, 12(4-5):345–374.
Pressman, R. and Maxim, B. (2016). Engenharia de Software-8a Edição. McGraw Hill Brasil.
Ribeiro, M. C. M. (2009). Genética Molecular. Universidade Federal de Santa Catarina. Biologia/EaD/UFSC, Florianópolis.
Ristad, E. S. and Yianilos, P. N. (1998). Learning string-edit distance. Pattern Analysis and Machine Intelligence, IEEE Transactions on, 20(5):522–532.
Saikkonen, R. and Soisalon-Soininen, E. (2008). Cache-sensitive memory layout for binary trees. In Fifth IFIP International Conference On Theoretical Computer Science–TCS 2008, pages 241–255. Springer.
Sutter, H. (2006). Programação avançada em C++. Pearson-Mahron Books, São Paulo.
Ukkonen, E. (1995). On-line construction of suffix trees. Algorithmica, 14(3):249–260.
Valimaki, N., Makinen, V., Gerlach, W., and Dixit, K. (2009). Engineering a compressed suffix tree implementation. Journal of Experimental Algorithmics (JEA), 14:2.
Ye, J., Coulouris, G., Zaretskaya, I., Cutcutache, I., Rozen, S., and Madden, T. L. (2012). Primer-blast: A tool to design target-specific primers for polymerase chain reaction. BMC Bioinformatics, 13(1):134.
