Subseqüência comum mais longa sem repetições e variantes

• Processo: 07/54282-6
• Modalidade de apoio: Bolsas no Brasil - Iniciação Científica
• Data de Início da vigência: 01 de julho de 2007
• Data de Término da vigência: 31 de dezembro de 2007
• Área de conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
• Pesquisador responsável: Carlos Eduardo Ferreira
• Beneficiário: Christian Tjandraatmadja
• Instituição Sede: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brasil
• Vinculado ao auxílio: 03/09925-5 - Fundamentos da ciência da computação: algoritmos combinatórios e estruturas discretas, AP.PRNX.TEM
• Assunto(s): Otimização combinatória Branch-and-cut Combinatória poliédrica Algoritmos de aproximação Biologia computacional
• Palavra(s)-Chave do Pesquisador: Algoritmos Se Aproximacao | Combonatoria Poliedrica | Metodo Branch And Cut | Otimizacao Combinatoria

Resumo

Nesta IC estudaremos o problema de encontrar uma subseqüência comum mais longa de duas seqüências em que repetições de símbolos não são permitidas. Há resultados recentes na literatura sobre a complexidade computacional do problema que o caracterizam como APX-difícil. Serão estudadas técnicas de algoritmos de aproximação e também de combinatória poliédrica para resolver o problema. Com base nestas técnicas serão implementados e testados algoritmos de aproximação para o problema, e também um algoritmo exato baseado no método branch and cut. Numa segunda etapa estudaremos variantes do problema em que são permitidas reversões de trechos das seqüências em que as subseqüências são buscadas. O problema em questão tem importantes aplicações em Biologia Computacional. (AU)