#   Time-stamp: <03/10/02 18:21:44 alair at tutu.ime.usp.br>  

Especifica��o do exerc�cio programa 2
=====================================

Pede-se nesta fase do projeto de biologia computacional que o aluno implemente
um algoritmo de contru��o de uma �rvore de sufixos.  Este algoritmo deve
faz�-lo em tempo linear no tamanho da seq��ncia fornecida.

A data de entrega do referido trabalho �:  25/10/03

Deve-se desenvolver uma �rvore de sufixos usando-se a descri��o presente no
cap�tulo 2 do livro "T�picos em Algoritmos sobre Seq��ncias". 

Uso eficiente de mem�ria
========================

(Um dos problemas muitas vezes abordados nas implementa��es de �rvores de
sufixos � a quantidade de mem�ria utilizada pela �rvore.  Quem n�o estiver
interessado numa implementa��o eficiente no uso de mem�ria, pode pular esta se��o.)

Na se��o de notas bibliogr�ficas comenta-se sobre a implementa��o mais eficiente no
uso de espa�o atualmente conhecida, desenvolvida por Kurtz '98.

O arquivo redspace.ps.gz cont�m o artigo "Reducing the space requirement of
suffix trees" de Kurtz.  A estrutura de dados proposta por Kurtz pode 
ser usada ou servir de inspira��o para algum aluno que queira construir uma
implementa��o tamb�m eficiente em espa�o.  Sua estrutura de dados pode ser
usada tanto pelo algoritmo de McCreight quanto pelo de Ukkonen.  Neste artigo, ele
exp�e as modifica��es necess�rias ao algoritmo de McCreight (fig 7, pg 22).
Toda a se��o 6 discute este algoritmo e as se��es 2 e 3.1 t�m v�rias
defini��es que poder�o ser necess�rias ao entendimento da se��o 6.

A implementa��o SLLI proposta na se��o 3.1 � perfeitamente suficiente, mas as
se��es 4.1 e 4.2 podem ser �teis para quem quiser entender e/ou se aventurar a
implementar a solu��o ILLI, mais eficiente no uso de espa�o.  Em particular, h� a
defini��o de n�s internos pequenos e grandes, e na se��o 6 esta terminologia
aparece em alguns coment�rios e tamb�m na figura 7 (a manipula��o das vari�veis
p, q e campo distance).  Para a solu��o SLLI, o campo suffixlink precisa ser corretamente
atualizado como descrito em sala, dado que a figura 7 aplica-se mais
diretamente � implementa��o ILLI.

Um eventual leitor atento perceber� que, na figura 7, a linha

   _
   u := headloc.suffixlink    /* case 2.2.2 */

n�o faz sentido e deve ser corrigida para:

   _    _
   u := u.suffixlink    /* case 2.2.2 */


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

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

  as [op��es] arquivo

onde arquivo cont�m a seq��ncia em formato FASTA a ser lida.
O programa deve reconhecer ao menos 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

Estat�sticas
============

As estat�ticas a serem listadas s�o:
n�mero de n�s internos (inclui-se a raiz)
n�mero de folhas
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 listar ao menos (quando forem
definidas) as seguintes informa��es associadas aos n�s:
  n�mero do n�
  headposition
  profundidade (de string)
  os n�meros dos n�s que s�o apontados a partir deste n� (firstchild,
  branchbroather, suffixlink, 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
======

Os aqruivos xae.seq e teste.seq ser�o testados com os programas submetidos.
  
Bom trabalho.

--
Alair
  
------------------    
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();

  ...