Proposta para o Trabalho de Formatura Supervisionado
Algoritmos de Aproximação e Problemas com Seqüências
Orientadora: Cristina Gomes Fernandes
Aluno: Rafael Crivellari Saliba Schouery

Sumário

1  Tema
2  Resumo da monografia a ser desenvolvida
3  Objetivos
4  Atividades já realizadas
5  Cronograma
6  Estrutura esperada da monografia

1  Tema

Problemas envolvendo seqüências aparecem nas mais diversas áreas, como por exemplo em compressão de dados e em biologia computacional [9,14].
Alguns destes problemas estão bem resolvidos, no sentido de que existem algoritmos eficientes para solucioná-los, enquanto que outros são considerados computacionalmente difíceis. Quando os problemas em questão são problemas de otimização combinatória difíceis, é comum encontrar na literatura uma variedade de algoritmos de aproximação para eles, que surgem como uma possível forma de atacá-los.
Algoritmos de aproximação são algoritmos eficientes para um problema de otimização combinatória que produzem não necessariamente uma solução ótima para o problema, mas sim uma solução viável com uma certa garantia de qualidade [6,10,19]. Muitos destes algoritmos decorrem de ferramentas bem conhecidas de projeto de algoritmos, bem como de propriedades muitas vezes não-triviais do problema em questão.
O estudo de algoritmos de aproximação para problemas envolvendo seqüências inclui o estudo de uma série de conceitos, ferramentas, e problemas algorítmicos básicos, que são de interesse geral na área de projeto de algoritmos combinatórios.
Um dos problemas bem conhecidos envolvendo seqüências é o problema da superseqüência comum mínima (shortest common supersequence), denotado por scs: dadas seqüências s1,...,sn (finits) de símbolos sobre um alfabeto, encontrar uma seqüência de comprimento mínimo que seja superseqüência de cada si, para i=1,...,n.
Sabe-se que o scs é NP-difícil [8], e mesmo MAX SNP-difícil [4,18], que significa que mesmo a existência de um PTAS (esquema polinomial de aproximação) para ele é pouco provável (implicaria que P = NP).
Na literatura, há diversos algoritmos de aproximação para o scs [2,3,4,5,7,12,13,15,16,17] e há também uma conjectura clássica envolvendo um destes algoritmos, conhecido como algoritmo guloso (greedy) para o scs.
Este trabalho de formatura supervisionado visa o estudo de algoritmos de aproximação e resultados de complexidade para o scs. Especial ênfase será dada aos resultados referentes à conjectura sobre o algoritmo guloso para o scs [1,4,11,20].
O problema específico escolhido neste projeto é importante e rico, como demonstra o levantamento bibliográfico inicial. O problema é discutido em diversos livros [9,14,19] e em uma série de artigos, alguns clássicos [4,13,17] e vários outros, alguns deles mais recentes [1,2,3,5,7,11,12,15,16,20].

2  Resumo da monografia a ser desenvolvida

Como dito na seção anterior, o objetivo deste projeto é estudar diversos algoritmos de aproximação e outros resultados de interesse para o problema da superseqüência comum mínima. Para isto, num primeiro momento introduziremos os conceitos necessários para que o leitor entenda o problema e a soluções possíveis. Mostraremos então o algoritmo mais clássico para este problema, o greedy, descrevendo-o e apresentando algumas idéias e conceitos que são utilizados pelos outros algoritmos. Como sua análise é muito complicada, deixamos a mesma para uma seção futura, até porque a mesma depende de uma comparação com um outro algoritmo.
Mostraremos então que o problema é NP-díficil e portanto um algoritmo eficiente para o mesmo é improvável (implicaria que P = NP). O resultado é válido mesmo com uma séria de restrições, mas não abordaremos todas já que este não é o foco do estudo. Seguiremos então mostrando que o scs é Max SNP-díficil e portanto, a menos que P = NP, não existe um esquema de aproximação polinomial para o mesmo.
Como o greedy depende da análise de outros algoritmos, mostraremos a análise de três destes, explicando em cada seção o funcionamento de cada um e qual é a razão de aproximação de cada um. Concluindo com a análise do greedy, teremos completado a parte "clássica" do problema, já que estes são os algoritmos mais conhecidos e citados. Por exemplo, estes são os apresentados por Vazirani [19] em sua compilação sobre algoritmos de aproximação.
Abordaremos então resultados mais novos para o problema, como novos algoritmos e novas análises que mostrem que os algoritmos já descritos são na verdade ainda melhores do que foi originalmente provado. Pretendemos também abordar novos resultados, como análise assintótica e utilizações práticas do problema, que aparece tanto em seqüenciamento de DNA da Biologia Computacional quanto em compressão de dados.

3  Objetivos

Muitos dos algoritmos para o scs usam o natural conceito de sobreposição máxima entre duas seqüências: dadas duas seqüências u e v, a sobreposição máxima entre u e v é o sufixo de comprimento máximo de u que é também prefixo de v. A composição entre u e v é a seqüência obtida de concatenarmos u e v, removendo a sobreposição máxima entre elas. Por exemplo, a sobreposição máxima entre as seqüências u = abbbaab e v = baababa é baab, enquanto que sua composição é abbbaababa, que é justamente a superseqüência comum mínima de u e v.
No capítulo 2 do livro de Vazirani [19] aparece descrito um simples e antigo algoritmo que intriga até hoje qualquer um que já tenha trabalhado com o scs. Trata-se do chamado algoritmo guloso para o scs, que, dado um conjunto S de seqüências, repetidamente substitui um par de seqüências em S que tenha sobreposição máxima pela sua composição, até que S tenha apenas uma seqüência, que é então devolvida. A conjectura mencionada diz que esse algoritmo tem razão de aproximação 2.
O objetivo dessa iniciação científica é estudar vários dos algoritmos de aproximação, alguns resultados de complexidade computacional sobre o scs, e alguns dos diversos resultados relacionados à conjectura sobre o algoritmo guloso para o scs.

4  Atividades já realizadas

Estou fazendo esta iniciação cientifica desde setembro de 2007 e até agora várias atividades foram realizadas. Numa primeira fase, estudei os capítulos iniciais do livro de Carvalho et al. [6] sobre algoritmos de aproximação. Após isso, iniciei o estudo dos capítulos 2 e 7 do livro de Vazirani [19], que tratam, entre outras coisas, de alguns algoritmos de aproximação clássicos para o scs.
Nosso objetivo inicial era analisar um algoritmo guloso para o scs mas como a sua análise se demonstrou muito complicada, ela foi postergada até recentemente e portanto ainda não foi escrita. Mas para compensar esta mudança, estudei dois resultados de complexidade para o scs que já estão escritos no texto.
Foi possível produzir durante este período um texto longo sobre o assunto (com quase trinta páginas) abordando os algoritmos mais conhecidos para o problema. Inicialmente estudei um algoritmo baseado na idéia de cobertura por circuitos de custo mínimo em um grafo, que é naturalmente associado a encontrar um emparelhamento perfeito de custo mínimo. Isto me trouxe novos conhecimentos na área de grafos e otimização combinatória.
Pude então estudar dois outros algoritmos que utilizam-se de idéias simples, porém poderosas, para resolver o problema. O MGREEDY utiliza também uma idéia gulosa, relaxando a idéia do algoritmo guloso original. O outro, o TGREEDY, utiliza os algoritmos já explicados para encontrar uma razão de aproximação melhor para o problema.
Essa parte foi especialmente importante pela análise do MGREEDY que utiliza um esquema de prova já bem conhecido para mostrar que um algoritmo guloso funciona, mas que eu nunca tinha estudado com todos os detalhes antes. O resultado atingido é que o MGREEDY é equivalente ao algoritmo mencionado no parágrafo anterior que encontra uma cobertura por circuitos de custo mínimo. É interessante notar que um algoritmo trabalha em um grafo com conceitos sofisticados desta área enquanto o outro trabalha com um conceito bem intuitivo que poderia ser facilmente implementado mas, mesmo assim, ambos são equivalentes. Todos estes algoritmos foram estudados em várias fontes diferentes [9,14,19,4] para que fosse possível comparar as notações utilizadas e como algumas definições foram feitas. Discutindo com a minha orientadora chegamos a uma notação que acredito ser fácil de entender e concisa.
Realizei então um estudo sobre a complexidade do problema. Inicialmente estudei o texto de Gallant et al. [8] onde é provado que o problema é NP-difícil. Esta foi a primeira vez que estudei uma redução polinomial para mostrar que um problema é computacionalmente difícil apesar do assunto já ter sido apresentado em uma aula de análise de algoritmos. Por causa disso, demorei um bom tempo para entender completamente a prova e conseguir reescrever a mesma. O mesmo ocorreu com o outro resultado de complexidade que mostra que o scs é MAX SNP-difícil [4]. Como nunca tinha estudado L-reduções antes tive muitas dificuldades em entender todo o processo. O texto original da prova é vago em muitos aspectos, principalmente pela semelhança com a redução de Gallant et al. [8] mencionada acima. Isso dificultou muito o processo de entender e reescrever a prova, mas isso foi possível graças a ajuda da professora Cristina que me ajudou a provar o resultado de forma independente. Apesar de nos basearmos na prova do artigo original, uma parte considerável do mesmo foi ignorada para escrever esta versão.
Por último, estudei a análise do GREEDY que prova que o mesmo é uma 4-aproximação polinomial para o scs. Esta prova é bem complicada, mas recentemente consegui entendê-la. Provavelmente algumas dificuldades surgirão ao tentar reescrever a prova, mas acho que a parte mais difícil já foi entendida. O grande problema desta análise é que ela é única não mencionada em nenhuma das outras fontes que pesquisamos e portanto não pudemos ver a explicação de um segundo autor.
Em maio participei de uma apresentação deste projeto na forma de um cartaz no Núcleo de Modelagem Estocástica e Complexidade (NUMEC) do Instituto de Matemática e Estatística da USP para professores e alunos de pós-graduação do instituto.

5  Cronograma

O cronograma geral para o projeto está descrito abaixo, mas talvez haja algumas alterações no mesmo. Como estou cursando a matéria Algoritmos de Aproximação, eu e minha supervisora estamos cogitando a possibilidade de tentar formular o problema através de outros métodos, como por exemplo, através de relaxação de programação linear inteira. Não sabemos ainda se será possível uma formulação do problema de outra forma, mas estamos interessados em realizar esta análise. Como não sabemos ainda se iremos realizar este estudo ou não, apresento o cronograma previsto inicialmente com os itens que pretendemos cumprir ainda que parcialmente.
Pretendemos realizar agora, após a escrita da análise do algoritmo guloso, a análise de alguns dos algoritmos de aproximação mais recentes, apresentados apenas em artigos [2,3,5,7,12,15,16], e algumas das análises aprimoradas do algoritmo guloso [1,11,20].
O cronograma estipulado para os próximos meses é o seguinte.
Atividade/Mês julho agosto setembro outubro novembro
Escrita da análise do algoritmo guloso. +     
Estudo das análises mais recentes do algoritmo guloso para o scs. + +    
Estudo de alguns algoritmos mais recentes para o scs.   + +  
Continuação da escrita do texto.  + + + +
Preparação do poster.     +
Preparação para a apresentação do trabalho.     +
Preparação da versão de entrega da monografia.     +

6  Estrutura esperada da monografia

A estrutura esperada da monografia é basicamente a sugerida pelo roteiro. A parte técnica será constituída de uma introdução explicando os conceitos necessários para entender o problema e os resultados apresentados. Para isso será necessária uma formalização de conceitos como algoritmos de aproximação, resultados de complexidade computacional e inaproximabilidade. Alguns destes conceitos poderão ser apresentados mais adiante no texto, quando for mais conveniente para o leitor. Abordarei então os conceitos estudados, mostrando uma variedade de algoritmos para o problema e vários resultados. Concluiremos com outros resultados sobre o scs que serão apenas discutidos pois não são do escopo deste trabalho. Um exemplo disso são os diversos resultados sobre a qualidade assintótica dos algoritmos. A segunda parte (subjetiva) conterá os itens pedidos na proposta, relatando a minha experiência no curso.

References

[1]
C. Armen and C. Stein. Improved length bounds for the shortest superstring problem. In Proceedings of the 4th International Workshop on Algorithms and Data Structures, volume 955 of Lecture Notes in Computer Science, pages 494-505. Springer, 1995.
[2]
C. Armen and C. Stein. Short superstrings and the structure of overlapping strings. Journal of Computational Biology, (2):307-333, 1995.
[3]
C. Armen and C. Stein. A 2[2/3] superstring approximation algorithm. Discrete Applied Mathematics, 88(1-3):29-57, 1998.
[4]
A. Blum, T. Jiang, M. Li, J. Tromp, and M. Yannakakis. Linear approximation of shortest superstrings. Journal of the Association for Computing Machinery, 41(4):630-647, 1994.
[5]
D. Bongartz. On the approximation ratio of the Group-Merge algorithm for the shortest common superstring problem. Computing and Informatics, 20(4):325-357, 2001.
[6]
M.H. Carvalho, M.R. Cerioli, R. Dahab, P. Feofiloff, C.G. Fernandes, C.E.  Ferreira, F.K. Miyazawa, J.C. de Pina, J. Soares, and Y. Wakabayashi. Uma Introdução Sucinta a Algoritmos de Aproximação. Publicações Matemáticas do IMPA, 2001.
[7]
A. Czumaj, L. G asieniec, M. Piotrów, and W. Rytter. Sequential and parallel approximation of shortest superstrings. Journal of Algorithms, 23(1):74-100, 1997.
[8]
J. Gallant, D. Maier, and J.A. Storer. On finding minimal length superstrings. Journal of Computer and System Sciences, 20(1):50-58, 1980.
[9]
D. Gusfield. Algorithms on strings, trees, and sequences. Cambridge University Press, Cambridge, 1997. Computer Science and Computational Biology.
[10]
D.S. Hochbaum, editor. Approximation Algorithms for NP-Hard Problems. PWS Publishing, 1997.
[11]
H. Kaplan and N. Shafrir. The greedy algorithm for shortest superstrings. Information Processing Letters, 93(1):13-17, 2005.
[12]
R. Kosaraju, J. Park, and C. Stein. Long tours and short superstrings. In Proceedings of the 35th Annual Symposium on Foundations of Computer Science (FOCS), pages 125-134, 1994.
[13]
M. Li. Towards a DNA sequencing theory. In Proceedings of the 31th Annual Symposium on Foundations of Computer Science (FOCS), pages 125-134. IEEE Comput. Soc. Press, Los Alamitos, CA, 1990.
[14]
J.C. Setubal and J. Meidanis. Introduction to Computational Molecular Biology. PWS Publishing Company, Boston, 1997.
[15]
Z. Sweedyk. A 21/2-approximation algorithm for shortest superstring. SIAM Journal on Computing, 29(3):954-986 (electronic), 2000.
[16]
S.H. Teng and F.F. Yao. Approximating shortest superstrings. SIAM Journal on Computing, 26(2):410-417, 1997.
[17]
J.S. Turner. Approximation algorithms for the shortest common superstring problem. Information and Computation, 83(1):1-20, 1989.
[18]
V. Vassilevska. Explicit inapproximability bounds for the shortest superstring problem. In Mathematical Foundations of Computer Science, volume 3618 of Lecture Notes in Computer Science, pages 793-800. Springer, Berlin, 2005.
[19]
V.V. Vazirani. Approximation Algorithms. Springer, 2001.
[20]
M. Weinard and G. Schnitger. On the greedy superstring conjecture. SIAM Journal on Discrete Mathematics, 20(2):502-522, 2006.