As Fases da Montagem

Podemos considerar três passos para a montagem:

Comparação Rápida:

Imagine um conjunto de 500 strings sobre $\Sigma = \{A, T, C,$ G} geradas como saída do shotgun. Espera-se que cada um destes fragmentos se sobreponha a um certo número de outras seqüências. Este número, porém, deve ser bem menor do que 500.

A comparação por Sim(X, Y) é bastante cara em termos de tempo de processamento, pois o algoritmo é O(mn). Se os 500 fragmentos tiverem comprimento em torno de 600 bases cada um, o custo da comparação dois a dois seria $C^{500}_{2}*(600*600) \sim 4.5*10^{10}$!

Torna-se necessário um meio mais barato de comparação, tendo como objetivo indicar para os algoritmos da próxima fase quais são os fragmentos que valem a pena serem analisados por Sim(X, Y), isto é, os fragmentos que têm uma semelhança mínima entre si de modo a valer a pena compará-los por programação dinâmica.

O objetivo desta fase será, portanto, gerar um grafo G=(V, E) onde cada vértive $v \in V$ representa um fragmento de entrada e só existe uma aresta $(u, v) \in E$ se e somente há uma semelhança mínima entre os fragmentos representados por u e v.

Refinamento:

O objetivo aqui é refinar os dados obtidos na fase anterior. Seja s[v] o fragmento associado ao vértice $v \in V$. Para cada aresta $(u, v) \in E$, chamamos Sim(s[u], s[v]). Se a similaridade entre os fragmentos estiver acima de um mínimo pré-estabelecido, a aresta (u, v) é mantida. Caso contrário, removemos (u, v) de E.

Após o refinamento, um algoritmo para cálculo de árvores geradoras máximas é utilizado no grafo G, gerando uma árvore A=(V_A, E_A). A idéia é manter um conjunto minimal de arestas que resultam na maior similaridade total.

Determinação do Consenso (Montagem):

Resta agora obtermos o DNA original. Para isso, seguiremos a árvore gerada na fase anterior: para cada $u, v \in E_{A}$ tal que v = filho[u], geramos um vértice w tal que s[w] seja a seqüência consenso entre s[u] e s[v]. Para cada aresta oriunda do vértice u, isto é, da forma $(u, z) \in E_{A}$, criamos uma aresta correspondente (w, z). Redefinimos A=(V_A^*, E_A^*) onde:

$V_{A}^{*}=(V_{A}-\{u, v\}) \cup \{w\}$
e
$E_{A}^{*}=(E_{A}-E_{u}) \cup E_{w}$
sendo: $E_{u} = \{(x, y) \in E_{A} \vert x=u\}$ e $E_{w} = \{(x, y) \in E_{A} \vert x=w\}$

Repetimos este processo até restar um único vértice r na árvore A. A seqüência s[r] será nosso consenso geral, ou seja, a molécula original.

Nas próximas seções detalharemos melhor cada uma destas fases.