010-2011

MO640 - Questão para a Prova Oral

Enunciado:

Considere as seguintes sequências: s= AACT e t=GAGG. Se for aplicado algoritmo básico de alinhamento global para estas sequências com pesos de match = 1, mismatch = -1 e gap = -2, quais seriam os valores da última linha e da última coluna da matriz?

a. linha: -8,-7,-3,-2,-1 ; coluna: -8,-5,-4,-3,-2

b. linha: -8,-7,-3,-2,-1 ; coluna: -8,-5,-3,-2,-1

c. linha: -8,-7,-4,-3,-2 ; coluna: -8,-5,-4,-3,-2

d. linha: -8,-7,-4,-3,-1 ; coluna: -8,-5,-3,-2,-1

e. NDA

 
Ideia original de: Wilson Vendramel

009-2011

Escolha a alternativa que indica a similaridade correta entre as seguintes sequências.  Considere similaridades calculadas por dois tipos de algoritmo: o de comparação global e o de comparação local.

 

ATGATTACATCGTA

ACTACGATTACACA

(Use: match = +1 ; mismatch = -1 ; gap = -2;)

1. A similaridade Local é 2
2. A similaridade Local é 7
3. A similaridade Global é 2
4. A similaridade Global é 7
5. NDA

Ideia original de: Felipe Holanda

036-2008

MO640 - Questão para a prova oral
Número: 036
Enunciado:
Considerando os vários algoritmos de comparação global, semi-global e local vistos em aula, que diferença NÃO existe entre eles?

1. Inicialização da matriz
2. Complexidade de pior caso do algoritmo
3. Penalização para casamentos com espaços
4. Posição em que é procurado o maior valor
5. NDA

Autor(a): Priscila do Nascimento Biller

035-2008

MO640 - Questão para a prova oral
Número: 035
Enunciado:
Qual das modificações abaixo não precisa ser feita para transformar o algoritmo de alinhamento global no algoritmo de alinhamento local?

1. Iniciar com zero a primeira coluna e a primeira linha da matriz.
2. Parar a reconstrução de um alinhamento local quando for encontrado um 0 na matriz.
3. Não deixar que os valores da matriz fiquem negativos; se o máximo se revelar negativo, deve ser substituído por 0. 
4. Procurar o maior valor da matriz inteira, para obter a similaridade e para utilizar como ponto de partida para reconstrução de um alinhamento ótimo.
5. NDA

Autor(a): Filipe Benevides Netto

033-2008

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

	0	A	G	T
0	0	-2	-4	-6
C	-2	0	X	-4
G	Y	-2	1	-1
T	-6	-4	-1	Z

Considere a tabela de similaridade global acima, com pesos de match = 1, mismatch = 0 e gap = -2. Indique a opção abaixo que representa os valores corretos de X, Y e Z (respectivamente) da tabela:

1. -1; -3; 0.
2. -1; -3; 2.
3. -2; -4; 0.
4. -2; -4; 2.
5. NDA

Autor(a): Fabio L. Usberti

030-2008

MO640 - Questão para a prova oral
Número: 030
Enunciado:
Uma diferença entre a reconstrução de um alinhamento local e outro global é:

1. A reconstrução local é encerrada quando encontra-se o valor zero, enquanto que a global segue até o elemento [0,0].
2. A reconstrução local é encerrada quando atinge uma borda inicializada com zeros, enquanto que a global segue até o elemento [0,0].
3. A reconstrução local inicia-se apenas no elemento mais abaixo e à direita, enquanto que a global pode iniciar-se em qualquer elemento.
4. A reconstrução local segue até o elemento [0,0], enquanto que a global somente se encerra quando atinge uma borda inicializada com zeros.
5. NDA

Ideia original de: Beto Marchesini

029-2008

MO640 - Questão para a prova oral
Número: 029
Enunciado:
Considere as seguintes afirmações:
I- Ponto de partida para alinhamento é o maior valor da última linha da matriz
II- Similaridade refere-se ao maior valor encontrado na matriz de similaridade
III- A primeira linha da matriz, apenas, é preenchida com zeros.
Elas referem-se respectivamente a quais alinhamentos:

1. global, local, semi-local não penalizando buracos no início da primeira seqüência.
2. semi-global não penalizando buracos no fim da primeira seqüência, local, semi-local não penalizando buracos no início da primeira seqüência.
3. semi-global não penalizando buracos no início da primeira seqüência, local, semi-local não penalizando buracos no fim da primeira seqüência.
4. semi-global não penalizando buracos no início da primeira seqüência, semi-local não penalizando buracos no início da segunda seqüência, local.
5. NDA

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

025-2008

MO640 - Questão para a prova oral

Número: 025
Enunciado:
Considerando seqüêrncias de entrada de tamanhos m e n, o que podemos dizer sobre a complexidade dos algoritmos de Similarity e Align do texto lido. Escolha somente uma opção:

1. A complexidade do Align é O(n).
2. A complexidade do Align é O(m + n).
3. A complexidade dos dois algoritmos acima é O(m³n).
4. Não há como calcular a complexidade se as seqüências possuirem tamanhos diferentes.
5. NDA
   

Ideia original de: Andréia G. Motta Maia

024-2008

MO640 - Questão para a prova oral
Número: 024
Enunciado:
Considere duas strings s1[1..m] e s2[1..n] para serem alinhadas e a matriz de similaridade a[i,j] definida por elas, onde 0 ≤ i ≤ m e 0 ≤ j ≤ n. Sobre a matriz de similaridade é correto afirmar que:

1. Os elementos a[i,0] para 0 ≤ i ≤ m são sempre múltiplos de -2.
2. cada elemento a[i,j] da matriz de similiaridade deve conter o peso g entre os caracteres s1[i] e s2[j].
3. O elemento a[i,j] da matriz de similiaridade deve conter a similaridade entre os caracteres s1[i] e s2[j].
4. O elemento a[i,j] da matriz de similaridade deve conter a similaridade entre as strings s1[1..i] e s2[1..j].
5. NDA

Autor(a): Gustavo Waku

022-2008

MO640 - Questão para a prova oral
Número: 022
Enunciado:
Existem vários métodos para comparar duas sequências de DNA. Um deles é o método da comparação global. De qual técnica esse método faz uso e qual a sua complexidade ? (n é o tamanho da primeira sequência de DNA e m é o tamanho da segunda)

1. Programação Gulosa, O(n+m)
2. Programação Inteira, O(n*m)
3. Programação Dinâmica, O(n*m)
4. Programação Funcional, O(n+m)
5. NDA

Autor(a): Bruno Conti Marini

021-2008

MO640 - Questão para a prova oral
Número: 021
Enunciado:
Sobre o algoritmo para o cálculo da similaridade global, é correto afirmar que:

1. Para o cálculo de sim[i,j] é apenas necessário o valor de sim[i-1,j].
2. Para o cálculo de sim[i,j] é apenas necessário o valor de sim[i,j-1].
3. Para o cálculo de sim[i,j] são apenas necessários os valores de sim[i-1,j] e sim[i,j-1].
4. Para o cálculo de sim[i,j] são apenas necessários os valores de sim[i-1,j], sim[i,j-1] e sim[i-1,j-1].
5. NDA

Autor(a): Beto Marchesini

020-2008

MO640 - Questão para a prova oral
Número: 020
Enunciado:
Qual destas afirmações sobre alinhamentos de sequências é falsa?

1. Espaços podem ser inseridos no começo de sequências.
2. Podem existir alinhamentos entre sequências de tamanhos distintos.
3. O número de alinhamentos que existe entre duas sequências é exponencial.
4. Um espaço de uma sequência pode ser alinhado com um espaço de outra sequência.
5. NDA

Autor: Felipe Augusto Archangelo

018-2008

MO640 - Questão para a prova oral

Número: 018
Enunciado:
Dadas as seqüências s e t, de tamanho m e n, respectivamente, qual é a complexidade de tempo do algoritmo básico de comparação global?

1. O(mn)
2. O(m + n)
3. O((mn)²)
4. O((m + n)²)
5. NDA

Autor(a): João Paulo Pereira Zanetti

013-2007

MO640 - Questão para a prova oral
Número: 013
Enunciado: Sejam P, G e L algoritmos estudados em classe para efetuar alinhamentos pontas livres, global e local, respectivamente. Considerando as afirmações a seguir, indique a alternativa que as relaciona adequadamente a esses algoritmos.
I) Possuem relações de recorrência iguais na recursão.
II) Possuem condições-base iguais na recursão.
III) Podem ser implementados com complexidade de tempo O(nm), onde n e m são os tamanhos das seqüências a serem alinhadas.
IV) Podem ser implementados com complexidade linear de espaço.

1. I: LP; II: GP; III: LP; IV: GL.
2. I: GL; II: GLP; III: GP; IV: GLP.
3. I: GP; II: LP; III: GLP; IV: GLP.
4. I: GLP; II: GL; III: GL; IV: LP.
5. NDA

Autor(a): Celmar Guimarães da Silva

011-2007

MO640 - Questão para a prova oral
Número: 011
Enunciado:
Em relacão ao Alinhamento Global Ótimo, é incorreto afirmar :

1. Para sequências suficientemente similares, não resultará diferente do Alinhamento Local Ótimo.
2. Uma solucão ótima pode ser encontrada em tempo linear usando programacão dinâmica.
3. Cada sequência envolvida é considerada na sua totalidade.
4. São inseridos "gaps" nas sequências para eliminar diferencas nos tamanhos delas.
5. NDA

Autor(a): Luis Felipe Strano Moraes

010-2007

MO640 - Questão para a prova oral
Nmero: 010
Enunciado:
Assinale a seqüência cujo melhor alinhamento global com CGCTATCG tem pontuação igual a 0. (Match = 1, Mismatch = -1 e Gap = -2)

1. CCGCTCGGG
2. GACTTAGG
3. CGTCACG
4. CGTCG
5. NDA

Autor(a): Lucas Pedersen Parizzi

009-2007

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

Enunciado:
Dadas as seqüencias S = ACAGTTCTT e P = ATGATT, escolha a alternativa que melhor representa a pontuação do alinhamento global e local, respectivamente. (match = 2, mismatch = -1 e gap = -1)

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

Autor(a): Andrey Seiji Shimada

039-2005

MO640 - Questão para a prova oral
Número: 039
Enunciado:
Sejam s e t duas sequencias, e sejam i, j posições nas seqüências s e t, respectivamente. Qual das opções a seguir não fornece um alinhamento entre s[1..i] e t[1..j]:

1. Alinhar s[1..i] com t[1..j-1] e alinhar um espaco com t[j]
2. Alinhar s[1..i-1] com t[1..j-1] e alinhar s[i] com t[j]
3. Alinhar s[1..i-1] com t[1..j-1] e alinhar um espaco com t[j]
4. Alinhar s[1..i-1] com t[1..j] e alinhar s[i] com um espaco
5. NDA

Autor: César Morais Palomo

037-2005

MO640 - Questão para a prova oral
Número: 037
Enunciado:
Considerando o alinhamento abaixo, qual sistema de pontuação resultará em uma maior pontuação?

AT-CAGGAG-G-

GAACTGGCGTAT

1. p(a,b) = 2 se a = b, p(a,b) = -2 se a<> b, e g = -3
2. p(a,b) = 1 se a = b, p(a,b) = -1 se a<> b, e g = -1
3. p(a,b) = 1 se a = b, p(a,b) = -1 se a<> b, e g = -2
4. p(a,b) = 2 se a = b, p(a,b) = -1 se a<> b, e g = -1
5. NDA
   

Autor(a): Alan Braz

036-2005

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

Enunciado:

Sobre comparação de seqüências é incorreto afirmar que:

1. Comparação de seqüências é operação primitiva mais importante na biologia computacional, servindo de base para outras operações mais complexas.
2. Um alinhamento local entre s e t é um alinhamento entre uma substring de s e uma substring de t.
3. Programação Dinâmica é uma técnica bastante utilizada para se resolver eficientemente problemas de comparação de seqüências.
4. Na comparação global de seqüências, a matriz utilizada para o cálculo de alinhamentos ótimos deve possuir a primeira linha e primeira coluna com valores iguais a -1.
5. nda     

Autor(a): Renato Hirata