022-2011

MO640 - Biologia Computacional

Número: 022-2011

Enunciado: Qual alternativa sobre troca de blocos abaixo é INCORRETA?

A) Uma troca de blocos é uma operação de rearranjo de genomas na qual dois blocos quaisquer do genoma trocam de posição, saindo de sua posição original e ficando um na posição antes ocupada pelo outro.

B) É impossível aumentar o número de ciclos alternados de uma permutação em mais de 2 unidades 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.

Ideia original de: Michel S. Fornaciali

035-2007

MO640 - Questão para a prova oral

Número: 035

Enunciado: Sejam dt, dp e db as distâncias de: transposição, transposição de prefixo e intercâmbio de blocos, respectivamente, definidas nos trabalhos de Bafna e Pevzner (1998), Christie (1996) e Fortuna (2005). Como podemos relacionar estas distâncias?

1. dt ≤ dp ≤ db
2. dp ≤ db ≤ dt
3. dp ≤ dt ≤ db
4. db ≤ dt ≤ dp
5. N.D.A.

Nome: Pettras Leonardo Bueno dos Santos

034-2007

MO640 - Questão para a prova oral
Número: 034
Enunciado: No quinto passo da ordenação por troca de blocos da permutação 3 1 5 4 10 2 8 6 9 7, o menor elemento fora de ordem (x) e o correspondente maior elemento à sua esquerda (y) são:

1. 2 e 3.
2. 3 e 7.
3. 5 e 10.
4. 6 e 8.
5. NDA

Autor(a): Peterson Katagiri Zilli

033-2007

MO640 - Questão para a prova oral
Número: 033
Enunciado:
Dada a seqüência pi = "8 7 3 1 2 5 6 4", qual é o número de ciclos e a distância de intercâmbio de blocos, respectivamente?

1. 3 e 3
2. 3 e 4
3. 4 e 3
4. 4 e 4
5. NDA

Autor(a): Andrey Seiji Shimada

032-2007

MO640 - Questão para a prova oral
Número: 032
Enunciado:
Quanto à ordenação de permutações (baseado nos textos de transposição e troca de blocos) podemos afirmar que (considere perm(0)=0 e perm(n+1)=n+1):

1. Em um grafo de ciclos de uma permutação, as arestas cinzas são direcionadas de i+1 para i.
2. [perm(i), perm(i+1)] é um breakpoint se perm(i+1)=perm(i)+1.
3. Uma troca de blocos com parâmetros (i,j,k,l), realiza a troca de [perm(i) ... perm(j)] e [perm(k) ... perm(l)].
4. Numa transposição p(i,j,k) com i < j < k, trocamos [perm(i) ... perm(j-1)] e [perm(j) ... perm(k-1)].
5. NDA

Autor(a): Paulo Renato de Faria

029-2007

MO640 - Questão para a prova oral
Número: 029
Enunciado:
Dada a permutação abaixo, qual o número mínimo de operações necessárias para
ordená-la por intercâmbio de blocos?

2          4          3          8          5          6          1          7

1. 7
2. 5
3. 3
4. 1
5. NDA

Autor(a): Daniel M. Ivasse

037-2006

MO640 - Questão para a prova oral
Número: 037
Enunciado:
Qual afirmação a respeito de block interchange está incorreta?

1. Block interchange consiste na troca de posição entre dois blocos de cromossomo que não possuem intersecção.
2. Block interchange, assim como transposições e reversões, são consideradas mutações de blocos de cromossomos, ao invés de mutações pontuais.
3. Sempre é possível encontrar um block interchange que remove ao menos dois breakpoints de uma dada permutação, a não ser que esta seja a permutação identidade.
4. A transposição pode ser encarada como uma generalização do block interchange.
5. NDA

Autor(a): Bruno Dilly

031-2006

MO640 - Questão para a prova oral
Número: 031
Enunciado: Existem dois tipos de rearranjo de genomas que são relativamente semelhantes : “Transposição” e “Troca de Blocos”. Em relação a esses eventos podemos afirmar que:

1. Na verdade eles são dois nomes para o mesmo evento, pois ambos tratam de dois blocos trocando de lugar.
2. Troca de Blocos é um caso especial de Transposição, onde a troca se dá entre blocos adjacentes.
3. Transposição é um caso especial de Troca de Blocos, onde a troca se dá entre blocos que estão em duas fitas diferentes do DNA.
4. Transposição é um caso especial de Troca de Blocos, onde a troca se dá entre blocos adjacentes.
5. NDA

Autor(a): Mirela

085-2005

MO640 - Questão para a prova oral
Número: 085
Enunciado:
Assinale a alternativa INCORRETA a respeito das operações de Block-Interchange

1. Uma operação de block-interchange pode ser vista como uma generalização da transposição
2. Em qualquer permutação, com exceção da identidade, é possível encontrarmos uma operação de block-interchange que remova ao menos dois breakpoints
3. Uma operação de block-interchange pode remover até 4 breakpoints, e assim adicionar até 4 ciclos em uma permutação
4. Quando uma operação de block-interchange mínima é aplicada, o número de ciclos de uma permutação é acrescido de 2
5. NDA

Autor(a): Leonardo Elias Mariote

084-2005

MO640 - Questão para a prova oral
Número: 084
Enunciado:
Qual das afirmações abaixo é INCORRETA com relação ao algoritmo de ordenação por intercâmbio de blocos, proposto por Christie, no artigo Sorting permutations by block-interchanges:

1. O algoritmo possui complexidade O(n²).
2. O algoritmo se basea numa operação chamada de minimal block-interchange que sempre remove 2 pontos de quebra.
3. O número de ciclos do grafo de ciclos (cycle graph) é sempre aumentado de 2 a cada operação de intercâmbio de blocos realizada pelo algoritmo.
4. O algoritmo possui fator de aproximação 2, já que é possível realizar operações de intercâmbio de blocos que removem até 4 pontos de quebra.
5. NDA

Autor(a): Marcelo de Almeida Oliveira