O problema da subsequência comum máxima sem repetições
Resumo
Estudamos o seguinte problema: dadas duas sequências X e Y sobre um alfabeto finito, encontre uma subsequência comum máxima de X e Y sem símbolos repetidos. Este problema NP-difícil surge no contexto de rearranjo de genomas quando duplicação de genes é considerada. Descrevemos um algoritmo que resolve o problema de forma ótima baseado na técnica branchand-cut. O algoritmo se aproveita de boas heurísticas e de uma técnica simples mas eficaz que elimina variáveis do problema no decorrer do algoritmo. Finalmente, descrevemos um algoritmo baseado em programação dinâmica que consome tempo e espaço linear quando o tamanho do alfabeto é constante.
Palavras-chave:
Subsequência comum máxima sem repetições, subsequência comum máxima, programação inteira, branch-and-cut, heurísticas
Referências
Adi, S., Braga, M., Fernandes, C., Ferreira, C., Martinez, F., Sagot, M.-F., Stefanes, M., Tjandraatmadja, C., and Wakabayashi, Y. (2010). Repetition-free longest common subsequence. Discrete Applied Mathematics, 158(12):1315–1324. Traces from LAGOS’07 IV Latin American Algorithms, Graphs, and Optimization Symposium Puerto Varas - 2007.
Fernandes, C., Ferreira, C., Tjandraatmadja, C., and Wakabayashi, Y. (2008). A polyhedral investigation of the LCS problem and a repetition-free variant. In Proc. of the 8th Latin American Symposium on Theoretical Informatics (LATIN’08), volume 4957 of Lecture Notes in Computer Science, pages 329–338. Springer.
Ferreira, C. and Tjandraatmadja, C. (2010). A branch-and-cut approach to the repetitionfree longest common subsequence problem. Electronic Notes in Discrete Mathematics, 36:527–534. ISCO 2010 - International Symposium on Combinatorial Optimization.
Hunt, J. and Szymanski, T. (1977). A fast algorithm for computing longest common subsequences. Communications of the ACM, 20(5):350–353.
Sankoff, D. and Kruskal, J. (1983). Time Warps, String Edits, and Macromolecules: The Theory and Practice of Sequence Comparison. Addison-Wesley.
Tjandraatmadja, C. (2010). O problema da subsequência comum máxima. Dissertação de mestrado.
Fernandes, C., Ferreira, C., Tjandraatmadja, C., and Wakabayashi, Y. (2008). A polyhedral investigation of the LCS problem and a repetition-free variant. In Proc. of the 8th Latin American Symposium on Theoretical Informatics (LATIN’08), volume 4957 of Lecture Notes in Computer Science, pages 329–338. Springer.
Ferreira, C. and Tjandraatmadja, C. (2010). A branch-and-cut approach to the repetitionfree longest common subsequence problem. Electronic Notes in Discrete Mathematics, 36:527–534. ISCO 2010 - International Symposium on Combinatorial Optimization.
Hunt, J. and Szymanski, T. (1977). A fast algorithm for computing longest common subsequences. Communications of the ACM, 20(5):350–353.
Sankoff, D. and Kruskal, J. (1983). Time Warps, String Edits, and Macromolecules: The Theory and Practice of Sequence Comparison. Addison-Wesley.
Tjandraatmadja, C. (2010). O problema da subsequência comum máxima. Dissertação de mestrado.
Publicado
19/07/2011
Como Citar
FERREIRA, Carlos E.; TJANDRAATMADJA, Christian.
O problema da subsequência comum máxima sem repetições. In: CONCURSO DE TESES E DISSERTAÇÕES (CTD), 24. , 2011, Natal/RN.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2011
.
p. 28-33.
ISSN 2763-8820.
