Complexidade de Alinhamento de Seqüências Biológicas

Authors

  • R.T. Brito

DOI:

https://doi.org/10.5540/tema.2007.08.03.0319

Abstract

Neste trabalho, apresentamos uma demonstração simples, completa e acessível (inclusive a alunos de graduação de Ciência da Computação) do fato de que o problema de Alinhamento de Seqüências Biológicas é NP-difícil, baseada na demonstração de Wang e Jiang [10], um resultado freqüentemente citado, mas coma prova normalmente omitida.

References

[1] P. Bonizzoni, G.D. Vedova, The complexity of multiple sequence alignment with SP-score that is a metric, Theoretical Computer Science, 259 (2001), 63–79.

R.T. Brito, “Alinhamento de Seq¨uˆencias Biol´ogicas”, Dissertação de Mestrado,

IME, USP, S˜ao Paulo, SP, 2003.

T.H. Cormen, C.E. Leiserson, R.L. Rivest, “Introduction to Algorithms”, The MIT Press, 1990.

G. Fuellen, “Multiple Alignment”, Complexity International 4, url: http://www.csu.edu.au/ci/vol04/mulali/mulali.html, 1997.

M.R. Garey, D.S. Johnson, “Computers and Intractability: A Guide to the Theory of NP-Completeness”, W.H. Freeman and Company, 1979.

S.K. Gupta, J.D. Kececioglu, A.A. Sch¨affer, Improving the practical space and time efficiency of the shortest-paths approach to sum-of-pairs multiple sequence alignment, Journal of Computational Biology, 2, No. 3 (1995), 459–472.

D. Gusfield, “Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology”, Cambrige Press, 1997.

W. Just, Computational complexity of multiple sequence alignment with SPscore, Journal of Computational Biology, 8, No. 6 (2001), 615–623.

W. Just, Comunicação Pessoal, Maio, 2002.

L. Wang, T. Jiang, On the complexity of multiple sequence alignment, Journal of Computational Biology, 1 (1994), 337–348.

Published

2007-06-01

How to Cite

Brito, R. (2007). Complexidade de Alinhamento de Seqüências Biológicas. Trends in Computational and Applied Mathematics, 8(3), 319–328. https://doi.org/10.5540/tema.2007.08.03.0319

Issue

Section

Original Article