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