MAC0499 - Trabalho de Formatura Supervisionado

O problema do Menor Ancestral Comum

Aluno: Daniel Noel Ribeiro

Supervisor: Alair Pereira do Lago

Tipo de trabalho: Iniciação Científica

Apoio: FAPESP (processo: 05/50796-0)

Resumo

Algoritmos sobre textos é uma classe muito ampla de algoritmos com aplicações de grande relevância para diversas áreas como Biologia Molecular Computacional e o desenvolvimento de ferramentas de buscas na Internet. Devido ao volume gigantesco de dados envolvidos, soluções lineares são muito procuradas, pois podem tornar solúvel um problema antes intratável.

Duas das estruturas de dados mais avançadas que permitem algoritmos extremamente eficientes são as Árvores dos Sufixos e as Tabelas que permitem a resolução do problema do Menor Ancestral Comum em tempo constante após um pré-processamento linear.

O projeto se concentra em estudar o problema do Menor Ancestral Comum, algumas de suas soluções algorítmicas, propor também melhorias (tanto no quesito de utilização de memória quanto no de tempo de processamento) a estas soluções, formalizar e escrever estas melhorias, implementá-las e realizar benchmarks. Ademais, deseja-se estudar algumas de suas aplicações, em particular, envolvendo árvores dos sufixos.

Objetivos

O objetivo principal do projeto é estudar o problema do Menor Ancestral Comum e algumas soluções já propostas, bem como propor melhorias a estas soluções que levem a uma solução mais eficiente. Para tanto, serão feitas comparações com estas outras soluções, tanto teoricamente quanto através de benchmarks. Uma implementação também será necessária, para tanto.

Também se pretende estudar, e eventualmente implementar, algumas das aplicações do MAC discutidas anteriormente.

Sendo-se feitas melhorias em relação aos algoritmos apresentados no livro [dLS03], como o mesmo se encontra disponível para alterações cooperativas no projeto da incubadora FAPESP, pretende-se propor alterações ao livro de forma a incluir estas eventuais melhorias. Eventualmente, considerar-se-á a possibilidade de que seja escrito algum relatório técnico e/ou artigo.

Atividades e Cronogramas

As atividades compreendidas pelo projeto são:

leitura e resenha de artigos principais;
generalização dos algoritmos aos casos propostos;
implementação e testes dos algoritmos citados;
experimentação (aplicação do algoritmo a dados reais);
pesquisa na literatura de problemas correlatos;
leitura e resenha de artigos com aplicações;
redação de relatórios semestrais para a fapesp;

Atividades Realizadas:

Implementação e testes dos algoritmos citados: foram escritos em C buscando o máximo de otimização computacional constante possível, devido ao fato dos algoritmos serem geralmente aplicados em ambientes onde perdas de eficiência, mesmo por um fator constante, não são toleradas.
Leitura e resenha de artigos principais: As leituras já foram realizadas, assim como algumas resenhas.
Experimentação (aplicação do algoritmo a dados reais): Em fase de conclusão. Até o momento foram realizados experimentos como dados gerados de forma pseudo-aleatória.

Cronograma das Atividades para o segundo semestre

Seguem os índices das atividades (linhas) relacionadas aos meses (colunas) previstos para suas realizações

A Figura 1 descreve a alocação das atividades durante no período de abril/2005 a fevereiro/2006.

**Figura 1:** Cronograma: segundo semestre de 2005
$\begin{figure}\begin{center} \begin{tabular}{\vert c\vert c\vert c\vert c\vert c... ... \ \hline 7 & & & X & & \ \hline \hline \end{tabular} \end{center}\end{figure}$

Estrutura esperada da monografia

A parte técnica da monografia será semelhantes aos relatórios a serem entregues à FAPESP. Portanto a parte técnica abordará:

Resumo
Introdução
Descrição do Problema
Justificativa
Aplicações do Problema do Menor Ancestral Comum
Descrição das atividades Realizadas
Resultados obtidos e sua análise
Resenha dos artigos principais
Bibliografia

A parte subjetiva será baseada nas minhas experiências ao longo da iniciação científica, e do relacionamento dos assuntos abordados pela graduação com o projeto. Sua estrutura é:

Desafios e frustrações encontrados
Disciplinas cursadas no BCC mais relevantes para a iniciação
Interação com o orientador
Análise da aplicação dos conceitos estudados ao longo da graduação em um contexto prático de aplicações reais
Próximos passos a serem seguidos para aprimoramento de conhecimentos relevantes à área de estudo, caso se dê continuidade ao trabalho realizado durante a pesquisa

Referências Bibliográficas

BFC00: Michael A. Bender and Martin Farach-Colton.
The LCA problem revisited.
In Latin American Theoretical INformatics, pages 88-94, 2000.
BGSV89: O. Berkman, Z. Galil, B. Schieber, and U. Vishkin.
Highly parallelizable problems.
In STOC '89: Proceedings of the twenty-first annual ACM symposium on Theory of computing, pages 309-319. ACM Press, 1989.
CR94: Maxime Crochemore and Wojciech Rytter.
Text algorithms.
The Clarendon Press Oxford University Press, New York, 1994.
With a preface by Zvi Galil.
dLS03: Alair Pereira do Lago and Imre Simon.
Tópicos em Algoritmos sobre Seqüências.
IMPA, Rio de Janeiro, 2003.
ISBN 85-244-0202-4.
Gus97: Dan Gusfield.
Algorithms on strings, trees, and sequences.
Cambridge University Press, Cambridge, 1997.
Computer science and computational biology.
HT84: Dov Harel and Robert Endre Tarjan.
Fast algorithms for finding nearest common ancestors.
SIAM J. Comput., 13(2):338-355, 1984.
Mut02: S. Muthukrishnan.
Efficient algorithms for document retrieval problems.
In SODA '02: Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, pages 657-666. Society for Industrial and Applied Mathematics, 2002.
SV88: Baruch Schieber and Uzi Vishkin.
On finding lowest common ancestors: Simplification and parallelization.
SIAM J. Comput., 17:1253-1262, 1988.