Em Ciência da Computação Teórica , e em particular em texto algorítmico , a cadeia mais próxima (English Closest string ) de um conjunto de dados de cadeias de caracteres é uma distância mínima das cadeias de canais, de acordo com a distância de Hamming . A busca pela cadeia mais próxima é um problema algorítmico NP-difícil .
Para as cinco cadeias
BARACADABRA |
ABRAACDABRA |
RBRACADABCA |
ACRACADABCA |
ABRADADABCA |
o canal mais próximo é
ABRACADABRA |
É remoto 2 dos canais fornecidos. As coincidências são marcadas em vermelho:
BA RACADABRA |
ABRA AC DABRA |
R BRACADAB C C |
A C RACADAB C A |
ABRA D ADAB C A |
Dados n cadeias s 1 , ..., s n do mesmo comprimento m , o problema da cadeia mais próxima consiste em determinar uma nova cadeia s de comprimento m tal que d ( s , s i ) ≤ k para todo i , onde d é a distância de Hamming , e onde k é o menor possível. O problema de decisão correspondente, que é NP-completo , também pega o inteiro k como entrada e pergunta se há uma string que está à distância de Hamming no máximo k de todas as strings fornecidas. O problema é NP-difícil, mesmo em um alfabeto binário.
Em bioinformática , o problema da cadeia mais próxima é um aspecto muito estudado do problema de detecção de sinal em DNAs . O problema também tem aplicações na teoria do código (problema do raio mínimo). O problema de substring mais próximo formaliza aplicações biológicas na busca de regiões conservadas, na identificação de alvos genéticos de drogas e na geração de sondas genéticas em biologia molecular. Em algoritmos de texto , é um problema de combinatória de cadeias de caracteres. Esse problema de cadeia e outros que surgem em uma variedade de aplicações, desde mineração de texto até análise de sequência biológica, costumam ser NP-difíceis . Isso motiva a busca por casos especiais tratáveis de parâmetros fixos desses problemas. Isso faz sentido nos casos em que há vários parâmetros naturalmente associados, como o tamanho do alfabeto, o número de strings ou um limite superior na distância.
O problema da cadeia mais próxima pode ser visto geometricamente como uma instância do problema de 1 centro com a distância de Hamming como sua distância.
As instâncias de problema da cadeia mais próxima podem conter informações que não são significativas para o problema, ou seja, não contribuem para a dificuldade do problema. Por exemplo, se algumas strings contêm o caractere a , e nenhuma contém o caractere z , substituir todo a por z dá uma instância essencialmente equivalente, ou seja, de uma solução de instância modificada, a solução original pode ser facilmente restaurada e vice-versa.
Escrevendo as strings de entrada uma abaixo da outra, obtemos uma matriz. Certos tipos de linhas têm essencialmente as mesmas influências na solução. Por exemplo, substituir uma coluna que tem as entradas ( a , a , b ) por uma coluna ( x , x , y ) pode levar a uma string de solução diferente, mas não pode afetar a solvência, porque ambas as colunas expressam a mesma estrutura., onde as duas primeiras entradas são iguais, mas diferentes da terceira.
Uma instância de entrada pode ser normalizada substituindo, em cada coluna, o caractere que ocorre mais frequentemente com a , o caractere que ocorre em segundo lugar com b e assim por diante. Dada uma solução da instância normalizada, a instância original pode ser recuperada substituindo os caracteres na solução por sua versão original em cada coluna. A ordem das colunas não contribui para a dificuldade do problema. Isso significa que se permutamos as strings de entrada de acordo com alguma permutação π e se obtivermos uma string de solução s para essa instância modificada, então π −1 ( s ) é uma solução da instância original.
Consideramos uma instância formada pelas três palavras uvwx , xuwv e xvwu (veja o diagrama acima). Na forma de uma matriz, obtemos a seguinte tabela:
você | v | C | x |
x | você | C | v |
x | v | C | você |
Na primeira coluna ( u , x , x ), é o símbolo x que aparece com mais frequência (2 vezes); nós o substituímos por a e o caractere u por b , o que dá a nova primeira coluna ( b , a , a ). A segunda coluna ( v , u , v ) é substituída, pela mesma estratégia, por ( a , b , a ). Procedendo da mesma forma para as outras colunas, acabamos com
b | no | no | no |
no | b | no | b |
no | no | no | vs |
A normalização tem como consequência que o tamanho do alfabeto é no máximo igual ao número de strings de entrada. Isso pode ser útil para algoritmos cujo tempo de computação depende do tamanho do alfabeto.
Li et al. descreveram um esquema de aproximação em tempo polinomial , mas que é inutilizável na prática por causa de grandes constantes ocultas.
O problema das cordas mais próximo pode ser resolvido por O ( nL + nd × d d ) , onde n é o número de cordas fornecidas como entrada, L é o comprimento comum de todas as cordas e d é a distância desejada da solução para todos os dados cordas. Portanto, está na classe de complexidade parametrizada FPT ( parâmetros fixos tratáveis ).
O problema da cadeia mais próxima é um caso especial do problema mais geral da substring mais próxima (in) é estritamente mais difícil. Embora o problema da cadeia mais próxima seja tratável por parâmetros fixos de maneiras diferentes, o problema da substring W [1] é difícil com relação a esses parâmetros. A kernelização desses e de problemas relacionados foi o assunto de um estudo detalhado que mostra que ou podemos obter um kernel polinomial ou que tal kernel não pode ser obtido sob as suposições usuais na teoria da complexidade, e em particular a hipótese do tempo exponencial (ETH ) Esses problemas são encontrar uma subestrutura ou superestrutura comum a um determinado conjunto de cadeias. Os problemas mais básicos são a subsequência comum mais longa , a supersequência comum mais curta e a menor sequência comum. Além disso, existe o problema mais geral do alinhamento de múltiplas sequências , que é de extrema importância na análise de sequências biológicas .