COMPARAÇÃO DE SEQUÊNCIAS DE CORONA VIRUS LIGADOS À SARS
	=======================================================

Primeira Etapa do Projeto de MAC0465
Prazo de Entrega: até 28/4 às 15hs

Numa primeiro exame no banco de dados genômico Genbank foram coletadas
224 sequências publicadas de janeiro a março de 2020 e que contêm
sequências genômicas de corona viri que provocam a SARS (Síndrome
Aguda Respiratória Severa), isolados em seres humanos das mais
diversas nacionalidades. É o arquivo seq20200327-224covid19.fasta presente no
diretório

   https://www.ime.usp.br/~alair/mac0465/

Destas 224 sequências, 156 possuem comprimento acima de 29000,
correspondendo a um sequenciamento completo do vírus. As demais 68
possuem comprimento não superior a 1260, o tamanho do CDS completo dos
viri obtidos de oito chineses. Das 156 sequências, 107 delas não
possuem ambiguidades oriundas do sequenciamento, e todas as posições
possuem uma das bases A C T ou G. Em particular, estas 107 não usam o
caractere N, que representa a possibilidade de que haja qualquer uma
das quatro bases, nem outros caracteres que representam abiguidades
mais restritas.

Nesta primeira etapa do projeto deve-se:

- instalar a biblioteca biopython, de forma a ler as diversas
  sequências armazenadas no arquivo em formato FASTA

- implementar a função BestScore da página 59 do livro, de modo a
  calcular e devolver a pontuação do alinhamento ótimo entre duas
  sequências s e t, para um sistema de pontuação descrito pelos
  parâmetros match, mismatch e gap.

  def BestScore(s,t,match,mismatch,gap):
      m=len(s)
      n=len(t)
      #...
      return a[n]

- implementar a função BestScoreStrip, que reune a funcionalidade de
  BestScore da página 59 com KBand da página 68, numa versão que trate
  o caso |s| != |t|. A função deve usar memória linear, como
  BestScore, e deve computar e usar apenas uma parte da matriz de
  programação dinâmica como aquela vista em nossa "lousa" online,
  reproduzido no arquivo Lousa.png. Observe que se antes as diagonais
  d utilizadas variavam no intervalo [ -k .. +k ] no algoritmo KBand,
  elas passarão a variar no intervalo [ n - m - k .. +k ] no algoritmo
  BestScoreStrip, supondo que m >= n.
  
  def BestScoreStrip(s,t,k,match,mismatch,gap):
      m=len(s)
      n=len(t)
      # ...
      return a[n]

Em princípio, estas funções podem ser aplicadas a cada par dentre as
107 sequências obtidas. Com pequenas alterações também se pode
acrescentar o tratamento dos casos com posições ambíguas, tratando-as
como sendo sempre uma desigualdade (mismatch), por exemplo.

Mais à frente será descrito como usar estas funções para obter uma
filogenia. Em princípio, deve-se computar a pontuação de alinhamentos
ótimos de cada par de sequências.