Caros alunos,

Como já foi dito em sala (vide aulas dos dias 22 e 25 de maio), nesta
próxima fase do trabalho, vocês devem obter e propor uma
reconstituição filogenética para a sequências covid fornecidas. Além
das 107 sequências completas sem qualquer ambiguidade, enumeradas de 0
a 106, estamos acrescentando à lista a sequência 107, italiana com uma
única ambiguidade e id MT066156.

O arquivo mutacoes108.txt contém um relatório sintético dos
alinhamentos ótimos entre a sequência de referência, id NC_045512, e
cada uma das demais. Ao invés de imprimir todas as colunas do
alinhamento, este relatório deixa de imprimir as colunas onde há
identidade de símbolos. Além de várias estatíticas sobre as mutações
pontuais, ele relata cada inserção, remoção e substituição destes
alinhamentos. As posições destas substituições na sequência constituem
as características binárias que serão usadas como dados da
reconstituição filogenética: a presença de um símbolo idêntico ao da
sequência de referência, corresponde ao estado 0; a presença de um
símbolo diferente, constitui o estado 1. São ao todo 415
substituições, sendo envolvidas 202 posições (sempre da sequência de
referência, a menos que dito em contrário). Algumas posições devem ser
porém descartadas, devido ao fato de participarem em regiões que
admitem alinhamentos ótimos alternativos, vizinhos a inserções ou
remoções. Isto inclui a posição 1, mas também as posições finais de
29871 a 29903, com alinhamentos alternativos provocados pelas
repetições presentes na cadeia de polyadenina destas posições.

Desta forma, as mutações consideradas (a menos que dito em contrário
estaremos sempre nos referindo apenas às substituições ocorridas nas
posições de 2 a 29870) são reduzidas a um total de 363, envolvendo 182
posições distintas.

cat mutacoes108.txt | egrep -v -- '-> -' | egrep -v -- '- ->' | egrep -- '->' | sort -n | awk '$1 <=29870 && 2 <= $1 { print $1 }' | uniq | wc

Para nossa felicidade, as mutações relativas a uma mesma posição são
homogêneas e apenas numa posição há uma sequência onde há mutação para
um terceiro símbolo. De fato, a cada posição p dentre as 182 posições que
sofrem mutações (0,6% das quase trinta mil posições) podemos associar
o conjunto Seq(p) de sequências que sofrem mutações na posição
p. É de se admirar que em meio a um número exponencial de
possíveis subconjuntos haja tanta repetição de subconjunto de
sequências. Por exemplo, são 35 as sequências que sofrem mutação na
posição 8782, enquanto que são as mesmas 35 sequências que sofrem
mutação numa posição extremamente distante como 28144, pertencente a  
outro gene e codificando outra proteína! Ainda que 1/3 das sequências tenham
sofrido cada uma das mutações, é de se admirar que nenhum exemplar de
uma sequência em que só uma das posições sofreu mutação tenha sido
sequenciada e publicada! De toda maneira, se são 94 sequências
distintas entre si nas 108 sequências, temos cerca de 2^94 (mais que
1,6 x 10^28) subconjuntos de sequências possíveis de serem associados
às 182 posições que sofreram mutações. Ocorre que são apenas 94 os
subconjuntos que são associados a estas 182 mutações sofridas, de modo que,
para o algoritmo de reconstituição filogenética, podemos agrupar
diferentes posições cujas mutações correspondentes ocorrem exatamente
no mesmo subconjunto de sequências. Cada grupo de posições assim
formado é o que chamaremos de característica, a partir de agora.

De acordo com a definição 6.1 e o lema 6.1, pode ocorrer que algumas
destas características sejam incompatíveis entre si. Isto ocorre
quando Seq(p1) e Seq(p2) não são disjuntos nem o de menor
cardinalidade está contida no outro.

A partir do arquivo mutacoes108.txt fornecido, você deve obter nesta
fase do projeto um conjunto maximal de características que sejam duas
a duas compatíveis entre si, bem como uma filogenia perfeita para as
108 sequências associada a estas características.

Contudo, há características incompatíveis entre si. Não propomos a
elaboração de um algoritmo de seleção de características compatíveis e
adotaremos o critério de descartar características incompatíveis com
outras de maior cardinalidade que não tenham sido descartadas, que
funciona bem para o nosso caso.

***

Se são n (=108) as sequências, há repetições. Sejam m (=94) as
sequências distintas entre si duas a duas. No que diz respeito à
árvore filogenética, ela é constituída de uma árvore enraizada com uma
folha para cada uma das m sequências distintas. A cada nó associamos o
conjuntos das sequências da sub-árvore associada a este nó, de modo
que à raiz estão associadas as sequências todas. Quando uma aresta é
rotulada com uma característica (como aquela rotulada por C4 na figura
6.2), ela particiona a árvore em dois subconjuntos: a componente com o
nó filho e todas as folhas da subárvore deste nó, cujas sequências
(A,C,e E, para este exemplo tomado na figura 6.2) correspondentes
possuem estado 1 nas mutações sofridas nas posições desta
característica; a componente restante onde se encontram o conjunto das
sequências que possuem estado 0 (B e D, no mesmo exemplo), inclusive a
sequência de referência. Há também arestas que não são rotuladas e que
não particionam nada, apenas unem diferentes partes da árvore,
permitindo "puxar" arestas de um vértice interno para as folhas que
representam sequências associadas a estes vértices internos (na figura
6.2, é o caso das arestas que ligam as folhas A e E a seus respectivos
nós internos.) Em particular, poder-se-á observar que existem várias
sequências que, embora não sendo idênticas à de referẽncia de Wuhan,
não sofreram qualquer mutação (de substituição) e que são unidas à
raiz através de arestas não rotuladas.

O arquivo Sequencias.py fornecido para esta fase pode ser usado em
maior ou menor grau. Está sendo fornecido principalmente para explicar
algumas linhas de código presentes no arquivo mac0465.py, que contém a
definição da classe Filo, que deriva da classe MeuGrafo.
Historicamente, MeuGrafo foi concebida e usada para desenhar filogenia
baseada em matriz de distâncias. A classe Filo contém o método
CospeSVG, que deve ser usado para apresentar a árvore filogenética que
vocês estão a gerar. A forma de apresentação da árvore filogenética
então gerada mostra-se mais apropriada que a da figura 6.2 para grande
quantidade de sequências.

***

Esta classe foi disponibilizada em duas versões do arquivo mac0465.py,
a do dia 1/6 e a do dia 10/6. Na primeira versão deste módulo, fizemos
uso de dois dicionários globais Part2RepPos e Vertice2Particao, que
são usados na minha solução para o problema. Vertice2Particao mapeia
um vértice do grafo na partição (uma lista) de vértices associados à
sub-árvore deste vértice. Se for uma folha, a partição contém apenas
este vértice, e se for a raiz, contém o conjunto de todas as
sequências. Part2RepPos mapeia a representação de uma Partição
devolvida por RepresentaParticao na semelhante representação da lista
de posições p tais que o conjunto das sequências que sofreram mutação
na posição p seja a referida partição de vértices. Estas variáveis
globais, bem como FullSeqs, foram removidas para a elaboração de um
exemplo de uso da classe Filo que imprima uma árvore filogenética
topologicamente equivalente à da Figura 6.2. Ao usar a nova versão
para as 108 sequências fornecidas, é importante que o rótulo de uma
aresta criada com o método {aresta} da classe seja uma representação
das posições p que sofrem mutação exatamente nas sequências da
subárvore do nó filho desta aresta. Esta lista de posições pode ser
eventualmente vazia.

Bom trabalho a todos.

Alair