064-2006

MO640 - Questão para a prova oral
Número: 064
Enunciado:
Quais das transposições de prefixo ρ₁ e ρ₂ abaixo correspondem à transposição ρ(3,6,10), de forma que em uma permutação π temos que ρ₂ρ₁π = ρπ?

1. ρ₁(1,5,7) e ρ₂(1,6,10)
2. ρ₁(1,3,6) e ρ₂(1,4,10)
3. ρ₁(1,5,7) e ρ₂(1,4,10)
4. ρ₁(1,4,10) e ρ₂(1,3,6)
5. NDA

Autor: Pedro Feijão

063-2006

MO640 - Questão para a prova oral
Número: 063
Enunciado:  Em relação ao artigo de Bafna e Pevzner sobre transposições (1998) podemos afirmar que:
I - O melhor limite inferior encontrado para a distância de transposição foi de (n +1 -c_odd(π)) / 2.
II - O melhor limite superior encontrado para a distância de transposição foi de n + 1 - c(π).
III - O melhor algoritmo de aproximação tem a taxa de 1.5.

Quais destas estão corretas?

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

Autor(a): Marcus Vinícius Benedito

062-2006

MO640 - Questão para a prova oral
Número: 062
Enunciado: Sobre os conceitos de transposição de prefixos vistos no artigo “Dias e Meidanis” podemos afirmar que:

1. Qualquer transposição pode ser substituida por duas transposicoes de prefixo.
2. A distancia de ordenação por transposicao de prefixos é igual a distancia de ordenação por transposicoes.
3. Nem sempre é possível achar uma transposicao de prefixo que retira breakpoints.
4. É possível achar transposições de prefixo que retiram até 3 breakpoints.
5. NDA

Autor(a): Mirela Dal Col Silva

061-2006

MO640 - Questão para a prova oral
Número: 061
Enunciado:
Qual é a distancia de transposicão para a seguinte seqüência: (4 3 5 7 2 1 6)

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

Autor(a): Matthias Gallé

060-2006

MO640 - Questão para a prova oral
Número: 060
Enunciado:
Segundo o artigo "Sorting by Prefix Transpositions", Dias e Meidanis qual o diametro da transposição por prefixo da seguinte permutação (8 7 6 5 4 3 2 1)

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

Autor(a): Renato Cristiano Torres

059-2006

MO640 - Questão para a prova oral
Número: 059
Enunciado:
Qual das seguintes afirmações a respeito de transposição de prefixo, tratadas pelo artigo de Dias e Meidanis, está correta?

1. Para qualquer permutação, temos que a distância de transposição é maior ou igual à distância de transposição de prefixo;
2. O diâmetro de transposição de prefixo, D(n), sendo n o tamanho da permutação, é tal que:
   n/2 <= D(n) <= 3n/4;
3. Sendo π uma permutação, para qualquer transposição p(x,y,z) com x ≠ 1, existem transposição de prefixo p1 e p2 tais que p2p1π = pπ
4. As únicas permutações que não possuem breakpoints são as permutações identidades, para todos os tamanhos de permutação;
5. NDA

Autor(a): Bruno Dilly

058-2006

MO640 - Questão para a prova oral
Número: 058
Enunciado:
Com relação ao algoritmo descrito por A. Bergeron, qual dos passos está incorreto?

1. Se uma permutação tem um número par de obstáculos, maior que 2, una dois obstáculos não consecutivos.
2. Se uma permutação tem um número ímpar de obstáculos, maior ou igual a 3, e tem um obstáculo simples, corte este obstáculo.
3. Se uma permutação tem um número ímpar de obstáculos, igual a 3, e não tem obstáculos simples, una dois obstáculos consecutivos.
4. Se uma permutação tem um número ímpar de obstáculos, maior que 3, e não tem obstáculos simples, una dois obstáculos não consecutivos.
5. NDA

Autor(a): Bruno Dilly

057-2006

MO640 - Questão para a prova oral
Número: 057
Enunciado:
Considerando que não existem intervalos enquadrados (framed intervals) de tamanho ≤ 2, o que pode-se afirmar sobre a permutação (0 2 5 4 3 6 8 7 9 1 10)?

1. Existem apenas 1 intervalo enquadrado e 1 obstáculo.
2. Existem 2 intervalos enquadrados, e 2 obstáculos.
3. Existem 3 intervalos enquadrados e 2 obstáculos.
4. Existem 4 intervalos enquadrados e 2 obstáculos.
5. NDA

Autor(a): Tiago Rinck Caveden

056-2006

MO640 - Questão para a prova oral
Número: 056
Enunciado:
Em relação aos conceitos apresentados por Bergeron em seu artigo "A very elementary presentation of the Hannenhalli-Pevzner theory", podemos dizer que:
I. O número de framed intervals em uma permutação reduzida é sempre par.
II. Em uma permutação reduzida, um framed interval de 6 ou menos elementos é sempre um obstáculo
III. Se uma permutação tem exatamente tres obstáculos, eles são obstáculos simples.

1. Apenas a afirmação I está correta.
2. Apenas a afirmação IIIestá correta.
3. Apenas as afirmações I e III estão corretas.
4. Todas as afirmações estão corretas.
5. NDA

Autor: Pedro Feijão

055-2006

MO640 - Questão para a prova oral

Número: 055
Enunciado: A respeito do algoritmo de ordenação por reversões apresentado por Anne Bergeron podemos afirmar que:

1. Qualquer permutação reduzida possui pelo menos um “framed interval”.
2. Uma permutação reduzida é aquela que possui todos os elementos consecutivos.
3. Uma permutação reduzida é aquela que possui apenas um par ordenado.
4. Um obstáculo é um “framed interval” que contém um ou mais outros “framed intervals”.
5. NDA

Autor(a): Mirela Dal Col Silva

054-2006

MO640 - Questão para a prova oral
Número: 054
Enunciado:
Segundo o paper de Bergeron (2002), qual é a matriz de bits correspondentes ao grafo de sobreposição da permutação (-2, 4, 3, -1) (ignorando o s)? Lembre-se que esta matriz nada mais é do que a matriz de adjacências do grafo de sobreposição de arcos, com a linha p indicando a coloração (1 para negro, 0 para branco).

A.

v0 v1 v2 v3 v4 v0 0 0 1 0 1 v1 0 0 1 1 0 v2 1 1 0 1 0 v3 0 1 1 0 1 v4 1 0 0 1 0 p 0 0 1 1 0

B.

v0 v1 v2 v3 v4 v0 0 0 0 0 1 v1 0 1 1 0 1 v2 1 1 0 1 1 v3 0 0 1 1 1 v4 0 1 0 1 0 p 0 1 0 1 1

C.

v0 v1 v2 v3 v4 v0 0 1 0 0 1 v1 0 0 1 1 1 v2 0 1 0 1 1 v3 1 0 1 0 1 v4 1 0 1 0 0 p 1 0 1 0 1

D.

v0 v1 v2 v3 v4 v0 0 0 0 0 1 v1 0 0 1 0 1 v2 0 1 0 1 1 v3 0 0 1 0 1 v4 1 1 1 1 0 p 1 0 1 0 0

E.

NDA

Autor(a): Matthias Gallé

053-2006

MO640 - Questão para a prova oral
Número: 053
Enunciado:
Considere a seguinte permutação:

π = (0 2 1 3 6 5 4 7 9 8 10)

Escolha dentre as alternativas abaixo aquela que representa um intervalo emoldurado (framed interval) da permutação π , de acordo com a definição da doutora A. Bergeron.

1. 2 1 3 6 5
2. 8 10 0 2 1
3. 6 5 4 7 9
4. 3 6 5 4 7
5. NDA

Autor(a): Douglas José Soares Rodrigues

052-2006

MO640 - Questão para a prova oral
Número: 052
Enunciado: Considere as afirmações abaixo relativas ao artigo (Bergeron 2005).
I - As arestas cinzas (arcos) do grafo de pontos de quebra são representadas como vértices no grafo de sobreposição de arcos.
II - As arestas cinzas (arcos) que se cruzam no grafo de pontos de quebra dão origem às arestas do grafo de sobreposição de arcos.
III - Os vértices cheios (negros) do grafo de sobreposição de arcos representam arestas orientadas do grafo de pontos de quebra.
IV - Os ciclos do grafo de pontos de quebra representam as componentes conexas do grafo de sobreposição de arcos.

Quais destas estão corretas?

1. I, II, III.
2. I, II, IV.
3. II, III, IV.
4. Todas as afirmações são corretas.
5. NDA

Autor(a): Marcus Vinícius Benedito

051-2006

MO640 - Questão para a prova oral
Número: 051
Enunciado:
Considere a seguinte permutação (0, 1, 7, 6, -10, 9, -8, 2, -11, -3, 5, 4, 12), já estendida com 0 e n+1. Quantos pares orientados ela possui?

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

Autor(a): Renato Cristiano Torres

050-2006

MO640 - Questão para a prova oral
Número: 050
Enunciado:
Qual a possível consequência de se aplicar a técnica de mesclagem (merge) em uma fortaleza com h obstáculos?

1. São destruídos dois super-obstáculos, criando uma nova fortaleza com h - 2 obstáculos, exceto para o caso h = 3.
2. São destruídos dois obstáculos simples, "desfazendo" a fortaleza, porém apenas no caso h = 3.
3. São destruídos dois obstáculos simples, tornando a fortaleza uma nova fortaleza com h - 2 obstáculos, exceto para o caso h = 3.
4. São destruídos dois super-obstáculos e criados dois obstáculos simples, criando uma nova fortaleza com h - 2 obstáculos, exceto para o caso h = 3.
5. NDA

Autor(a): Tiago Rinck Caveden

049-2006

MO640 - Questão para a prova oral

Número: 049
Enunciado:
Dadas duas permutações, α e β, e considerando que ρ₁, ρ₂,...,ρ_t é uma série mínima de reversões sinalizadas que transformam α em β, ou seja

αρ₁ρ₂...ρ_t = β

A distância entre as permutações é definida como d_β(α) = t.
Sendo assim, uma reversão segura (safe reversal) ρ, de acordo com as notas de aula de Mneimneh, tem a seguinte propriedade:

1. d_β(αρ) = 1.
2. d_β(αρ) < 1.
3. d_β(αρ) < d_β(α).
4. d_β(α) < d_β(αρ).
5. NDA

Ideia original de: Douglas José Soares Rodrigues

048-2006

MO640 - Questão para a prova oral
Número: 048
Enunciado: Dados
Condições:
X- Tenho uma componente boa no grafo
Y- Não tenho componentes boas e o número de obstáculos é ímpar
Z- Não tenho componentes boas e o número de obstáculos é par
Tipo de Reversões:
Tipo 1: Reversão segura do tipo “quebra ciclos” que não cria componentes ruins.
Tipo 2: Mescla dois obstáculos opostos.
Tipo 3: “Quebra” um obstáculo, agindo em um ciclo ruim e tornando-o um ciclo bom.
Considerando o algoritmo de ordenar uma permutação usando reversões apresentado nas “Lectures” de Saad Mneimneh podemos dizer que:

1. Se X então aplica Tipo 1. Se Y então aplica Tipo 2. Se Z então aplica Tipo 3.
2. Se X então aplica Tipo 1. Se Y então aplica Tipo 3. Se Z então aplica Tipo 2.
3. Se X então aplica Tipo 3. Se Y então aplica Tipo 1. Se Z então aplica Tipo 2.
4. Se X então aplica Tipo 3. Se Y então aplica Tipo 2. Se Z então aplica Tipo 1.
5. NDA

Autor(a): Mirela Dal Col Silva

047-2006

MO640 - Questão para a prova oral
Número: 047
Enunciado:
Saad Mneimneh introduz um novo conceito, chamado de separação. Qual das seguintes afirmações é certa?

1. Se A separa B e C, então B não separa a A e C.
2. A é uma separação entre dois componentes B e C se qualquer aresta imaginária (corda) no grafo de interleaving entre um vértice de B e um vértice de C, cruza um vértice desejável de A.
3. Uma reversão definida por dois vértices em dois componentes A e B, tem como consequência que todos os componentes bons que separam A e B se transformem em ruins, e todos os ruins que separam A e B se transformem em bons.
4. Uma componente qualquer é um obstáculo se ele não separa outros dois componentens ruins.
5. NDA

Autor(a): Matthias Gallé

046-2006

MO640 - Questão para a prova oral
Número: 046
Enunciado:
Qual das seguintes afirmações a respeito de obstáculos está incorreta, considerando-se o texto de S. Mneimneh?

1. Um obstáculo é um componente ruim que não separa outros dois componentes ruins
2. Qualquer obstáculo que não seja considerado super obstáculo é chamado de obstáculo simples
3. Um obstáculo é considerado um super obstáculo quando, ao ser removido, faz com que um componente que não era um obstáculo se transforme em obstáculo
4. Em uma fortaleza, todos os obstáculos são super obstáculos
5. NDA

Autor(a): Bruno Dilly

045-2006

MO640 - Questão para a prova oral
Número: 045
Enunciado: Num problema de ordenação por reversões, resultou o seguinte diagrama de ciclos. Sobre este diagrama, podemos afirmar que:

1. Ele possui três componentes, sendo que todas elas são componentes ruins e super-obstáculos que formam uma fortaleza.
2. Ele possui três componentes, sendo que uma delas é boa e as outras duas são ruins.
3. Ele possui três componentes, sendo que duas delas são componentes boas e a outra é uma componente ruim e também um obstáculo simples.
4. Ele possui três componentes, sendo que duas delas são componentes boas e a outra é uma componente ruim que não é obstáculo.
5. NDA

Autor(a): Marcus Vinícius Benedito

044-2006

MO640 - Questão para a prova oral
Número: 044
Enunciado: No artigo (Hannenhalli-Pevzner 1999) vimos o conceito de fortaleza, que é uma permutação difícil de ordenar. Se π é uma fortaleza, quantos passos são necessários para fazê-lo?

1. c(π)
2. b(π) - c(π) + h(π)
3. b(π) - c(π)
4. b(π) - c(π) + h(π) + 1
5. NDA

Autor(a): Marcus Vinícius Benedito

043-2006

MO640 - Questão para a prova oral
Número: 043
Enunciado: Qual a alternativa INCORRETA em relação aos conceitos apresentados no paper do Hannenhalli e Pevzner?

1. Todo obstáculo é uma componente não orientada.
2. As componentes orientadas se resolvem sozinhas, não possuindo obstáculos.
3. Se um super obstáculo é resolvido, uma outra componente não orientada passará a ser um obstáculo.
4. Toda componente não orientada é um obstáculo.
5. NDA

Autor(a): Mirela Dal Col Silva

042-2006

MO640 - Questão para a prova oral
Número: 042
Enunciado:
Considerando as seguintes afirmações sobre grafos de arestas coloridas, baseado no texto de Hannenhalli e Pevzner:

1. Um ciclo neste tipo de grafo é dito alternado se as cores de duas arestas consecutivas são sempre distintas
2. O comprimento de um ciclo alternado é o número total de arestas que ele possui
3. Um ciclo alternado é dado como pequeno se seu comprimento é igual a 2, e grande se maior que dois
4. Uma permutação π é simples seu grafo de breakpoints não possui ciclos longos.

1. Apenas a afirmação I está correta
2. Apenas a afirmação II está incorreta
3. Somente as afirmações I, II e III estão corretas
4. Todas as afirmações estão corretas
5. NDA

Autor(a): Bruno Dilly

041-2006

MO640 - Questão para a prova oral
Número: 041
Enunciado:
Um block-interchange é um rearranjo composto pelo produto de 4 2-ciclos :
(u x) (πΓx πΓu) (v y) (πΓy πΓv)
com certas restrições.
Qual das restrições abaixo não está correta?

1. u ≠ x, u ≠ y, v ≠ x, v ≠ y
2. u, v, x ∈ orb(π, y)
3. (u v) (x y) | π
4. (u y) (v x) | π
5. NDA

Autor(a): Bruno Dilly

040-2006

MO640 - Questão para a prova oral
Número: 040
Enunciado:
Considere a permutação π = (p s o t) (a b c d). Qual deve ser a permutação Γ para que π seja um genoma, na definição de Mira e Meidanis (2005)?

1. Γ = (p d) (s c) (o b) (t a)
2. Γ = (p o) (s t) (a c) (b d)
3. Γ = (p a) (s b) (o c) (t d)
4. Γ = (p s) (o t) (a b) (c d)
5. NDA

Autor: Pedro Feijão

039-2006

MO640 - Questão para a prova oral
Número: 039
Enunciado: Dado o genoma  π = (g  c  a  f  e  b) (d h i)  e as seguintes afirmações:

        I.      ( a  d ) representa uma fissão sobre π

     II.      ( a  b ) representa uma fusão sobre π

   III.      ( c e ) ( f  b) representa um block interchange sobre π

Podemos dizer que:

1. Apenas I e II estão corretas
2. Apenas I e III estão corretas  
3. Apenas III está correta
4. Todas estão corretas
5. NDA

Autor(a): Mirela Dal Col Silva

038-2006

MO640 - Questão para a prova oral
Número: 038
Enunciado:
Para o genoma π = (a b c d e f g h i j l m) (-m -l -j -i -h -g -f -e -d -c -b -a), qual das seguintes permutações poderia ser considerada uma troca de blocos?

1. (a c) (-a -c) (b d) (-b -d)
2. (b g) (-a -f) (e l) (-d -j)
3. (a d) (-m -c) (f h) (-e -g)
4. (a d) (-m -c) (g j) (-f -i)
5. NDA

Autor(a): Tiago Rinck Caveden

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

036-2006

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

Considere o genoma π = (a b c d) (e f g h). Sobre as seguintes permutações podemos dizer que:

I. A permutação ρ = (d f) é uma fusão ao ser aplicada ao genoma π.
II. A permutação ρ = (d f) é uma fissão ao ser aplicada ao genoma π.
III. A permutação φ = (b d a) é uma transposição ao ser aplicada ao genoma π.

1. Apenas a afirmação I está correta.
2. Apenas a afirmação III está correta.
3. As afirmações I e II estão corretas.
4. As afirmações I e III estão corretas.
5. NDA

Autor(a): Pedro Feijão

035-2006

Número: 035
Enunciado:
Dada uma permutação P, a norma de P, denotada por |P|, é o número mínimo de 2-ciclos em uma representação de P como produto de 2-ciclos. Qual das alternativas é correta:

1. a norma da permutação identidade é 1;
2. a norma da conjugação de Q por P é igual à norma de P;
3. a norma da composição PQ é maior que a soma das normas de P e Q;.
4. a norma de uma permutação é igual à norma de sua inversa;
5. NDA

Autor(a): Renato Cristiano Torres

034-2006

MO640 - Questão para a prova oral
Número: 034
Enunciado:
A operação de conjugação de uma permutação α por β, denotada por β • α, pode ser definida como:

1. βαβ^-1.
2. αβα.
3. α^-1β^-1α.
4. βαβ.
5. NDA

Autor(a): Douglas José Soares Rodrigues

033-2006

MO640 - Questão para a prova oral
Número: 033
Enunciado:
A respeito dos eventos de rearranjo de genomas, qual das alternativas está incorreta:

1. A inserção e deleção são respectivamente ganho e perda de genes entre genomas.
2. A fusão é junção de dois genomas.
3. A fissão é quebra de um genoma em exatamente dois novos genomas.
4. A transposição é troca de dois segmentos adjacentes.
5. NDA

Autor(a): Renato Cristiano Torres

032-2006

MO640 - Questão para a prova oral
Número: 032
Enunciado:
Qual dentre os seguintes NÃO é um evento de rearranjo de genomas?

1. Fusão
2. Transversão
3. Troca de blocos
4. Transposição
5. NDA

Autor(a): Tiago Rinck Caveden

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

030-2006

MO640 - Questão para a prova oral
Número: 030
Enunciado:
Considere o genoma π = (A B C D E F G) (-G -F -E -D -C -B -A). A operação de permutação ρ que gera um block-interchange entre os blocos (B,C) e (E,F), transformando o genoma em ρπ = (A E F D B C G) (-G -C -B -D -F -E -A) é:

1. ρ = (B E) (-D -A) (C F) (-E -B)
2. ρ = (B E) (-D -A) (D G) (-F -C)
3. ρ = (B E) (-E -A) (D G) (-F -C)
4. ρ = (B E) (-D -A) (D G) (-F -E)
5. NDA

Autor(a): Pedro Feijão

029-2006

MO640 - Questão para a prova oral
Número: 029
Enunciado: Qual é o resultado da aplicação da reversão sinalizada ρ(B, D) no genoma circular π = (A B C D) (-D -C -B -A)?

1. ρπ = (B C -A -D) (D A -C -B)
2. ρπ = (A B C D) (-D -C -B -A)
3. ρπ = (B C -D -A) (-C -B A D)
4. ρπ = (-D -C -B A) (-A B C D)
5. NDA

Autor(a): Marcus Vinícius Benedito

028-2006

MO640 - Questão para a prova oral
Nmero: 028
Enunciado:
Qual das seguintes é errada:

1. Se dois ciclos são disjuntos, então o seu produto é comutativo
2. A identidade é disjunta dela mesma
3. Dois ciclos são disjuntos quando suas órbitas são disjuntas
4. se dois ciclos são disjuntos, então o produto deles aplicado a um elemento x é igual a aplicar so' o ciclo onde ocorre x (se não ocorre en nenhum, então aplicar a identidade)
5. NDA

Autor(a): Matthias Gallé

027-2006

MO640 - Questão para a prova oral
Número: 027
Enunciado:
Sobre as novas técnicas de sequenciamento que produzem reads menores do que os obtidos com a técnica de Sanger, podemos dizer que:
I. Apesar de produzirem reads menores, a quantidade de dados produzidos é bem maior e com menor custo, possibilitando uma maior cobertura do genoma sequenciado.
II. A abordagem "overlap-layout-consensus" foi criada para resolver o problema de montagem gerados por estas novas técnicas.
III. Em projetos de sequenciamento via WGS (whole-genome-shotgun) com sequenciamento de Sanger, as informações obtidas através dos mated-pairs ajudam a resolver as regiões repetidas no genoma.

1. Apenas a afirmação I está correta.
2. Apenas a afirmação II está correta.
3. As afirmações I e II estão corretas.
4. Todas as afirmações estão corretas.
5. NDA

Autor(a): Pedro Feijão

026-2006

MO640 - Questão para a prova oral
Número: 026
Enunciado:
Faz parte do método de seqüenciamento de Sanger:

1. A criação de uma biblioteca de clones e o uso de eletroforese.
2. Adição de nucleotídios, em ordem, à solução com DNA e polimerase.
3. Verificação da emissão de luz na reação de oxidação da luciferina.
4. A visualização das bases do DNA no microscópio eletrônico.
5. NDA

Autor(a): Douglas José Soares Rodrigues

025-2006

MO640 - Questão para a prova oral
Número: 025
Enunciado:
Na montagem de fragmentos de DNA, qual a principal função dos "pares casados" (mate pairs)?

1. São eles que preenchem os espaços vazios entre e intra scaffolds.
2. Através deles é possível separar a porção eucromática (que será seqüenciada) da heterocromática (que em geral não é seqüenciada).
3. São usados no processo de clonagem do DNA, para aumentar o número de cópias a serem lidas e portanto facilitar a montagem.
4. Servem para inferir a posicao e a orientação relativas entre os contigs, uma vez que sabe-se que vem de fitas opostas, e qual a distância aproximada entre eles.
5. NDA

Autor(a): Tiago Rinck Caveden

024-2006

MO640 - Questão para a prova oral
Número: 024
Enunciado: As técnicas de sequenciamento e montagem de DNA vem melhorando ao longo dos anos. Dentre os itens abaixo, qual deles NÃO é uma das melhorias:

1. Maior volume da dados gerados devido a maior velocidade no sequenciamento dos trechos de DNA
2. Capacidade de ler reads maiores
3. Maior velocidade na clonagem do DNA
4. Computadores mais eficientes que aumentam a velocidade na montagem dos fragmentos de DNA
5. NDA

Autor(a): Mirela Dal Col Silva

023-2006

MO640 - Questão para a prova oral

Número: 023
Enunciado:
Podemos afirmar que trimagem de uma seqüência é:

1. A remoção de todas as regiões e repetidas presentes na seqüência.
2. A retirada de regiões de baixa qualidade ou contaminantes presentes na seqüência.
3. O uso de enzimas para cortar a seqüencia lida em fragmentos menores.
4. A obtenção de dados externos para comparar e corrigir partes da seqüência.
5. NDA

Ideia original de: Renato Cristiano Torres

022-2006

MO640 - Questão para a prova oral
Nmero: 022
Enunciado:
Qual dos seguintes é o maior problema que enfrenta o método shotgun:

1. O desenvolvimento de técnicas para detectar DNA repetido
2. A limpeza para filtrar o DNA dos vectores do DNA da espécie original
3. A baixa taxa de reprodução das cosmidios e BAC
4. Poder clonar a heterocromia dos centrômeros
5. NDA

Autor(a): Matthias Gallé

021-2006

MO640 - Questão para a prova oral

Número: 021
Enunciado:
Qual das afirmativas a respeito de evolução paralela está INCORRETA?

1. É um fenomeno onde espécies que não são genéticamente próximas compartilham um mesmo estado de um dado caractere.
2. Um exemplo típico de evolução paralela é a existêcia de asas tanto em pássaros como em morcegos.
3. Este fênomeno ocorre com abundância na natureza.
4. Também é conhecido como convergência
5. NDA

Autor(a): Bruno Dilly

020-2006

MO640 - Questão para a prova oral

Número: 020
Enunciado:

                  Caracteres

Object  c1   c2   c3   c4   c5

    A       1     1    0     0     0

    B       0     0    1     0     1

    C       1     1    0     0     1

    D       0     1    1     1     0

    E       1     1    0     0     1

Dada a matriz de características acima, e admitindo transições de estado apenas na direção 0 --> 1, podemos afirmar que:

1. Ela admite uma filogenia perfeita
2. Ela não admite uma filogenia perfeita pois os caracteres c1 e c2 não são compatíveis.
3. Ela não admite uma filogenia perfeita pois os caracteres c2 e c3 não são compatíveis.
4. Ela não admite uma filogenia perfeita pois os caracteres c4 e c5 não são compatíveis.
5. NDA

Autor(a): Mirela Dal Col Silva

019-2006

MO640 - Questão para a prova oral

Número: 019
Enunciado: O objetivo do “problema da compatibilidade” em filogenias é:

1. Explorar ao máximo eventos reversos e convergentes, visando obter uma filogenia perfeita.
2. Evitar a ocorrência de eventos reversos e convergentes, encontrando o máximo de caracteres que admitam uma filogenia perfeita entre eles.
3. Tornar os valores da matriz compatíveis entre si, maximizando o número de eventos reversos.
4. Encontrar o maior número possível de convergências, utilizando todos os eventos reversos possíveis.
5. NDA

Autor: Rodrigo Ritter

018-2006

MO640 - Questão para a prova oral

Número: 018
Enunciado:
A respeito de árvores filogenéticas, seria correto afirmar que:

1. É comprovado que, dentre todas as opções de "montagem" de uma árvore filogenética, as árvores mais parcimoniosas serão as que melhor refletem a realidade.
2. O chamado "relógio molecular" é um método para "enraizar" uma árvore sem raiz no qual supõe-se que para todas as espécies o número de mudanças de características ocorridas é aproximadamente o mesmo.
3. Desenhar uma árvore filogenética sem raiz é uma forma de se determinar a árvore mais parcimoniosa dentre as várias possíveis.
4. Para existir homoplasia numa árvore, é necessário que, dentre todas possíveis árvores, não exista nenhuma com menor número de mudanças de características.
5. NDA

Autor(a): Tiago Rinck Caveden

017-2006

MO640 - Questão para a prova oral
Número: 017
Enunciado:
O software fdnadist, da suíte de programas EMBOSS pode ser utilizado para:

1. Calcular uma matriz de distâncias entre seqüências de ácidos nucleicos de várias espécies.
2. Calcular a probabilidade de ocorrerem transições e transversões em uma determinada espécie.
3. Encontrar raízes para árvores filogenéticas.
4. Traçar uma possível árvore filogenética que represente a evolução das características de várias espécies.
5. NDA

Autor(a): Douglas José Soares Rodrigues

016-2006

MO640 - Questão para a prova oral

Número: 016
Enunciado: Os métodos que usam “parcimônia” para a construção de árvores filogenéticas tem por objetivo:

1. Buscar a filogenia que possua o menor número de “outgroups” dentre as espécies analisadas.
2. Buscar a filogenia que possua o maior número possivel de espécies que fiquem nas folhas da árvore, ou seja, espécies que não tenham dado origem a nenhuma das outras espécies.
3. Buscar a árvore filogenética que não possua uma raiz.
4. Buscar a filogenia que possua o menor número possivel de homoplasias.
5. NDA

Autor(a): Mirela Dal Col Silva

015-2006

MO640 - Questão para a prova oral
Número: 015
Enunciado:
Dadas as duas seguintes sequências:
AGCCAATGTT
GGCCCAAATC
Sejam X(t), Y(t) e Z(t), respectivamente, as probabilidades de, após um tempo t, uma base mutar para: outra igual (ou não mutar), outra do mesmo grupo, e outra de grupo diferente, definidas como na tese de mestrado de Quitzau.
Com respeito às duas sequências acima, separadas por t unidades de tempo, qual das seguintes afirmações e' certa?

1. Z(t) ≤ 0.15
2. X(t) ≥ 0.6
3. Y(t) ≥ 0.3 e Z(t) ≤ 0.05
4. X(t) ≤ 0.5 e Y(t) < 0.28
5. NDA

Autor(a): Matthias Gallé

014-2006

MO640 - Questão para a prova oral
Número: 014
Enunciado: Em relação aos modelos Jukes-Cantor e Kimura, vistos em aula, podemos afirmar que:

1. O modelo de Jukes-Cantor é mais preciso na criação das matrizes de distância, pois o modelo de Kimura leva em consideração apenas as probabilidades de ocorrerem transições e transversões na mudança de um nucleotídeo em uma seqüência.
2. Apesar do modelo de Jukes-Cantor ter se baseado no modelo de Kimura, este último continua mais preciso na representação da realidade, visto que este leva em conta transições e transversões.
3. O calculo da estimativa do tempo de divergência entre um par de espécies independe do modelo que estamos utilizando, pois estamos apenas criando matrizes de distância.
4. O modelo de Jukes-Cantor é uma especialização do modelo de Kimura se considerarmos alfa = beta.
5. NDA

Autor(a): Marcus Vinícius Benedito

013-2006

MO640 - Questão para a prova oral
Número: 013
Enunciado:
Considere as seguintes afirmações:
I. Para uma string de tamanho n, existem 1 + n(n+1)/2 substrings possíveis.
II. Para uma string de tamanho n, existem 2ⁿ subseqüencias possíveis.
III. Para uma string de tamanho n, existem n + 1 prefixos possíveis.

1. Somente a afirmação II está correta.
2. As afirmações I e II estão corretas.
3. As afirmações II e III estão corretas.
4. As afirmações I e III estão corretas.
5. NDA

Autor(a): Pedro C. Feijão

012-2006

MO640 - Questão para a prova oral
Número: 012
Enunciado:
A respeito de classes de problemas, podemos afirmar que:

1. Problemas da classe NP não podem ser resolvidos em tempo polinomial.
2. Qualquer problema NP pode ser reduzido em tempo polinomial a um problema NP-completo.
3. Há uma intersecção entre as classes de problemas P e NP, que não engloba completamente nenhuma das duas.
4. As classes de problemas P e NP são comprovadamente diferentes.
5. NDA

Autor(a): Tiago Rinck Caveden

011-2006

MO640 - Questão para a prova oral
Número: 011
Enunciado:
Qual é a principal diferença entre o modelo de Jukes-Cantor e o modelo de Kimura?

1. O modelo de Kimura é usado para estudar transições, enquanto o de Jukes-Cantor é usado para estudar transversões.
2. O modelo de Kimura é uma representação recursiva do modelo de Jukes-Cantor.
3. O modelo de Kimura é mais geral que o modelo de Jukes-Cantor, pois naquele transições e transversões recebem probabilidades diferentes.
4. Os modelos de Kimura e Jukes-Cantor servem para estudar assuntos completamente distintos, de forma que não faz sentido querer compará-los.
5. NDA

Autor(a): Douglas José Soares Rodrigues

010-2006

MO640 - Questão para a prova oral
Número: 010
Enunciado: Dados dois algoritmos A e B para resolver um problema, sendo que o algoritmo A leva tempo f(N)=N² em qualquer entrada de tamanho N, e o algoritmo B leva g(N)=aN, onde a é uma constante, em qualquer entrada de tamanho N. Pode-se concluir que:

1. O algoritmo A sempre será mais rápido que B em virtude de ser quadrático, independendo do tamanho N do problema.
2. O algoritmo B sempre será mais rápido que A em virtude ser linear, independendo do tamanho N do problema.
3. Quando o tamanho N for menor que a, o algoritmo quadrático será mais rápido.
4. Quando o tamanho N for maior que a, o algoritmo quadrático será mais rápido.
5. NDA

Autor: Rodrigo Ritter

009-2006

MO640 - Questão para a prova oral
Número: 009
Enunciado: Dada a string s = “AGGTCATG” qual das afirmações abaixo é FALSA?

1. “GTCA” é uma subsequencia de s.
2. “GTCA” é uma substring de s.
3. “GTAG” é uma subsequencia de s.
4. “GTAG” é uma substring de s.
5. NDA

Autor(a): Mirela Dal Col Silva

008-2006

MO640 - Questão para a prova oral
Número: 008
Enunciado: Os quatro tipos de nucleotídeos encontrados no DNA podem ser divididos em dois grupos que são as purinas e pirimidinas. Sabendo que um nucleotídeo, em uma posição específica de uma seqüência, pode sofrer uma mutação com o passar do tempo, podemos afirmar que:

1. Transição, que é a mudança de um nucleotídeo qualquer por outro do mesmo grupo, tem maior probabilidade de ocorrer.
2. Transversão, que é a mudança de um nucleotídeo qualquer por outro do mesmo grupo, tem maior probabilidade de ocorrer.
3. Transição, que é a mudança de um nucleotídeo qualquer por outro de um grupo diferente, tem maior probabilidade de ocorrer.
4. Transversão, que é a mudança de um nucleotídeo qualquer por outro de um grupo diferente, tem maior probabilidade de ocorrer.
5. NDA

Autor(a): Marcus Vinícius Benedito

007-2006

MO640 - Questão para a prova oral

Número: 007
Enunciado:
A respeito do estudo de um genoma, podemos afirmar que:

1. O termo locus refere-se à localização de um cromossomo dentro do núcleo.
2. O processo de obtenção da sequência de nucleotídeos de uma amostra de DNA é chamado de mapeamento.
3. As técnicas atuais utilizadas em laboratório produzem sequências sem erros.
4. Mapeamento físico é o processo de determinar a localização de certos marcadores em um cromossomo.
5. NDA

Ideia original de: Ézio Francisco Fagan Júnior

006-2006

MO640 - Questão para a prova oral
Número: 006
Enunciado:
Qual das seguintes afirmações é FALSA?

1. Enzimas de restrição são capazes de cortar moléculas de DNA.
2. cDNA, ou DNA complementar, só contém bases de éxons.
3. Cadeias de DNA são usualmente maiores e mais pesadas que cadeias peptídicas ou proteínas.
4. Atualmente, a técnica para leitura de seqüências de DNA conhecida como eletroforese em gel não consegue ler cadeias muito grandes, sendo 700 bp um limite aproximado.
5. NDA

Autor(a): Tiago Rinck Caveden

005-2006

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

Considere as seguintes afirmações com relação às diferenças entre DNA e RNA:

I. O açúcar do DNA é a desoxiribose enquanto que o do RNA é a ribose.
II. O DNA contém a uracil (ou uracila) e o RNA a timina.
III. O DNA é geralmente encontrado na natureza formando fita dupla enquanto que o RNA é mais comum em fita simples.

Podemos dizer que:

1. Apenas a afirmação I está correta.
2. Apenas a afirmação II está incorreta.
3. As afirmações II e III estão corretas.
4. Todas as afirmações estão corretas.
5. NDA

Autor: Rodrigo Ritter

004-2006

MO640 - Questão para a prova oral
Número: 004
Enunciado: O que podemos afirmar sobre os introns e os exons ?

1. Introns são trechos do DNA que nunca são transcritos, logo não codificam proteínas.
2. Introns são trechos do DNA que não codificam proteínas apesar de serem transcritos.
3. Exons são trechos do DNA que nunca são transcritos, logo não codificam proteínas.
4. Exons são trechos do DNA que não codificam proteínas apesar de serem transcritos.
5. NDA

Autor(a): Mirela Dal Col Silva

003-2006

MO640 - Questão para a prova oral
Número: 003
Enunciado:
Proteínas são moléculas essenciais para manter a estrutura e funcionamento de todos os organismos vivos e podem ter diferentes propriedades e funções. Por exemplo: as enzimas, a hemoglobina, certos hormônios e o colágeno dos ossos, tendões e pele são todos proteínas. Entre outras coisas, as proteínas regulam a contração muscular, produção de anticorpos, expansão e contração dos vasos sangüíneos para manter a pressão normal. A respeito de proteínas podemos afirmar que:

1. São formadas por uma cadeia de moléculas menores, denominadas bases.
2. Sua estrutura primária é composta por formas de hélices e folhas.
3. A seqüência de aminoácidos que formam uma proteína é chamada de estrutura primária desta proteína.
4. São o resultado do desdobramento de fitas que contém uma molécula de acuçar, fosfato e 4 carbonos.
5. NDA

Autor(a): Renato Cristiano Torres

002-2006

MO640 - Questão para a prova oral
Número: 002
Enunciado:
Qual afirmação acerca dos projetos EST está correta?

1. É impossível extrair qualquer informação sobre a funcionalidade de um novo gene identificado em um projeto EST, mesmo contando com as informações contidas em grandes bancos de EST, como o dbEST, devido ao ainda baixo grau de confiabilidade deste método;
2. Tanto os projetos EST quanto os projetos de sequenciamento de genomas completos sequenciam todos os genes, tanto os expressos quanto os não-expressos pelo organismo;
3. Todos os ESTs que correspondem a um mesmo gene são agrupados em um único grupo, já que de forma geral um EST não corresponde a um gene inteiro, mas a apenas parte dele. A isto se dá o nome de "clustering".
4. As técnicas utilizadas em projetos EST estão muito avançadas, de tal modo que não se visualiza, atualmente, qualquer desafio relevante nessa área.
5. NDA

Autor(a): Bruno Dilly

001-2006

MO640 - Questão para a prova oral
Número: 001
Enunciado:
Em que momento o splicing é realizado?

1. No momento em que os peptídeos se juntam para formar uma proteína.
2. No momento em que o RNA mensageiro "cria" os peptídeos.
3. Logo após o processo de transcrição, porém antes da formação do RNA mensageiro.
4. Antes de todo o processo de transcrição, ou seja, antes mesmo do gene a ser transcrito ser "escolhido".
5. NDA

Autor(a): Tiago Rinck Caveden

104-2005

MO640 - Questão para a prova oral
Número: 104
Enunciado:
Considerando os passos 1 e 2 do algoritmo de construção da árvore PQR do artigo Meidanis e Telles 2004, qual será a coloração de cada elemento da árvore, após a aplicação da restrição {f, g, j, k}?

 

1. brancos: n1, n2, n3, a, b, c, d, e, h, i
   cinzas: n6, n4
   pretos: n5, n7, f, g, j, k
   
2. brancos: n1, n2, n3, n4, a, b, c, d, e, h, i
   cinzas: nenhum
   pretos: n5, n6, n7, f, g, j, k
   
3. brancos: n1, n2, n3, n4, a, b, c, d, e, h, i
   cinzas: n6
   pretos: n5, n7, f, g, j, k
   
4. brancos: n2, n3, a, b, c, d, e, h, i
   cinzas: n1, n4, n6
   pretos: n5, n7, f, g, j, k
   
5. NDA

Autor(a): Renata Azzolini

103-2005

MO640 - Questão para a prova oral
Número: 103
Enunciado:
Com relação ao primeiro algoritmo para a construção de árvores PQR, descrito em On the consecutives ones property por Meidanis et al, qual passo do algoritmo não pode ser executado em tempo linear?

1. Encontrar um conjunto H não-trivial.
2. Decompor o problema em dois sub-problemas.
3. Juntar as árvores de cada sub-problema.
4. Testar se uma coleção prima é trivial.
5. NDA

Autor(a): Marcelo de Almeida Oliveira

102-2005

MO640 - Questão para a prova oral
Número: 102
Enunciado:
Com relação ao algoritmo para construção de árvores PQR, contido no artigo "Building PQR Trees in Almost-Linear Time" de Telles e Meidanis, a sequência correta de passos é (não necessariamente estão incluídos exatamente todos os passos):

1. achar LCA, colorir folhas correspondentes à restrição S, eliminar nós cinzas, ajustar LCA
2. colorir folhas correspondentes à restrição S, achar LCA, eliminar nós cinzas, ajustar LCA
3. achar LCA, ajustar LCA, colorir folhas correspondentes à restrição S, eliminar nós cinzas
4. colorir folhas correspondentes à restrição S, ajustar LCA, eliminar nós cinzas, achar LCA
5. NDA

Autor(a): Karina Zupo de Oliveira

101-2005

MO640 - Questão para a prova oral
Número: 101
Enunciado:
A repeito do algoritmo quase linear de construção de uma árvore PQR (Meidanis e Telles, 2004), assinale a alternativa INCORRETA:

1. É baseado na inserção de uma restrição por vez, utilizando como árvore inicial um único nó P que tem como filhos todos os elementos de U
2. Ao inserir uma restrição, encontra o nó que seja o ancestral comum mais próximo de todas as folhas envolvidas na restrição, e este nó é chamado de LCA
3. As folhas envolvidas pela restrição sempre são coloridas como pretas, e os nós intermediários da árvore são coloridos como cinzas caso sejam ortogonais à restrição em questão
4. Após a inserção de uma restrição, os nós que foram coloridos com a cor cinza devem ser eliminados por meio de uma reestruturação da árvore
5. NDA

Autor(a): Leonardo Elias Mariote

100-2005

MO640 - Questão para a prova oral
Número: 100
Enunciado:
A árvore PQR relativa ao universo U = {a, b, c, d, e, f, g, h, i, j} com o conjunto de restrições C = {abc, bcef, efg, ghi, ij} será constituída de:

1. 3 nós P, 1 nó Q e 1 nó R
2. 1 nó Q e 3 nós P
3. 3 nós P e 2 nós Q
4. 2 nós Q e 1 nó R
5. NDA

Autor(a): Patricia

099-2005

MO640 - Questão para a prova oral
Número: 099
Enunciado:
Dada uma coleção prima C, relacione o grafo binário gerado por C com o tipo de nó (P,Q ou R) correspondente.

1. P - caminho; Q - clique; R - grafo desconexo.
2. P - grafo desconexo; Q - caminho; R - clique.
3. P - caminho; Q - grafo desconexo; R - clique.
4. P - clique; Q - grafo desconexo; R - caminho.
5. NDA

Autor(a): Fernando Ferrari de Goes

098-2005

MO640 - Questão para a prova oral
Número: 098
Enunciado:
Num grafo qualquer, uma clique é um conjunto de vértices mutuamente adjacentes. Sobre grafos de intervalo, podemos afirmar que:

1. Todo grafo de intervalo é um grafo cordal, i.e., para todo ciclo de comprimento maior que 3, existe uma aresta conectando dois vértices não consecutivos desse ciclo.
2. Todo grafo de intervalo corresponde a um modelo de interseção, no qual os vértices representam intervalos e as arestas conectam intervalos disjuntos.
3. Um grafo é grafo de intervalo se sua matriz de cliques por vértices respeitam a propriedade de 1s consecutivos por coluna.
4. Um grafo pode ser verificado como sendo um grafo de intervalo com, no mínimo, complexidade quadrática em relação ao tamanho do grafo.
5. NDA

Autor(a): Fernando Ferrari de Goes

097-2005

MO640 - Questão para a prova oral
Número: 097
Enunciado:
Baseado no texto "On the consecutive ones property" de Meidanis et al., assinale a alternativa FALSA:

1. Três tipos de transformações de equivalência são permitidas em árvores PQR: permutações de filhos de um nó P, reversão de um nó Q e permutações de filhos de um nó R.
2. Duas árvores PQR são equivalentes quando uma pode ser transformada na outra aplicando zero ou mais transformações de equivalência.
3. Seja C um conjunto de restrições a serem respeitadas em um problema de C1P. Para encontrar a "completion" de C, três operações aplicadas repetidamente são suficientes: interseção, união não disjunta e diferença não contida.
4. Nos casos em que uma árvore PQ, estudada anteriormente, não puder ser construída a partir das restrições estabelecidas, uma árvore PQR poderá ser construída e conterá no mínimo um nó R.
5. NDA

Autor: César Morais Palomo

096-2005

MO640 - Questão para a prova oral
Número: 096
Enunciado:
De acordo com o artigo de Meidanis et al. (1997) sobre a propriedade de uns consecutivos (C1P), é INCORRETO afirmar que:

1. O problema de “ordem de dicionário” de Benzer corresponde a verificar se um grafo baseado nas relações de adjacência definidas é um grafo de intervalos.
2. Em bioinfomática, C1P pode ser aplicada na construção de mapas físicos por hibridização.
3. A propriedade de “uns consecutivos” só vale para matrizes quadradas.
4. Conjuntos triviais são ortogonais a qualquer outro conjunto.
5. NDA

Autor(a): Renato Hirata

095-2005

MO640 - Questão para a prova oral
Número: 095
Enunciado:
Dada a matriz abaixo, qual é o conjunto Universo(U) e quais são as restrições(S) para a construção de uma árvore PQ, que verifique a propriedade de uns consecutivos nas colunas da matriz?

	C1	C2	C3	C4	C5
L1	1	0	0	1	1
L2	0	1	1	1	1
L3	1	0	1	1	0

1. U = {C1, C2, C3, C4, C5}, S = {C1C4C5, C2C3C4C5, C1C3C4}
2. U = {C1, C2, C3, C4, C5}, S = {C2C3, C1, C2C5}
3. U = {L1, L2, L3}, S = {L1L3, L2, L2L3, L1L2L3, L1L2}
4. U = {L1, L2, L3}, S = {L2, L1L3, L1, L3}
5. NDA

Autor(a): Marcelo de Almeida Oliveira

094-2005

MO640 - Questão para a prova oral
Número: 094
Enunciado: Dado um conjunto de elementos U = {1, 2, 3, 4, 5, 6, 7} e uma seqüencia de restrições S₁={1, 3, 5, 7}, S₂={2, 4, 6} e S₃={1, 2, 5, 6}, qual a PQ-Tree resultante

A.

B.

C.

D.

E. NDA

Autor(a): Tony Minoru Tamura Lopes

093-2005

MO640 - Questão para a prova oral
Número: 093
Enunciado:
O que representam os 0's e 1's da matriz de recombinação citada no texto de Benzer? 

1. Indicam se o cruzamentro entre dois indivíduos mutantes pode produzir indivíduos padrão.
2. Indicam se o cruzamento entre um indivíduo padrão e um indivíduo mutante pode produzir indivíduos mutantes.
3. Indicam se pelo menos um descendente mutante dos indivíduos cruzados apresenta reversão.
4. Indicam se os indivíduos cruzados são recombinantes.
5. NDA
   

Autor(a): Caroline Campos Frossard

092-2005

MO640 - Questão para a prova oral
Número: 092
Enunciado:
De acordo com o artigo de Booth e Lueker sobre Árvores PQ (1976), é INCORRETO afirmar que:

1. Árvore PQ é uma estrutura de dados usada para representar as permutações de um conjunto U onde vários subconjuntos de U ocorrem consecutivamente.
2. São apresentados algoritmos para testar a planaridade de um grafo e a propriedade de “uns consecutivos” de uma matriz. Esses algoritmos utilizam árvore PQ e têm complexidade de tempo linear.
3. Em uma árvore PQ própria todos os nós “Q” têm pelo menos 3 filhos.
4. Uma matriz de “zeros e uns” tem a propriedade de “uns consecutivos” para colunas se suas colunas podem ser permutadas de forma que em cada linha todos os “uns” são consecutivos.
5. NDA

Autor(a): Renato Hirata

091-2005

MO640 - Questão para a prova oral
Número: 091
Enunciado:
Dada a árvore PQ abaixo, qual das alternativas não representa uma permutação válida?

1. DGFEBCA
2. EFGDBCA
3. ABCFEGD
4. ACBEFGD 
5. NDA

Autor: Alan Braz

090-2005

MO640 - Questão para a prova oral
Número: 090
Enunciado:
Segundo o artigo On the topology of the genetic fine structure de Seymour Benzer, sabemos que uma matriz está na ordem de dicionário se:

1. Em cada linha, temos um conjunto de zeros consecutivos, seguido por um conjunto de uns consecutivos.
2. Em cada coluna, temos um conjunto de zeros consecutivos, seguido por um conjunto de uns consecutivos.
3. A partir da diagonal, para a direita ou para baixo, temos um conjunto de zeros consecutivos, seguido de um conjunto de uns consecutivos.
4. A partir da diagonal, para a esquerda ou para cima, temos um conjunto de zeros consecutivos, seguido de um conjunto de uns consecutivos.
5. NDA

Autor(a): Marcelo de Almeida Oliveira

089-2005

MO640 - Questão para a prova oral
Número: 089
Enunciado: Não é problema resolvido através de estruturas de árvores PQ:

1. Reconhecer se um determinado grafo é ou não de intervalo.
2. Reconhecer se um determinado grafo é ou não cordal.
3. Numa matriz (0, 1) determinar se ela possui a propriedade de "1 consecutivos".
4. Reconhecer se um determinado grafo é ou não planar.
5. NDA

Autor(a): Karina Zupo de Oliveira

088-2005

MO640 - Questão para a prova oral
Número: 088
Enunciado:
Segundo a definição do artigo On the topology of genetic fine structure, Benzer (1959), qual das seguintes matrizes representa a matriz de recombinação dos mutantes abaixo:


1. a b c d e f g h i j k l
2. a b c d e f g h i j k l
3. a b c d e f g h i j k l
4. a b c d e f g h i j k l
5. a b c d e f g h i j k l
6. a b c d e f g h i j k l
7. a b c d e f g h i j k l
8. a b c d e f g h i j k l

(os elementos sublinhados são os elementos que sofreram alteração)

A. 1 2 3 4 5 6 7 8 1 0 1 1 1 1 1 1 1 2 0 0 0 1 1 1 0 0 3 0 0 1 1 1 0 0 1 4 1 0 0 0 1 1 1 0 5 1 1 1 1 0 0 0 1 6 0 0 0 0 0 0 0 0 7 1 1 1 1 0 0 0 1 8 0 1 0 1 0 1 0 1

B. 1 2 3 4 5 6 7 8 1 0 0 1 1 1 1 1 1 2 0 0 1 0 1 0 0 1 3 1 1 0 1 0 1 0 1 4 1 0 1 0 1 0 0 1 5 1 1 0 1 0 0 0 1 6 1 0 1 0 0 0 0 1 7 1 0 0 0 0 0 0 1 8 1 1 1 1 1 1 1 0

C. 1 2 3 4 5 6 7 8 1 0 0 1 1 1 1 1 2 2 0 0 1 0 1 0 0 1 3 1 1 0 1 0 1 0 1 4 1 0 1 1 1 0 0 1 5 1 1 0 1 0 0 0 1 6 1 0 1 0 0 0 0 1 7 1 0 0 0 0 0 0 1 8 1 1 1 1 1 1 1 2

D. 1 2 3 4 5 6 7 8 1 0 0 0 0 0 0 0 0 2 0 0 1 0 1 0 0 1 3 1 1 0 1 0 1 0 1 4 1 0 1 0 1 0 0 1 5 1 1 0 1 0 0 0 1 6 1 0 1 0 0 0 0 1 7 1 0 0 0 0 0 0 1 8 1 1 1 1 1 1 1 0

E. NDA

Autor(a): Renata Martinelli Azzolini