Nesta postagem apresentaremos a definição do Problema da Cadeia de Caracteres mais Próxima, porém antes introduziremos algumas notações que possibilitarão uma melhor compreensão do PCCP.
Seja Σ = {c1,...,ck} um conjunto finito de elementos, denominado caracteres, a partir dos quais cadeias de caracteres podem ser construídas. Cada cadeia de caracteres corresponde a uma seqüência (s1,...,sm), com si ∈ Σ, onde Σ é o alfabeto utilizado. O tamanho de uma cadeia de caracteres s, denotado por |s|, corresponde ao número de elementos (ou caracteres) na seqüência que compõe a cadeia s. Por exemplo, se s = (s1,...,sm) então |s| = m.
Várias medidas têm sido propostas para encontrar as similaridades (ou diferenças) entre as seqüências. A mais utilizada é a distância de Hamming. Uma justificativa mais técnica para o uso freqüente da distância de Hamming na comparação de seqüências em biologia molecular. A distância de Hamming entre duas cadeias de caracteres, denotada por dH(a,b), tal que |a| = |b|, corresponde ao número de posições nas quais as seqüências diferem. Assim, para o alfabeto Σ = {A,C,G,T} e as cadeias de caracteres a = CATCC e b = CTTGC temos dH(a,b) = 2.
Considere agora um conjunto S = {s1,...,sn} de cadeia de caracteres, com |si| = m, deseja-se encontrar uma seqüência t, com |t| = m, que minimize o valor da distância k, tal que, dH(si,t) ≤ k para cada cadeia de caracteres si ∈ S.
Como dito anteriormente, o Problema da Cadeia de Caracteres mais Próxima é NP-difícil. Os autores demonstraram que para um k fixo, o PCCP pode ser resolvido em tempo polinomial.
