Complexidade de Alinhamento de Seqüências Biológicas

R.T. Brito

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.




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

Article Metrics

Metrics Loading ...

Metrics powered by PLOS ALM

Refbacks

  • There are currently no refbacks.


Trends in Computational and Applied Mathematics

A publication of the Brazilian Society of Applied and Computational Mathematics (SBMAC)

 

Indexed in:

                       

         

 

Desenvolvido por:

Logomarca da Lepidus Tecnologia