Complexidade de Alinhamento de Seqüências Biológicas
DOI:
https://doi.org/10.5540/tema.2007.08.03.0319Resumo
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
Como Citar
Edição
Seção
Licença
Política para Periódicos de Acesso Livre
Autores que publicam nesta revista concordam com os seguintes termos:
- Autores mantém os direitos autorais e concedem à revista o direito de primeira publicação, com o trabalho simultaneamente licenciado sob a Licença Creative Commons Attribution que permite o compartilhamento do trabalho com reconhecimento da autoria e publicação inicial nesta revista.
- Autores têm autorização para assumir contratos adicionais separadamente, para distribuição não-exclusiva da versão do trabalho publicada nesta revista (ex.: publicar em repositório institucional ou como capítulo de livro), com reconhecimento de autoria e publicação inicial nesta revista.
- Autores têm permissão e são estimulados a publicar e distribuir seu trabalho online (ex.: em repositórios institucionais ou na sua página pessoal) a qualquer ponto antes ou durante o processo editorial, já que isso pode gerar alterações produtivas, bem como aumentar o impacto e a citação do trabalho publicado (Veja O Efeito do Acesso Livre).
- Esta é uma revista de acesso aberto, o que significa que todo o conteúdo é livremente disponível gratuitamente para o usuário ou sua instituição. Os usuários estão autorizados a ler, baixar, copiar, distribuir, imprimir, pesquisar ou vincular os textos completos dos artigos, ou usá-los para qualquer outro propósito legal, sem pedir permissão prévia do editor ou do autor. Isso está de acordo com a definição de acesso aberto do BOAI.
Todo o conteúdo do periódico está licenciado sob uma Licença Creative Commons do tipo atribuição BY.