# 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(); ...