Cinco mudanças são o mínimo necessário. Uma das árvores mais parcimoniosas segue.
Segue uma matriz ultramétrica que resolve o problema e a árvore ultramétrica que lhe corresponde.
A B C D E A 0 3 2 2 3 B 3 0 3 3 2 C 2 3 0 2 3 D 2 3 2 0 3 E 3 2 3 3 0 
Uma possível inferência segue. Em vermelho os haplótipos reusados.
00102 → 00101, 00100
10021 → 10001, 10011
22201 → 10001, 01101
10221 → 10011, 10101
O problema de montagem de fragmentos de DNA consiste em reconstruir uma longa seqüência de DNA a partir de um grande número de trechos curtos originados de qualquer das duas fitas.
Este problema aparece porque com a tecnologia atual não é possível seqüenciar diretamente longos trechos de DNA. Tem-se que partir a molécula aleatoriamente e seqüenciar a partir de uma extremidade do fragmento até atingir a resolução da técnica, que pode ser de algumas dezenas de bases até várias centenas de bases.
CAP3 usa o paradigma overlap-layout-consensus. Primeiro, determinam-se as sobreposições entre os fragmentos. Depois, estes são montados em contigs. Por fim, para cada contig um consenso é construído a partir do alinhamento múltiplo dos fragmentos.
EULER usa uma estratégia diferente. Os fragmentos são substituídos pelo conjunto de suas l-tuplas, onde l é um inteiro fixo. Um grafo de de Bruijn é construído e caminhos neste grafo dão origem aos contigs.
A maior dificuldade em montar grande genomas é colocada pelas regiões repetidas que aparecem neles.
Uma ordenação segue. Os trechos permutados estão sublinhados.
3 1 4 6 2 5
3 1 2 5 4 6
3 1 2 4 5 6
1 2 3 4 5 6
O grafo associado tem 1 ciclo. Como uma transposição pode criar no máximo 2 ciclos, e temos n=6 blocos, são necessários no mínimo (n+1-c)/2 = 6/2 = 3 movimentos. Logo, a solução dada é ótima.
Uma ordenação segue. Os trechos revertidos estão sublinhados.
-2 -3 4 1 5 6
-2 -1 -4 3 5 6
1 2 -4 3 5 6
1 2 -3 4 5 6
1 2 3 4 5 6
O grafo associado tem 3 ciclos. Como uma reversão pode criar no máximo 1 ciclo, e temos n=6 blocos, são necessários no mínimo n+1-c = 4 movimentos. Logo, a solução dada é ótima.
Uma ordenação segue. Os trechos envolvidos estão sublinhados. O tipo de operação está escrito ao lado.
(-3 1) (4 6 -2) (5)fusão
(4 6 -2 -1 3) (5)reversão
(4 6 1 2 3) (5)fissão
(4 6) (1 2 3) (5)translocação
(4 5) (1 2 3) (6)fusão
(4 5 6) (1 2 3)
Note que na penúltima operação não poderíamos inserir diretamente o 5 entre o 4 e o 6, pois trata-se de um cromossomo linear. Se usássemos um DCJ para torná-lo circular, poderíamos inseri-lo entre 4 e 6 no próximo passo, ficando também com 5 movimentos.
O grafo associado, após colocação e tratamento das caps, tem b=10 e c=5 ciclos. Como uma operação DCJ pode decrementar b-c em no máximo 1 unidade, são necessários no mínimo b-c = 5 movimentos. Logo, a solução dada é ótima.
Uma ordenação segue. Os trechos envolvidos estão sublinhados. O tipo de operação está escrito ao lado. Operações que não contam (reversões de cromossomos inteiros, troca de ordem entre cromossomos) estão sem tipo.
(-6 2 1) (4 -5 3)translocação interna
(-6 2 3) (4 -5 1)translocação interna
(-6 -5 1) (4 2 3)
(1 5 6) (4 2 3)translocação interna
(1 2 3) (4 5 6)
O grafo associado tem 1 ciclo preto. O limite inferior neste caso é n - N - c = 6 - 2 - 1 = 3. Logo, a solução dada é ótima.