Os algoritmos de alinhamento de sequências são essenciais para a análise de sequências biológicas. Esses
algoritmos são utilizados em diversas tarefas na Bioinformática, tais como montagem de genomas, análise filogenética e busca por similaridade. Com relação aos algoritmos
de alinhamentos, analise as assertivas abaixo.
I. O algoritmo de alinhamento global Needleman-Wunsch
consome tempo O(nm), onde n e m são os comprimentos das sequências que serão alinhadas.
II. A matriz de programação dinâmica que o algoritmo
Smith-Waterman calcula tem entradas negativas ao
alinhar duas sequências de nucleotídeos no sistema de
escore que fornece uma penalidade de -5 de abertura
de lacuna.
III. O e-value é o valor de probabilidade de encontrar, ao
acaso, um hit com um escore maior que o escore calculado do alinhamento.
IV. Dependendo do sistema de pontuação utilizado, o
problema de alinhamento múltiplo é NP-hard.
V. O algoritmo de alinhamento semi-global pode ser utilizado para ajudar na montagem de genomas.
Das assertivas acima, apenas: