Questão de Algoritmos e Estrutura de Dados — Algoritmos — FIOCRUZ 2024
Algoritmos e Estrutura de Dados›Algoritmos
Código
qg145072
Banca
FIOCRUZ
Órgão
FIOCRUZ
Ano
2024
Nível
Superior
Cargo
Tecnologista em Saúde Pública - Bioinformática
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:
AI, IV e V são verdadeiras.
BII é verdadeira.
CIII é verdadeira.
DIV é verdadeira.
EIII e IV são verdadeiras.
Revelar gabarito e comentário▾
GabaritoA — I, IV e V são verdadeiras.
Comentário gerado por IA. É um apoio ao estudo, ancorado em fontes, mas pode conter imprecisões — confira sempre na fonte oficial (lei, súmula, edital e gabarito da banca). Encontrou um erro? Use “Reportar”.
Algoritmos de Alinhamento de Sequências
Gabarito: letra A — as assertivas I, IV e V são verdadeiras, conforme a literatura clássica de bioinformática (Needleman-Wunsch, complexidade NP-difícil do alinhamento múltiplo, uso do semi-global em montagem). A assertiva II erra ao dizer que a matriz do Smith-Waterman tem entradas negativas (na verdade, valores negativos são zerados). A assertiva III confunde E-value com p-value: o E-value é o número esperado de hits ao acaso, não uma probabilidade.
Assertiva
Conteúdo
Verdadeiro/Falso
Justificativa
I
O algoritmo Needleman-Wunsch consome tempo O(nm).
✅ Verdadeiro
Complexidade clássica de programação dinâmica para alinhamento global.
II
A matriz do Smith-Waterman tem entradas negativas com penalidade de -5.
❌ Falso
No Smith-Waterman, valores negativos são zerados; a matriz nunca fica negativa.
III
E-value é a probabilidade de encontrar um hit ao acaso com escore maior.
❌ Falso
E-value é o número esperado de hits; a probabilidade é o p-value.
IV
Alinhamento múltiplo é NP-difícil dependendo do sistema de pontuação.
✅ Verdadeiro
Problema clássico de otimização combinatória NP-difícil.
V
Alinhamento semi-global é usado em montagem de genomas para overlaps.
✅ Verdadeiro
Técnica comum para identificar sobreposições entre reads.
Alinhamento de sequências: Global (Needleman-Wunsch) (O(nm), Programação dinâmica); Local (Smith-Waterman) (Valores negativos zerados, Alinhamento local); Semi-global (Montagem de genomas, Overlaps entre reads); Múltiplo (NP-difícil, Soma de pares); Estatística (E-value: número esperado de hits, Confunde com p-value (probabilidade))
Item I — ✅ Correto
O algoritmo de Needleman-Wunsch para alinhamento global utiliza programação dinâmica com complexidade de tempo (O(nm)), sendo (n) e (m) os comprimentos das sequências. É um resultado fundamental e amplamente conhecido.
Item II — ❌ Incorreto
No Smith-Waterman (alinhamento local), a matriz de programação dinâmica nunca contém entradas negativas: valores negativos calculados são substituídos por zero (ou por um valor mínimo permitido, geralmente 0). A presença de penalidades de abertura de lacuna (ex.: -5) não altera essa regra; a matriz é construída de forma que a célula nunca fique negativa. Portanto, a afirmação é falsa.
Item III — ❌ Incorreto
O E-value (expectation value) é o número esperado de hits com escore maior ou igual ao observado em uma busca em base de dados, não uma probabilidade. A definição correta de probabilidade de encontrar um hit ao acaso com escore superior é o p-value. A assertiva inverte os conceitos.
Item IV — ✅ Correto
Dependendo do sistema de pontuação (por exemplo, soma de pares com penalidades de lacuna), o problema de alinhamento múltiplo de sequências é NP-difícil. É um problema clássico de otimização combinatória.
Item V — ✅ Correto
O alinhamento semi-global (ou glocal) é amplamente utilizado em montagem de genomas para identificar sobreposições (overlaps) entre reads, alinhando apenas as extremidades sem penalizar extremidades não alinhadas.
NÃO CAIA NESSA!
A banca explora a confusão entre E-value e p-value (assertiva III) e o mito de que a matriz do Smith-Waterman aceita valores negativos (assertiva II). Grave: no Smith-Waterman, valores negativos viram zero; E-value é expectativa, não probabilidade.
Conclusão: Corretas apenas I, IV e V → gabarito letra A.