Questão
ID 87065Disciplina: Biologia
Assuntos: Bioinformática, Complexidade de Algoritmos (Big-O, P x NP)
Ano: 2024 Banca: FIOTEC/FIOCRUZ Órgão: Fundação Oswaldo Cruz
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:
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: