#   Time-stamp: <03/11/22 18:11:21 alair at tutu.ime.usp.br>  


Especificação do exercício programa 3  (definitivo)
===================================================

A finalidade deste exercício programa é escrever um programa que obtenha um
alinhamento local de máxima pontuação entre duas seqüências.  Tal como no
primeiro exercício-programa.  Contudo, será introduzida uma heurística,
semelhante à do BLAST. Isto acelerará o método que, de outra forma teria
comportamento quadrático, e permitirá comparações de seqüências maiores.

Para tanto, supomos a seguinte heurística.  Sejam S e T as duas seqüências que
queremos comparar.  Sejam dados os parâmetros nr, nq, nG, nE, nW e nX.
Obtemos todos os pares maximais (i,j,l) (definidos por S[i..i+l-1] ==
T[j..j+l-1], S[i-1] != T[j-1], S[i+l] != T[j+l]) tais que
l>=nW, onde nW é o comprimento mínimo l de cada hit.  Cada S[i..i+k-1] é
alinhado a cada T[j..j+k-1], para 1<=k<=l, e esta é a semente de um
alinhamento local que será extendido em ambas as direções.  Estas extensões
são feitas por métodos de programação dinâmica, com a diferença de que existem
alguns limites.  Uma extensão numa direção é interrompida caso a pontuação
obtida seja mais que nX pontos menor que a melhor pontuação obtida para o
corrente alinhamento local.  Para a extensão à direita, por exemplo, obtém-se
a melhor pontuação de um prefixo de S[i+l..|S|] com um prefixo de T[j+l..|T|]
e que não envolva uma queda de pontuação maior que nX pontos.  Para a extensão
à esquerda, obtém-se a melhor pontuação de um sufixo de S[1..i-1] com um
sufixo de T[1..j-1] e que não envolva uma queda de pontuação maior que nX
pontos.  Escolhe-se o alinhamento local obtido da maneira acima com maior
pontuação e deve-se listar este alinhamento.

Os pares maximais acima devem ser obtidos através do uso de árvores de
sufixos.  Uma maneira (não obrigatória) de fazer isto é através da construção
da árvore de sufixos da seqüência S#T$ onde # e $ são duas letras diferentes
das que ocorrem em S e T. Então procuram-se os pares maximais (como visto
durante o estudo de repetições (vide nota 2).  Na implementação, o aluno integrará o
algoritmo de construção de uma árvore de sufixos em tempo linear do segundo
exercício-programa ao algorítmo de alinhamento local do primeiro exercício.
 
A data de entrega do referido trabalho é:  02/12/03

Interface do programa
=====================

Pede-se que o programa (suporei seu nome como sendo 'myblast') tenha o seguinte modo de uso:

  myblast [opções] arquivo1 arquivo2

onde arquivo1 e arquivo2 contêm as seqüências em formato FASTA a serem lidas.
O programa deve reconhecer ao menos as opções:

-r nr : o número nr é o valor da pontuação para cada identidade (match)
-q nq : o número nq é o valor da pontuação para cada símbolo desemparelhado
        (mismatch) e normalmente é negativo
-G nG : o número nG é a penalidade por abertura de Gap
        (não é necessário implementar esta opção, supondo pois que nG=0)
-E nE : o número nE é a penalidade pela extensão de um Gap
        um único Gap é penalizado com nG + nE enquanto que dois Gaps consecutivos
        são penalizados com nG + 2*nE
-X nX : o número nX é o parâmetro drop-off explicado anteriormente
-W nW : o número nW é o comprimento mínimo de um hit

-p : lista-se uma tabela com estatísticas sobre os pares maximais

Sobre a árvore de sufixos, permancem as opções: 

-s : dá uma informação de algumas estatísticas
-d : lista toda a árvore de sufixos
-v : listagem verborrágica (verbose)
-i : lista a árvore com indentação


Quanto à tabela das estatísticas dos pares maximais, em cada linha devem-se
listar os valores i, j, l, do par maximal, bem como os valores: p, id, jd, ie,
je, cd, pd, ce, pe.

O valor p é a pontuação do alinhamento local obtido a partir do par maximal em
questão.
O alinhamento local obtido alinha S[ie..id] a T[je..jd].
O valor cd é o número de células na matriz de programação
dinâmica calculadas na extensão à direita e pd é a pontuação da parte do
alinhamento da extensão à direita obtida.  De outra maneira, cd é o número de
células (x,y) visitadas na extensão à direita.  Que a célula (x,y) seja
visitada implica que x>=i+l e y>=j+l e que você calculou a pontuação do melhor
alinhamento entre S[i+l..x] e T[j+l..y].  Por razões de eficiência, espera-se que
nenhum destes pares (x,y) visitados tenha pontuação do alinhamento abaixo do
valor (pico-nX), a não ser para os pontos (x,y) que são casos de fronteira
(para os quais a extensão foi interrompida e onde pela primeira vez se obteve
pontuação de alinhamento abaixo do valor pico - nX).
Este valor pico pode ser pd ou pode ser simplesmente a maior pontuação
de uma célula visitada por este alinhamento ótimo associado a (x,y).
Os valores ce e pe correspondem para a extensão à esquerda.

Estatísticas
============

As estatíticas a serem listadas são:
número de nós internos da árvore de sufixos (inclui-se a raiz)
número de folhas da árvore
número de arestas que levam a nós internos
número de bytes necessários para guardar esta árvore
  obs: se a linguagem for Perl ou java, esta informação é facultativa 
número máximo de filhos de um nó (kmax)
altura da árvore (altura máxima de um nó) (hmax)
  a raiz tem altura 1, um nó imediatamente abaixo tem altura 2, etc

Uma listagem verborrágica das estatísticas deve também listar informações num
formato matricial onde cada linha está associada a uma altura h, para
1<=h<=hmax, e cada coluna está associada a um número de filhos k, para
0<=k<=kmax.  Em cada posição desta matriz deve-se listar  
o número de nós com altura h que têm k filhos.
Deve-se acrescentar uma coluna final com os totais da linha e uma linha final
com os totais das colunas.

Recomenda-se não armazenar estas informações na árvore mas construir estas
estatísticas, somente se requeridas, a partir de uma varredura em profundidade
(depth-first) na árvore de sufixos.

Listagem da árvore
==================

Numa listagem da árvore, cada nó é listado numa linha.  Caso a árvore deva ser
listada com indentação, deve-se imprimir antes da primeira informação da linha
um total de h-1 espaços em branco, onde h é a altura do nó em questão.

Uma listagem sumária da árvore deve listar os rótulos de cada nó da árvore,
onde o rótulo de um nó é o string obtido pela concatenação de todas as arestas
da raiz até este nó.  O rótulo pode ser imediatamente obtido a partir das
informações headposition e profundidade.

Uma listagem verborrágica da árvore deve ser feita através de busca em
profundidade e deve listar ao menos (quando forem
definidas) as seguintes informações associadas aos nós:
  número do nó (se for índice de um vetor)
  cabeça
  profundidade de palavra
  os números dos nós que são apontados a partir deste nó
   (primog, irmao, sufixo, etc)
  o número do nó que é pai do nó corrente
  o rótulo da aresta que liga o pai até o nó corrente

Observe que numa visita em profundidade à árvore, o pai de um nó é uma
informação naturalmente disponível, assim como a altura do nó na árvore.


Reconhecimento dos parâmetros
=============================
  
Para o reconhecimento dos parâmetros, recomenda-se usar a função getopt (da
biblioteca C, cabeçalho em unistd.h).  Neste caso o formato será simplesmente
"sdvi".  Logo abaixo há um exemplo de um código que usa esta função.  Pode-se
encontrar mais informação sobre a função com

  man 3 getopt

num sistema unix.  Para quem usar Perl, use a função Getopt::Std.

  man 3 Getopt::Std


Testes
======

O arquivo TESTES descreverá os testes ainda em estudo e que serão deixados no
diretório onde se encontra este enunciado.
  
Bom trabalho.

--
Alair
  
------------------    
NOTA 1

void	Usage(void){
  printf ("rdistr [-r num] [-q num] [-E num] [-G num] [-n ntests] [-w windowlength] [-s|-g|-l] file\n");
  exit(1);
}

int	main(int argc, char *argv[]) {
  int	MatchScore=1;
  int	MismatchScore=0;
  int	GapExtension=0;
  int	GapOpen=0;
  int   NTests=100000;
  int   Length=100;
  int opt;
  enum {semiglobal,global,local} method = semiglobal;

  /* read parameters */
  
  while ( (opt=(getopt( argc, argv, "r:q:E:G:n:w:sgl"))) != -1 ){
    switch(opt) {
    case 'r':
      MatchScore = atoi(optarg);
      break;
    case 'q':
      MismatchScore = atoi(optarg);
      break;
    case 'G':
      GapOpen = atoi(optarg);
      break;
    case 'E':
      GapExtension = atoi(optarg);
      break;
    case 'n':
      NTests = atoi(optarg);
      break;
    case 'w':
      Length = atoi(optarg);
      break;
    case 'l':
      method = local;
      break;
    case 's':
      method = semiglobal;
      break;
    case 'g':
      method = global;
      break;
      
    }
  }

  /* optind is a global variable set to the first index of argv that is not an option */  
  
  if (argc - optind != 1)
    Usage();

  ...  


--------------------------------------
NOTA 2
Vide ítem 7.12.3 do livro do Gusfield. Uma cópia escaniada do ítem
7.12 encontra-se no arquivo gusfield.zip.