O Problema da seleção de segmentos específicos: algoritmos e aplicações - Dobre, Jean Alexandre (2017)
O Problema da Seleção de Segmentos Específicos consiste em, dadas duas ou mais sequências de DNA, encontrar o menor segmento em uma delas que tenha pelo menos k diferenças com relação a todos os segmentos das outras sequências. Esse problema é recorrente na Biologia, cuja solução possibilita, dentre outras coisas, uma amplificação precisa de regiões específicas de DNA em laboratório. Com isso é possível detectar e diagnosticar doenças infecciosas, e identificar o patógeno causador da infecção. O Problema da Seleção de Segmentos Específicos pode ser resolvido através de um problema computacional denominado Problema do Primer com k Diferenças. Embora ao longo do tempo algumas abordagens tenham sido propostas para esse último, com algoritmos cada vez mais eficientes, sabemos que alguns têm um alto custo de processamento e uso de memória, o que torna inviável sua aplicação na prática. Com isso em mente, e considerando que, até onde sabemos, nenhum estudo foi realizado para fazer uma comparação entre esses algoritmos, propomos aqui um estudo detalhado das diferentes abordagens conhecidas para resolver o Problema do Primer com k Diferenças, fazendo uma avaliação dos algoritmos relacionados com casos de testes artificiais e reais e utilizando o melhor deles no desenvolvimento de um sistema que possa ser utilizado de forma efetiva por biólogos e outros interessados na seleção de segmentos específicos.