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