027-2011

MO640 - Questão para a prova oral

Número: 027

Enunciado: Considerando a composição de permutações abaixo, qual é a alternativa correta:

(4 2 5 1 3 6 8 7) (4 5 6 7 8) (7 6 5 4 3 2 1 8) (1 2 3)

a) O resultado é formado por um 2-ciclo e um 4-ciclo disjuntos.

b) O resultado é um 4-ciclo.

c) O resultado é formado por dois 4-ciclos disjuntos.

d) O resultado é um 6-ciclo.

e) NDA

026-2011

  MO640 - Questão para a prova oral

Número: 026

Enunciado: Quantos pares orientados possui o seguinte genoma?

(0 -5 -6 -1 -3 -2 4 7)

1. 0
2. 2
3. 4
4. 8
5. NDA

025-2011

MO640 - Questão para prova oral

Número: 025
Enunciado:
Sobre permutações, selecione a afirmativa incorreta.

1. Seja α = (a b c) e seja β uma permutação tal que a, b, c estão distribuídos em dois ciclos de β. O número total de ciclos em αβ será menor que o número de ciclos de β.
2. Sejam α = (a b) e β uma permutação qualquer. Se a e b estiverem no mesmo ciclo da decomposição em ciclos de β, então na decomposição em ciclos do produto αβ este ciclo estará quebrado em dois.
3. Sejam α = (a b) e β uma permutação qualquer. Suponha que a e b encontram-se em ciclos separados da decomposição em ciclos de β. Estes ciclos tornar-se-ão um só na decomposição em ciclos de αβ.
4. Dada uma permutação α, para se obter a sua inversa, α^-1, basta inverter cada ciclo da decomposição em ciclos de α.
5. NDA

024-2011

MO640 - Questão para a prova oral

Número: 024-2011
Enunciado:
Assinale a alternativa INCORRETA.

1. Cada componente de um diagrama realidade-desejo equivale a um componente conexo no interleave graph correspondente.
2. Em um diagrama realidade-desejo, um componente A separa dois outros componentes B e C se todas as cordas entre algum terminal em B e algum terminal em C cortam alguma aresta desejo de A.
3. Um componente bom é um componente que contém um ciclo bom. Um ciclo bom é tal que possui pelo menos um par de arestas divergentes.
4. Um obstáculo é um componente ruim que não separa nenhum par de componentes.
5. NDA

Ideia original de: Kaio Karam

023-2011

MO640 - Questão para a prova oral

Número: 023-2011

Enunciado:

Dada a permutação α =(-5,+3,-1,+4,-2), qual dos Reality and Desire Diagrams abaixo melhor representa RD(α)?

a.

b.

c.

d.

e. NDA

Ideia original de: Alexandre de Queiroz

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

021-2011

MO640 - Questão para a prova oral

Número: 021-2011

Enunciado:

De acordo com o artigo de Anne Bergeron, A Very Elementary Presentation of Hannenhalli-Pevzner Theory, 2005, qual das alternativas abaixo NÃO apresenta o resultado de uma reversão que minimiza o score resultante quando aplicada a p = (1 -5 2 6 4 -3 -8 7)?

1. (1 -2 5 6 4 -3 -8 7)
2. (1 -5 2 6 4 -3 -8 -7)
3. (1 -5 -4 -6 -2 -3 -8 7)
4. (1 -5 2 3 -4 -6 -8 7)
5. NDA

Ideia original de: Adriano Batista Prieto

020-2011

MO640 - Biologia Computacional

Qual é a alternativa FALSA:

a) Para o problema de distância de transposição de prefixo, é possivel determinar quando uma permutação pode ser ordenada usando exatamente o número de operações indicado pela lower bound de breakpoints.

b) Dados dois genomas circulares, há um algortimo linear que determina uma série de fusões, fissões e transposições, de peso mínimo, que transforma um genoma no outro, quando o peso da transposição é 2 e o peso das duas outras operações é 1.

c) A distância de transposição entre uma permutação de tamanho n ≥ 2 e a permutação que representa a sua inversa é exatamente [n/2]+1.

d) Existem algoritmos de aproximação com fator 3/2 para o problema de ordenação por transposição.

e) NDA.

019-2011

MO640 - Questão para a Prova Oral

Enunciado:

Dadas as sequências {A,B,C,D,E}, {E,D,C,B,A} e {D,E,C,B,A}, sendo que A=5, B=4, C=3, D=2 e E=1, quais os números de breakpoints, respectivamente, em relação a {1,2,3,4,5}?

a. 5, 0 e 2

b. 5, 1 e 4

c. 6, 1 e 3

d. 6, 0 e 3

e. NDA

 

095-2008

MO640 - Questão para a prova oral
Número: 095
Enunciado:
Usando os métodos de Bergeron e colegas quanto à ordenação por translocação, assinale a alterativa que contém o número mínimo de translocações para transformar o genoma A no genoma B:

A = {(1,4,5,2),(3,6,7,8)};
B = {(1,2),(3,4,5,6,7,8)};

Dica: d(A)=n - N - c + t

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

Autor(a): Tiago Takamoto

094-2008

MO640 - Questão para a prova oral
Número: 094
Enunciado:
No problema de rearranjo de genomas sempre há uma operação DCJ (double-cut-and-join) que reduz a diferença entre o número de breakpoints e de ciclos (b - c) em uma unidade, exceto quando o genoma já se encontra ordenado. Outras características deste problema são:

1. Uma operação DCJ não pode aumentar (b - c).
2. Uma operação DCJ sempre aumenta o número de ciclos.
3. Uma operação DCJ sempre diminui o número de breakpoints.
4. a distância genômica, com relação à operação DCJ, é igual a (b - c).
5. NDA

Autor(a): Fabio L. Usberti

093-2008

MO640 - Questão para a prova oral
Número: 093
Enunciado:
Dado os genomas: A={(3 2)(1 4 8)(6 7 5)} e B={(1 2)(3 4 5)(6 7 8)} Quais das afirmativas abaixo são FALSAS:
I- Os genomas não são "co-tailed".
II- Exitem dois ciclos pretos para uma concatenação de A.
III- A translocação que gera A1={(3 4 8)(1 2)(6 7 5)}, partindo de A, é interna.

1. I.
2. II.
3. I e II.
4. I, II e III.
5. NDA

Autor(a): Maria Angélica Lopes de Souza

092-2008

MO640 - Questão para a prova oral
Número: 092
Enunciado:
De acordo com o artigo "On Sorting by Translocations" de Bergeron, Mixtacki e Stoye, a complexidade dos algoritmos para encontrar a distância de translocação e para fazer a ordenação por translocações em genomas de tamanho n é, respectivamente:

1. O(n) e O(n²)
2. O(n) e O(n³)
3. O(n²) e O(n²)
4. O(n²) e O(n³)
5. NDA

Autor(a): Victor de Abreu Iizuka

091-2008

MO640 - Questão para a prova oral
Número: 091
Enunciado:
Sobre a operação Double-Cut-Join descrita no artigo "Efficient sorting of genomic permutations by translocation, inversion and block interchange" é incorreto afirmar que:

1. Considera diretamente obstáculos (hurdles)
2. Pode diminuir ou aumentar o número de ciclos
3. Pode gerar cromossomos circulares intermediários
4. É uma operação local que opera em quatro vértices inicialmente conectados em pares
5. NDA

Autor(a): Bruno Conti Marini

090-2008

MO640 - Questão para a prova oral
Número: 090
Enunciado:
Quais dos eventos de evolução a seguir podem ser modelados por uma ou mais aplicações da operação de double-cut-and-join?

I - Translocação
II - Reversão
III - Troca de blocos

1. Somente I e II.
2. Somente I e III.
3. Somente II e III.
4. I, II e III.
5. NDA

Autor(a): João Paulo Pereira Zanetti

089-2008

MO640 - Questão para a prova oral

Número: 089

Enunciado:
A menor fortaleza possui quantos ciclos?

1. 3
2. 6
3. 9
4. 12
5. NDA

Autor(a): Priscila do Nascimento Biller

088-2008

MO640 - Questão para a prova oral
Número: 088

Enunciado: Na literatura encontramos a fórmula da distância de reversão: d = n + 1 - c + h + f. Considere o diagrama realidade e desejo ao lado. Qual é o valor da distância de reversão? 10 11 12 13 NDA

Autor(a): Gustavo Waku

087-2008

MO640 - Questão para a prova oral
Número: 087
Enunciado:
Sobre o algoritmo de Bader, Moret e Yan para o cálculo de distância de reversão de permutações de tamanho n, podemos afirmar que:

1. Seu limitante inferior de tempo é O(n²).
2. Ele executa em O(n) para a maioria dos casos, mas não para todos.
3. Ele calcula a distância e os passos da ordenação em tempo O(n).
4. Ele calcula a distância em complexidade O(n) mas não calcula os passos da ordenação.
5. NDA.

Autor(a): Danilo Brandão Gonçalves

086-2008

MO640 - Questão para a prova oral
Número: 086
Enunciado:
Encontramos fórmulas diferentes na literatura para a distância de seqüências por reversão:

1. d(α) = n + 1 - c(α) + h(α) + f
2. d(α) = b(α) - c(α) + h(α) + f

onde n é o comprimento da seqüencia, b(α) é o número de breakpoints, h(α) é o número de obstáculos (hurdles) e f é um fator de correção para fortalezas (fortresses).

Por que há esta diferença?

1. Na 1ª fórmula c(α) é o total de ciclos menos os ciclos de tamanho 2. Na segunda c(α) é simplesmente o total de ciclos.
2. Na 2ª fórmula c(α) é o total de ciclos menos os ciclos de tamanho 2. Na primeira c(α) é simplesmente o total de ciclos.
3. Na 2ª fórmula c(α) é o total de ciclos bons. Na primeira c(α) é o total de ciclos ruins.
4. Na 1ª fórmula c(α) é o total de ciclos bons. Na segunda c(α) é o total de ciclos ruins.
5. NDA

Autor(a): Pedro Henrique Del Bianco Hokama

085-2008

MO640 - Questão para a prova oral
Número: 085
Enunciado: Considere o grafo de realidade e desejo a seguir, e os possíveis tipos de reversões seguras que existem. Qual dos tipo de reversão segura, se aplicandos neste momento, estarão caminhando na direção de ordená-lo com o mínimo número de reversões?

I. Reversão segura Tipo 1: definida sobre duas arestas reais divergentes em um ciclo bom. II. Reversão segura Tipo 2 (Hurdle Merging): definida sobre duas arestas reais em hurdles não consecutivos. III. Reversão segura Tipo 3 (Hurdle Cutting): definida sobre duas arestas reais de um mesmo ciclo ruim.

1. Somente I e II
2. Somente I e II
3. Somente II e III
4. O grafo consiste em uma fortaleza, logo não há reversão segura.
5. NDA

Autor(a): Fabio L. Usberti