O Problema da seleção de segmentos específicos: algoritmos e aplicações

Abstract

The Specific Segment Selection Problem takes as input two or more DNA sequences, and gives as output the shortest segment in one of them that has at least k differences from any segments of the other sequences. This problem is recurrent in Biology, whose solution enables, among other things, an accurate amplification of specific regions of DNA in laboratory. With this it is possible to detect and diagnose infectious diseases, and to identify the pathogen that causes the infection. The Specific Segment Selection Problem can be solved through a computational problem called k Diference Primer Problem. Although over time several approaches have been proposed to solve this last problem, with efficient algorithms, we know that some of them have a high cost of processing and memory usage, which makes its application impractical. With this in mind, and considering that, to the best of our knowledge, no studies have been carried out to compare these algorithms, we propose here a detailed study of the different known approaches to the k Diference Primer Problem, making an evaluation of the related algorithms by using artificial and real tests and using the best of them in the development of a software that can be used effectively by biologists and others interested in the selection of specific segments.