Pacote MPRS vs. 9.1 Mar 2003 Estela Maris Rodrigues -------------------------------------------------------------------- Este pacote contém os códigos fonte dos programas listados a seguir: MAF PRINTTREE RANDOM SCRAMBLE Esses programas foram desenvolvidos por Estela Maris Rodrigues em 2001-2002 como parte de seu trabalho na tese de doutoramento "Algoritmos para Comparação de Árvores Filogenéticas e o Problema dos Pontos de Recombinação" [1]. Conteúdo deste documento: - O que estes programas fazem - Para quais sistemas eles estão disponíveis - Obtenção dos fontes - Instalação e compilação dos fontes - Opções de linha de comando - MAF - Opções de linha de comando - PRINTTREE - Opções de linha de comando - RANDOM - Opções de linha de comando - SCRAMBLE - Exemplos de uso - Impressão de instâncias - Exemplos de uso - Tamanho das florestas de concordância - Exemplos de uso - Obtenção das florestas de concordância - Exemplos de uso - Geração e teste de instâncias O que estes programas fazem --------------------------- MAF é um programa que calcula uma aproximação com garantia de desempenho constante para o tamanho da floresta de concordância ótima entre duas árvores filogenéticas dadas como entrada. A garantia de desempenho mínima oferecida pelo programa é 3. Os algoritmos de construção de florestas de concordância suportados por esta versão do MAF são os algoritmos 1, 2, 3, 4 e 5 em [2]. PRINTTREE é um utilitário de formataçäo de árvores filogenéticas, desenhado para formatar as florestas de concordância fornecidas como saída pelo programa MAF. Árvores com graus superiores a 2 nos nós são suportadas. RANDOM é um utilitário de geração de instâncias do problema da floresta de concordância ótima que usa o algoritmo de geração de árvores descrito a seguir. Inicialmente, uma árvore filogenética com um único nó é criado. A partir daí, executa-se n-1 vezes a seguinte sequência de operações, sendo n o número de folhas especificado pelo usuário. Sorteia-se um nó da árvore que está sendo construída e estende-se esse nó. Com isso, um novo nó de grau 1 é criado na árvore. Em seguida, cria-se um novo nó, que é conectado a esse nó de grau 1. A escolha do nó a ser estendido é feita sorteando-se um inteiro p de 1 a 2(n-1), e em seguida tomando-se o (p-1)-ésimo sucessor da raiz dessa árvore em pré-ordem ([1], Capítulo 5). SCRAMBLE é um outro utilitário de geração de instâncias do problema da floresta de concordância ótima, que utiliza transferências de subárvore, segundo o algoritmo descrito a seguir. Se o programa lê um par de árvores da entrada, ele imprime a primeira árvore desse par na saída; caso ele gere uma árvore aleatoriamente, ele imprime essa árvore na saída. Em seguida, o programa executa sobre a árvore gerada aleatoriamente, ou sobre a segunda árvore lida da entrada, uma sequência de t operações de transferência de subárvore escolhidas aleatoriamente, sendo t o número de transferências especificado pelo usuário. A árvore resultante é, então, impressa na saída, compondo assim, junto com a árvore impressa anteriormente, uma entrada para o programa MAF ([1], Capítulo 5). Para quais sistemas eles estão disponíveis ------------------------------------------ Unix. A implementação foi testada em ambiente Debian GNU/Linux 2.2. Obtenção dos fontes ------------------- Através da página WEB http://www.ime.usp.br/~estela/ime-tese.html ou pelo e-mail estela@ime.usp.br Instalação e Compilação dos fontes ---------------------------------- Os arquivos fonte para o MPRS vs. 9 estão armazenados em um arquivo chamado mprs9.2.tar.gz. Para instalar o pacote, descompacte o arquivo mprs9.2.tar.gz. Essa operação criará um diretório chamado mprs no seu diretório corrente, contendo os arquivos fonte do pacote. estela@debian:~> tar xvzf mprs9.2.tar.gz mprs/allocation.c mprs/allocation.h mprs/compile-maf mprs/compile-printtree mprs/compile-random mprs/compile-scramble mprs/defs.h mprs/dictionary.c mprs/dictionary.h mprs/error.c mprs/error.h mprs/forests.c mprs/forests.h mprs/input.c mprs/input.h mprs/intreepre.c mprs/intreepre.h mprs/ioforests.c mprs/ioforests.h mprs/iotreeadj.c mprs/iotreeadj.h mprs/lidt.h mprs/litems.h mprs/maf.c mprs/maf.h mprs/mafops.c mprs/mafops.h mprs/mainmaf.c mprs/mainprinttree.c mprs/mainrandom.c mprs/mainscramble.c mprs/mapping.c mprs/mapping.h mprs/mktreepre.c mprs/mktreepre.h mprs/output.c mprs/output.h mprs/outtreepre.c mprs/outtreepre.h mprs/sprops.c mprs/sprops.h mprs/treepre.c mprs/treepre.h mprs/utreepre.c mprs/utreepre.h estela@debian:~> Na listagem acima há quatro arquivos com nome iniciando por compile: compile-maf, compile-printtree, compile-random e compile-scramble. Esses arquivos devem ser executados a partir da linha de comando. Para que eles funcionem, o compilador gcc deve estar instalado. estela@debian:~> cd mprs estela@debian:~/mprs> compile-maf estela@debian:~/mprs> compile-printtree estela@debian:~/mprs> compile-random estela@debian:~/mprs> compile-scramble estela@debian:~/mprs> Com isso, são criados os arquivos binários maf, printtree, random e scramble. Opções de linha de comando - MAF -------------------------------- Abaixo listamos as opções para cada programa, e damos uma rápida explicação para cada opção. estela@debian:~/mprs> maf -h MAF by E. M. Rodrigues - 01/2003. Usage: maf [options] Options: -h: displays this help -f : reads in trees from (default=stdin) -o : writes out results to (default=stdout) -i: shows lexical items -m: shows moves -r: shows restriction -c: shows cases -n: shows number of components -1: runs algorithm 2 for the MAF_2 problem (default) -k : specifies bar{k} (default=2) -2: runs algorithm 5 for the MAF problem -3: runs algorithm 3 for the MAF_2 problem -5: runs algorithm 4 for the MAF_2 problem MAF: Done. estela@debian:~/mprs> As opções importantes são -h, -f, -o, -r, -n, -k, -1, -2, -3, -5. As opções -i, -m e -c são usadas apenas para depuração do programa e não serão discutidas aqui. Opção -h: mostra o help acima. Opções -f e -o : especificam respectivamente os arquivos de entrada e saída do programa. Se -f não estiver presente, o arquivo de entrada é a entrada padrão. Se -o não estiver presente, o arquivo de saída é a saída padrão. O arquivo especificado com a opção -f deve conter um par de árvores filogenéticas no formato especificado em [1], Capítulo 5. Opções -r e -n: especificam o tipo de saída desejada pelo usuário. Se o usuário especificar -r, então será impresso na saída especificada com o parâmetro -o ou na saída padrão um arquivo contendo a representação de uma floresta de concordância para a entrada especificada, no formato descrito em [1], Capítulo 5. Se o usuário especificar -n, será impresso o número de componentes de uma floresta de concordância para a entrada especificada. Ao menos um destes dois parâmetros deve estar presente. É aconselhável utilizar o utilitário PRINTTREE com a opção -r (ver Exemplos de uso). Opções -1 a -5 e -k : especificam o algoritmo que será usado para construir a floresta de concordância. Se nenhuma dessas opções está presente, então o algoritmo usado é o algoritmo 2. Opções de linha de comando - PRINTTREE -------------------------------------- estela@debian:~/mprs> printtree -h PRINTTREE by E. M. Rodrigues - 01/2003. Usage: printtree [options] Options: -h: displays this help -f : reads in trees from (default=stdin) -o : writes out results to (default=stdout) -i: shows lexical items PRINTTREE: Done. estela@debian:~/mprs> Opção -h: mostra o help acima. Opções -f e -o : similares ao programa MAF. Opção -i: usada apenas para depuração. Opções de linha de comando - RANDOM ----------------------------------- estela@debian:~/mprs> random -h RANDOM by E. M. Rodrigues - 01/2003. Usage: random [options] Options: -h: displays this help -o : writes out results to (default=stdout) -l: makes labels -s : sets random seed -n : sets number of leaves RANDOM: Done. estela@debian:~/mprs> Opção -h: mostra o help. Opção -o : similares ao programa MAF. Opção -l: gera rótulos nos nós internos. Se não estiver presente, o programa gera rótulos apenas para as folhas das árvores. Opção -s : permite passar um valor inicial ao gerador aleatório empregado pelo programa. Se não estiver presente, o gerador aleatório é inicializado usando-se o relógio do sistema. Opção -n : especifica quantas folhas devem ter as árvores geradas. Deve estar presente. Opções de linha de comando - SCRAMBLE ------------------------------------- estela@debian:~/mprs> scramble -h SCRAMBLE by E. M. Rodrigues - 01/2003. Usage: scramble [options] Options: -h: displays this help -f : reads in a pair of trees from (default=stdin) -o : writes out results to (default=stdout) -l: makes labels -s : sets random seed -n : sets number of leaves -t : sets number of sttransfer operations (default=0) -r: makes random trees (reads from file if not specified) SCRAMBLE: Done. estela@debian:~/mprs> Opção -h: mostra o help. Opções -f e -o : similares ao programa MAF. Opção -r: especifica se as árvores sobre as quais as transferências de subárvore vão ser aplicadas devem ser geradas pelo programa ou se elas devem ser lidas da entrada. Se não estiver presente, as árvores são lidas da entrada padrão ou do arquivo especificado com a opção -f. Opções -l e -s : similares ao programa RANDOM. Se -r não está presente, então -l é ignorada. Opção -n : especifica quantas folhas devem ter as árvores geradas. Se -r não está presente, então -n é ignorada. Opção -t : especifica o número de transferências de subárvore que serão aplicadas. Deve estar presente. Exemplos de uso - Impressão de instâncias ----------------------------------------- Suponhamos para os exemplos a seguir que o diretório ~ contém um subdiretório chamado data, onde estão os arquivos de dados example002 e example003, contendo uma árvores com grau no máximo 2 nos nós internos, e example014, em que uma das árvores tem um nó interno com grau 3. Abaixo listamos o conteúdo desses três arquivos: estela@debian:~/mprs> cat ../data/example002 ((((((((((A2,A5),A1),(A10,(A6,A9))),A3),A11),A8),A12),A7),A13),A4); (((((A1,((A2,A3),(A4,A5))),(((A6,A7),(A8,A9)),A10)),A11),A12),A13); estela@debian:~/mprs> cat ../data/example003 (((((((((((((((((((((((((((((((((((((((((((((((((A17,A18),A19),A20),A21), A22),A23),A24),A25),A26),A27),A28),A29),A30),A31),A32),A33),A9),A34),A10), A35),A11),A36),A12),A37),A13),A38),A14),A39),A15),A40),A16),A41),A5),A42), A6),A43),A7),A44),A8),A45),A1),A46),A3),A47),A0),A48),A4),A49),A2); (((((((((((((((((((((((((((((((((((((((((((((((((A17,A0),A9),A5),A18),A19), A1),A10),A20),A21),A11),A2),A22),A23),A6),A12),A24),A25),A13),A7),A26),A27), A4),A14),A28),A29),A15),A3),A30),A31),A8),A16),A32),A33),A34),A35),A36), A37),A38),A39),A40),A41),A42),A43),A44),A45),A46),A47),A48),A49); estela@debian:~/mprs> cat ../data/example014 ((((A1,A5)I1,A2)I2,A3)I3,A4)I4; (A1,(A2,A3,(A4,A5)J1)J2)J3; estela@debian:~/mprs> Para imprimir as instâncias contidas no arquivo example002: estela@debian:~/mprs> printtree -f ../data/example002 PRINTTREE by E. M. Rodrigues - 01/2003. Input file: "../data/example002". Output file: stdout. +--+A2 +--+ | +--+A5 +--+ | +--+A1 +--+ | | +--+A10 | +--+ | | +--+A6 | +--+ | +--+A9 +--+ | +--+A3 +--+ | +--+A11 +--+ | +--+A8 +--+ | +--+A12 +--+ | +--+A7 +--+ | +--+A13 +--+ +--+A4 +--+A1 +--+ | | +--+A2 | | +--+ | | | +--+A3 | +--+ | | +--+A4 | +--+ | +--+A5 +--+ | | +--+A6 | | +--+ | | | +--+A7 | | +--+ | | | | +--+A8 | | | +--+ | | | +--+A9 | +--+ | +--+A10 +--+ | +--+A11 +--+ | +--+A12 +--+ +--+A13 PRINTTREE: Done. estela@debian:~/mprs> Para imprimir as instâncias contidas no arquivo example014: estela@debian:~/mprs> printtree -f ../data/example014 PRINTTREE by E. M. Rodrigues - 01/2003. Input file: "../data/example014". Output file: stdout. +--+A1 +--+I1 | +--+A5 +--+I2 | +--+A2 +--+I3 | +--+A3 +--+I4 +--+A4 +--+A1 +--+J3 | +--+A2 | | | +--+A3 +--+J2 | +--+A4 +--+J1 +--+A5 PRINTTREE: Done. estela@debian:~/mprs> Exemplos de uso - Tamanho de florestas de concordância ------------------------------------------------------ Para calcular uma 3-aproximação para o tamanho da floresta de concordância ótima das árvores em example002 usando o algoritmo A_2: estela@debian:~/mprs> maf -f ../data/example002 -n MAF by E. M. Rodrigues - 01/2003. Input file: "../data/example002". Output file: stdout. 5 MAF: Done. estela@debian:~/mprs> Para calcular uma 4-aproximação para o tamanho da floresta de concordância ótima das árvores em example002 usando o algoritmo A_1: estela@debian:~/mprs> maf -f ../data/example002 -n -k 1 MAF by E. M. Rodrigues - 01/2003. Input file: "../data/example002". Output file: stdout. 12 MAF: Done. estela@debian:~/mprs> Para calcular uma 3-aproximação para o tamanho da floresta de concordância ótima das árvores em example003 usando o algoritmo A_2: estela@debian:~/mprs> maf -f ../data/example003 -n MAF by E. M. Rodrigues - 01/2003. Input file: "../data/example003". Output file: stdout. 48 MAF: Done. estela@debian:~/mprs> Para calcular uma 3,67-aproximação para o tamanho da floresta de concordância ótima das árvores em example003 usando o algoritmo A_3: estela@debian:~/mprs> maf -f ../data/example003 -n -1 -k 3 MAF by E. M. Rodrigues - 01/2003. Input file: "../data/example003". Output file: stdout. 18 MAF: Done. estela@debian:~/mprs> Para calcular uma 4-aproximação para o tamanho da floresta de concordância ótima das árvores em example014 usando o algoritmo D: estela@debian:~/mprs> maf -f ../data/example014 -n -2 MAF by E. M. Rodrigues - 01/2003. Input file: "../data/example014". Output file: stdout. 4 MAF: Done. estela@debian:~/mprs> Exemplos de uso - Obtenção das florestas de concordância -------------------------------------------------------- Para imprimir a floresta de concordância obtida pela execução do último exemplo acima: estela@debian:~/mprs> maf -f ../data/example014 -r -2 MAF by E. M. Rodrigues - 01/2003. Input file: "../data/example014". Output file: stdout. MAF: Done. (*A4,*(((*A5,*A1)I1,A2)I2,A3)I3)I4;(*A1,*((*A5,*A4)J1,A2,A3)J2)J3; estela@debian:~/mprs> Mesmo exemplo usando-se PRINTTREE: estela@debian:~/mprs> maf -f ../data/example014 -r -2 | printtree MAF by E. M. Rodrigues - 01/2003. Input file: "../data/example014". Output file: stdout. MAF: Done. PRINTTREE by E. M. Rodrigues - 01/2003. Input file: stdin. Output file: stdout. +--*A4 +--+I4 | +--*A5 | +--+I1 | | +--*A1 | +--+I2 | | +--+A2 +--*I3 +--+A3 +--*A1 +--+J3 | +--*A5 | +--+J1 | | +--*A4 | | | +--+A2 +--*J2 +--+A3 PRINTTREE: Done. estela@debian:~/biocomput/programas/mprs-estavel/mprs> Exemplos de uso - Geração e teste de instâncias ----------------------------------------------- Geração de uma instância com 50000 rótulos usando RANDOM e aplicação de A_2 a esta instância (o tempo de execução deste exemplo em uma máquina Pentium III 866 MHz 256 Mb foi de sete minutos): estela@debian:~/mprs> random -n 50000 | maf -n RANDOM by E. M. Rodrigues - 01/2003. Output file: stdout. MAF by E. M. Rodrigues - 01/2003. Input file: stdin. Output file: stdout. RANDOM: Done. 49992 MAF: Done. estela@debian:~/mprs> Geração de uma instância com 50000 rótulos usando SCRAMBLE com 9 transferências de subárvore (valor otimo <= 10) e aplicação de A_2 a esta instância (o tempo de execução deste exemplo na mesma máquina usada no exemplo anterior foi de quatro minutos e meio): estela@debian:~/mprs> scramble -n 50000 -t 9 -r | maf -n SCRAMBLE by E. M. Rodrigues - 01/2003. Output file: stdout. MAF by E. M. Rodrigues - 01/2003. Input file: stdin. Output file: stdout. SCRAMBLE: Done. 15 MAF: Done. estela@debian:~/mprs> Exemplo de geração das instâncias do tipo usado para os testes em [1], Capítulo 5. O arquivo prog011-000 é gerado aleatoriamente, e contém duas árvores iguais. Cada um dos quatro arquivos seguintes é gerado aplicando-se transferências sobre o arquivo anterior na série, sucessivamente. estela@debian:~/mprs> scramble -n 1000 -t 0 -r >prog011-000 SCRAMBLE by E. M. Rodrigues - 01/2003. Output file: stdout. SCRAMBLE: Done. estela@debian:~/mprs> scramble -f prog011-000 -t 4 >prog011-005 SCRAMBLE by E. M. Rodrigues - 01/2003. Output file: stdout. Input file: "prog011-000". SCRAMBLE: Done. estela@debian:~/mprs> scramble -f prog011-005 -t 5 >prog011-010 SCRAMBLE by E. M. Rodrigues - 01/2003. Output file: stdout. Input file: "prog011-005". SCRAMBLE: Done. estela@debian:~/mprs> scramble -f prog011-010 -t 10 >prog011-020 SCRAMBLE by E. M. Rodrigues - 01/2003. Output file: stdout. Input file: "prog011-010". SCRAMBLE: Done. estela@debian:~/mprs> scramble -f prog011-020 -t 30 >prog011-050 SCRAMBLE by E. M. Rodrigues - 01/2003. Output file: stdout. Input file: "prog011-020". SCRAMBLE: Done. estela@debian:~/mprs> ls prog* -al -rw-r--r-- 1 estela estela 13782 Jan 16 14:17 prog011-000 -rw-r--r-- 1 estela estela 13782 Jan 16 14:17 prog011-005 -rw-r--r-- 1 estela estela 13782 Jan 16 14:18 prog011-010 -rw-r--r-- 1 estela estela 13782 Jan 16 14:18 prog011-020 -rw-r--r-- 1 estela estela 13782 Jan 16 14:19 prog011-050 estela@debian:~/mprs> Testes com as instâncias geradas acima, usando-se o algoritmo A_2 (os valores respectivos de l_C para esses arquivos são 1, 5, 10, 20 e 47): estela@debian:~/mprs> maf -f prog011-000 -n MAF by E. M. Rodrigues - 01/2003. Input file: "prog011-000". Output file: stdout. 1 MAF: Done. estela@debian:~/mprs> maf -f prog011-005 -n MAF by E. M. Rodrigues - 01/2003. Input file: "prog011-005". Output file: stdout. 8 MAF: Done. estela@debian:~/mprs> maf -f prog011-010 -n MAF by E. M. Rodrigues - 01/2003. Input file: "prog011-010". Output file: stdout. 15 MAF: Done. estela@debian:~/mprs> maf -f prog011-020 -n MAF by E. M. Rodrigues - 01/2003. Input file: "prog011-020". Output file: stdout. 27 MAF: Done. estela@debian:~/mprs> maf -f prog011-050 -n MAF by E. M. Rodrigues - 01/2003. Input file: "prog011-050". Output file: stdout. 74 MAF: Done. estela@debian:~/mprs> Cálculo de l_C para cada um desses cinco arquivos: estela@debian:~/mprs> maf -f prog011-000 -n -5 MAF by E. M. Rodrigues - 01/2003. Input file: "prog011-000". Output file: stdout. 1 MAF: Done. estela@debian:~/mprs> maf -f prog011-005 -n -5 MAF by E. M. Rodrigues - 01/2003. Input file: "prog011-005". Output file: stdout. 13 MAF: Done. estela@debian:~/mprs> maf -f prog011-010 -n -5 MAF by E. M. Rodrigues - 01/2003. Input file: "prog011-010". Output file: stdout. 28 MAF: Done. estela@debian:~/mprs> maf -f prog011-020 -n -5 MAF by E. M. Rodrigues - 01/2003. Input file: "prog011-020". Output file: stdout. 58 MAF: Done. estela@debian:~/mprs> maf -f prog011-050 -n -5 MAF by E. M. Rodrigues - 01/2003. Input file: "prog011-050". Output file: stdout. 139 MAF: Done. estela@debian:~/mprs> De acordo com [1], capítulo 5, os valores de l_C são respectivamente 1, 5, 10, 20 e 47. ================================================================= Bibliografia ------------ [1] E. M. Rodrigues. Algoritmos para Comparação de Árvores Filogenéticas e o Problema dos Pontos de Recombinação. Tese de doutoramento. Instituto de Matemática e Estatística da Universidade de São Paulo, 2003. [2] E. M. Rodrigues, M.-F. Sagot e Y. Wakabayashi. The maximum agreement forest problem: approximation algorithms and computational experiments. Theoretical Computer Science 374 (2007), 91-110.