Complexidade de Alinhamento de Seqüências Biológicas

Autores

  • R.T. Brito

DOI:

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

Resumo

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.

Referências

[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.

Downloads

Publicado

2007-06-01

Como Citar

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

Edição

v. 8 n. 3 (2007)

Seção

Artigo Original

Licença

Direitos Autorais

Autores de artigos publicados no periódico Trends in Computational and Applied Mathematics mantêm os direitos autorais de seus trabalhos. O periódico utiliza a Atribuição Creative Commons (CC-BY) nos artigos publicados. Os autores concedem ao periódico o direito de primeira publicação.

Propriedade Intelectual e Termos de uso

O conteúdo dos artigos é de responsabilidade exclusiva dos autores. O periódico utiliza a Atribuição Creative Commons (CC-BY) nos artigos publicados. Esta licença permite que os artigos publicados sejam reutilizados sem permissão para qualquer finalidade, desde que o trabalho original seja corretamente citado.

O periódico encoraja os Autores a autoarquivar seus manuscritos aceitos, publicando-os em blogs pessoais, repositórios institucionais e mídias sociais acadêmicas, bem como postando-os em suas mídias sociais pessoais, desde que seja incluída a citação completa à versão do website da revista.