A software to help in selection of specifics regions in biological sequences
DOI:
https://doi.org/10.5753/isys.2018.373Keywords:
Specific segments, Amplification, PCR, Specific region, Specific Primer, ProbeAbstract
The Specific Segment Selection Problem takes as input two or more DNA sequences and gives as output the shortest substring in one of them that has at least k differences from any substring of the other sequences. This problem is recurrent in Biology, and its solution can be used, for example, in the design of specific primers, that allows an accurate amplification of specific regions of DNA in laboratory under a PCR protocol. Given the importance of these specific regions in the detection and diagnosis of infectious diseases, we present in this paper the development of a WEB client/server software that can help people interested in the selection of specific substring from genome sequences. Our software uses two algorithms that solve the k Difference Primer Problem, chosen experimentally among four that were coded and evaluated by us.
Downloads
Download data is not yet available.
References
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.
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.
Downloads
Published
2018-12-10
How to Cite
Dobre, J. A., & Adi, S. S. (2018). A software to help in selection of specifics regions in biological sequences. ISys - Brazilian Journal of Information Systems, 11(3), 127–151. https://doi.org/10.5753/isys.2018.373
Issue
Section
Systems and prototypes, and their application cases
