MO640 - Prova Individual 1 - Solução

Enunciado distribuido na sala.

  1. (Valor 2,0)
    1. Quais são as diferenças entre moléculas de DNA e RNA?
    2. Explique o papel de cada um dos seguintes tipos de RNA na síntese de proteínas:

      mRNA, tRNA, rRNA

    Solução:

    1. DNA tem desoxirribose como açúcar, RNA tem ribose; DNA tem timina, RNA tem uracila; DNA é estável apenas como fita dupla, RNA pode assumir uma grande variedade de formas tridimensionais.
    2. mRNA é o mensageiro, cópia de uma das fitas do gene que após splicing sai do núcleo; tRNA é o transportador, que numa ponta carrega um amino ácido e na outra tem um anti-codon; rRNA é o ribossomal, que juntamente com várias proteínas compõe a estrutura chamada de ribossomo.
  2. (Valor 2,0)  Seja G = (V,E) um grafo orientado acíclico de n vértices tal que se ignorarmos as orientações das arestas teremos um grafo completo.  Descreva e analise a complexidade computacional de um algoritmo que construa um vetor a[1..n] tal que:

    Procure obter o algoritmo mais eficiente que você conseguir.

    Obs: Tal vetor será uma ordenação topológica de G.

    Solução:

    Basta fazer uma busca em profundidade, colocando os vértices no vetor a conforme a busca os deixa:

    Algoritmo:
    inicialize com todos os vértices desmarcados
    i ← n
    escolha um vértice qualquer v
    dfs(v)

    Procedimento dfs(v):
    marque v
    para todo u não marcado tal que v → u faça
        dfs(u)
    a[i] ← v
    i ← i - 1

    Este algoritmo tem complexidade linear O(|V|+|E|).

  3. (Valor 2,0) Considere as seguintes seqüências de DNA, sendo a primeira ancestral e a segunda descendente:

    TAATCCAGCCATTTATACCCGCATTACTAG
    TAAGCTAGCCATTTATATCCACATTACTAG

    1. Obtenha as taxas observadas de transições e transversões por posição.
    2. Obtenha as taxas estimadas de transições e transversões por posição segundo o modelo de dois parâmetros de Kimura.

    Obs.: (são dadas as equações de Kimura).

    Solução:

    1. Taxa observada de transições: Y = 3/30 = 0,1
      Taxa observada de transversões: 2Z = 1/30 = 0,033333...
    2. Taxa estimada de transição (por Kimura): ut = -(1/2)*ln(1 - 2Y - 2Z) - vt = 0,115603
      Taxa estimada de transversão (por Kimura): 2vt = -(1/2)*ln(1 - 2*(2Z)) = 0,034496
  4. (Valor 4,0) Considere as seqüências de DNA abaixo:

    CGAGCC, TAGG

    Preencha a matriz de programação dinâmica e obtenha a similaridade global entre estas seqüências, usando match=1, mismatch=-1, space=-2.  A seguir, marque na matriz um caminho ótimo e produza o alinhamento correspondente a este caminho.

    Solução:
    		T
    		 A
    		 G
    		 G

    		0
    		 -2
    		 -4
    		 -6
    		 -8
    C
    		 -2
    		 -1
    		 -3
    		 -5
    		 -7
    G
    		 -4
    		 -3
    		 -2
    		 -2
    		 -4
    A
    		 -6
    		 -5
    		 -2
    		 -3
    		 -3
    G
    		 -8
    		 -7
    		 -4
    		 -1
    		 -2
    C
    		 -10
    		 -9
    		 -6
    		 -3
    		 -2
    C
    		 -12
    		 -11
    		 -8
    		 -5
    		 -4

    Um caminho ótimo está marcado na tabela.  Seu alinhamento correspondente:

    CGAGCC
    -TAG-G

MO640 Home

© 2004 João Meidanis