Formalizações

Através dos fragmentos de DNA seqüenciados em laboratório, queremos obter o DNA original. É natural associar esse problema ao:

Problema 1 (Mínima Supercadeia Comum - MSC)   Dado um conjunto de strings s₁, s₂,..., s_k sobre um alfabeto $\Sigma$, encontrar a seqüência mais curta possível S tal que cada s_i seja um fator de S, ou seja, S=us_iv para certos u e v sobre $\Sigma$.

Este problema é NP-difícil. Embora pareça bastante adequado no contexto da montagem de fragmentos, há algumas ressalvas que devem ser feitas:

Erros na entrada:

Como vimos, o processo de seqüenciamento pode gerar fragmentos contaminados pelo DNA do vetor e/ou alterados por mutações (embora este último seja um evento raro). O MSC não leva em conta tais fatos.

Orientação:

O seqüenciamento é feito em DNA de fita simples. É muito comum que os fragmentos gerados sejam oriundos de fitas diferentes. Porém, cada molécula possui extremidades bem definidadas (nomeadas 3' e 5'). Cada uma das fitas do DNA-duplo se encontra em um a orientação diferente (3'-5' e 5'-3'). Logo, a molécula gerada na montagem deve cobrir cada fragmento ou seu complemento reverso.

Cobertura insuficiente:

Embora o shotgun procure minimizar este problema, é possível que os fragmentos não cubram a extensão total da molécula original (Figura 3). Devemos, nestes casos, tentar encontrar uma ou mais seqüências que cubram todos os fragmentos.

Comprimento da molécula original:

O esforço do MSC em minimizar o comprimento da resposta é para evitar respostas triviais (como a simples concatenação dos fragmentos). No problema de montagem, os biólogos podem, com grande precisão, determinar o comprimento da molécula alvo.

Assim, podemos redefinir o problema, tornando-o mais próximo da realidade biológica:

Problema 2 (Montagem de Fragmentos)   Dado um conjunto de strings s₁, s₂,..., s_k sobre um alfabeto $\Sigma=\{A, C, T, G\}$, encontrar a seqüência S tal que, para cada s_i:

$Sim(s_{i}, S) > \alpha$
ou
$Sim(s_{i}^{CR}, S) > \alpha$

Onde Sim(f, F) é uma função que retorna um valor associado a similaridade entre as duas seqüências e $\alpha$ é a similaridade mínima requerida.

Um versão mais completa faria uma restrição sobre S, para que seu comprimento fosse próximo do tamanho estimado pelos biólogos. Por hora, trataremos desta versão mais simplificada do problema.