Determinação do Consenso (Montagem)

Munidos da árvore gerada pela fase de refinamento, podemos obter a molécula original. A cada vértice de V, associamos um consenso. Um consenso é um vetor tal que consenso[i] é uma listas das candidatos a ocupar a posição i (Figura 9). Cala candidato é composto de uma base $B \in \Sigma=\{A, C, T ,G, \Box\}$, onde $\Box$ denota um ``buraco'', isto é, um espaço vago na seqüência, e de um número inteiro que indica quantas vezes tal base foi indicada para ocupar esta posição.

Figure 9: Fragmento Consenso.

Seja $c[v], v \in V$ o consenso associado ao vértice v. Inicialmente, c[v] é obtido de s[v] de forma bastante simples: há apenas uma base candidata para cada posição com uma indicação apenas. A partir daí, iremos comprimir as arestas de A, como indicado na Figura 10.

Um vértice de A é dito preto quando ele não possui vértices filhos. Caso o vértice possua filhos e estes sejam todos pretos, dizemos que o vértice é cinza. Em último caso, quando o vértice possui filhos de mais de uma cor, dizemos que ele é branco. A cada vértice preto, iremos comprimir sua aresta com seu vértice pai. Continuaremos este processo até restar um único vértice preto sem pai.

Quando comprimimos a aresta entre dois vértices u e v, geramos um vértice w tal que c[w] seja um consenso obtido de c[u] e c[v] através de um algoritmo de alinhamento, semelhante ao visto em [SF 98]. Como indicado na Figura 11, um alinhamento entre consensos pode reforçar os votos de certos candidatos ou até mesmos propor novos candidatos para uma certa posição i.

Ao final, quando obtivermos um único vértice r, definimos a molécula original como uma string s tal que:

s[i]=MaxBase(c[r][i])

onde MaxBase(L) é a base mais votada na lista L.

Figure: Colapso dos vértices na fase de montagem.

Figure 11: Alinhamento entre Consensos.