008 - reversals

MO640 – Questão para a prova oral

Número:

Enunciado:

De acordo com o artigo de HANNENHALLI & PEVZNER sobre o algoritmo polinomial para ordenar permutações sinaladas por reversões, quais dos seguintes passos NÃO é um passo necessário para gerar um (g, b)-split de um grafo de breakpoints G(PI) que contém a aresta preta b=(vb, wb) e a aresta cinza g=(wg, vg)?

A. Adicionar duas novas arestas pretas (vb, v) e (w, wb);

B. Remover as arestas g e b;

C. Adicionar duas novas arestas cinzas (wg, w) e (v, vg);

D. Adicionar os novos vértices v e w;

E. NDA.

Autor: Michel S. Fornaciali

007 - block interchange

Qual é a alternativa INCORRETA sobre troca de blocos?



A) Uma troca de blocos é uma operação de rearranjo de genomas na qual quaisquer blocos do genoma podem trocar de posição.

B) É impossível aumentar o número de ciclos alternados de uma permutação P por mais de 2 com uma única troca de blocos.

C) Sempre é possível encontrar uma troca de blocos em um genoma que remove ao menos dois breakpoints de uma dada permutação P, a menos que P seja a permutação identidade.

D) É conhecido um algoritmo polinomial para calcular a quantidade mínima de trocas de bloco para ordenar um genoma, e ele possui complexidade O(n³).

E) NDA.


Autor: Michel S. Fornaciali

006 – Haplótipos

Sobre inferência de haplótipos, qual é a alternativa FALSA?

A. Haplótipo é a sequência de DNA que foi herdada de um dos pais.
B. O problema da Parcimônia Pura visa encontrar uma solução para a inferência de haplótipos que minimize o número total de haplótipos usados.
C. Uma Filogenia Perfeita sobre um conjunto M de sequências binárias e uma sequência inicial V é uma árvore que mostra a evolução dos haplótipos, com V na raiz.
D. O problema da Resolução Máxima, que é NP-difícil, visa descobrir qual é a execução do algoritmo de Clarck que maximiza o número de vetores ambíguos que podem ser resolvidos.
E. NDA.

Autor: Michel S. Fornaciali

005 - Tendências

De acordo com os artigos estudados sobre tendências na Biologia Computacional, temos as seguintes afirmações:

I- Eddy nos diz que pessoas com habilidades em múltiplas áreas podem ver o mundo sob uma nova óptica, por isto são muito mais adequadas em pesquisas científicas do que grupos de pessoas especializadas independentemente em áreas distintas.

II- Segundo Pevzner, não basta que um biólogo saiba apenas utilizar ferramentas computadorizadas para bioinformática sem conhecer os conceitos biológicos e as idéias computacionais por trás delas.

III- Meidanis nos mostra uma série de desafios encontrados pelos biólogos e pelos cientistas da computação em relação à bioinformática. Dentre eles, o de menor importância é a inovação dos cursos já existentes de bioinformática, uma vez que não há mais nada a ser aprimorado.

Quais delas são verdadeiras?

A. I e II.

B. II e III.

C. Todas estão corretas.

D. Todas estão incorretas.

E. NDA.

Autor: Michel S. Fornaciali

004 – database search / similarity and distance

De acordo com o capítulo 3 do livro “Introduction to Computational Molecular Biology” de Setubal & Meidanis, considere as seguintes afirmações:

I-                   Definimos [similaridade] como o maior “score” em qualquer alinhamento. A similaridade é dita [aditiva] porque se cortarmos o alinhamento em blocos consecutivos, o “score” total é a soma do “score” de cada bloco.

II-                Definimos [distância] como o menor custo para transformar uma string s em t. Além disto, a [inequação triangular] afirma que a distância entre as strings X e Y é estritamente menor que soma das distâncias entre X e Z, e entre Z e Y.

III-             Existe um conjunto finito de operações que podem ser realizadas para alinharmos duas strings. Tal conjunto é formado pelas seguintes operações: substituição de um caracter A por um caracter B, inserção e remoção de um caracter arbitrário.

IV-             A definição do termo [database] empregado no texto, refere-se a um banco de dados que armazena de forma eficiente muitas sequências de DNA e que permite acesso rápido do seu conteúdo, razão pela qual o algoritmo BLAST não é oneroso em relação ao tempo.

Quais são verdadeiras?

A)    Todas.

B)    I e III.

C)    I, III e IV.

D)    II.

E)     NDA.

Autor: Michel S. Fornaciali

003 - Árvores PQ e PQR

Sobre árvores PQ e PQR, é INCORRETO afirmar que:

1. Dada uma árvore T, do tipo PQR, podemos construir uma árvore T’, equivalente a T, também do tipo PQR, por meio de zero ou mais das seguintes operações: permutações arbitrárias dos filhos de um nó P, reversão dos filhos de um nó Q e permutações arbitrárias dos filhos de um nó R.
2. O algoritmo apresentado por Telles e Meidanis para a construção de uma árvore PQR é dito incremental porque a árvore é construída aos poucos de acordo com o acréscimo sucessivo de restrições (uma por iteração).
3. Numa árvore PQ ou PQR, definimos a “árvore pertinente” como a menor subárvore que possui todos os nós contidos numa restrição.
4. O algoritmo apresentado por  Booth e Lueker para a construção de uma árvore PQ é quadrático. O algoritmo apresentado por Telles e Meidanis para a construção de uma árvore PQR também é quadrático, e provou-se que é impossível encontrar um algoritmo mais eficiente para este problema.
5. NDA.

Autor: Michel S. Fornaciali

002 - Árvores PQ e PQR

Considere as seguintes afirmações sobre árvores PQ e PQR:

 I – Podemos dizer que árvores PQ são especializações de árvores PQR e que estas são generalizações de árvores PQ.

II – A interseção do conjunto C-Completude com o conjunto C-ortogonal representa o conjunto de nós da árvore PQR.

III – Dentre as vantagens do uso do algoritmo PQR ao invés do PQ podemos destacar que o primeiro é mais simples e intuitivo, além de sempre permitir uma visualização da árvore resultante. Ou seja, caso a árvore PQ exista, ela será gerada. Caso não exista, será possível detectar a restrição que impede sua construção.

IV – Dada uma restrição numa árvore PQ, chamamos de nós CHEIOS as folhas que não estão presentes na restrição e de VAZIOS as folhas que estão na restrição.

É correto afirmar que:

1-      Todas as afirmações são verdadeiras.

2-      Todas as afirmações são falsas.

3-      As alternativas II e IV são falsas.

4-      Apenas a alternativa IV é falsa.

5-      NDA.

Autor: Michel S. Fornaciali