Jump to content
thoga31

As Proteínas

Recommended Posts

thoga31

Título: As Proteínas

Descrição introdutória:

Isto vai ser muito texto, mas o objectivo é muito simples. Deixem-me só dar-vos uma ideia geral da utilidade prática deste desafio :)

Uma proteína é um conjunto de aminoácidos (aa) ligados entre si através de ligações peptídicas, sendo as suas pontas denominadas de "C-terminal" (grupo carboxílico) e "N-terminal" (grupo amina).

Consoante o número e a ordem dos aa, a proteína ganha uma conformação específica através das interacções de forças fracas entre estes mesmos aa, o que lhe confere actividade biológica.

Determinar quantos e quais são os aa de uma proteína não é um trabalho fácil - recorre-se geralmente à hidrólise ácida -, mas comparativamente com a sua sequenciação pode-se dizer que é uma brincadeira de miúdos.

Sequenciar a proteína significa não só saber quantos e quais são os aa: significa saber a sua ordem exacta de uma ponta à outra.

A Degradação de Edman permite fazer isto de uma forma teoricamente simples (na prática é uma bonito exercício de muitas horas): retiramos um aa, analisamos qual é, retiramos outro e determinados qual é, e assim sucessivamente. Mas esta técnica tem uma margem de erro que só é aceitável se o peptídeo tiver, no máximo, 50 aa.

Para isso existem químicos que clivam a proteína em aminoácidos específicos, dando-nos "pedacinhos" da proteína. Pelo menos duas "separações" ocorrem em paralelo para garantir a posterior montagem do "puzzle" que nos fica reservado.

Tendo estas (pelo menos) duas sequenciações em "pedaços", resta-nos sobrepô-las para determinar a ordem correcta dos aminoácidos e descobrir, por fim, a composição da proteína.

Exemplo:

Por hidrólise ácida determinou-se que uma certa proteína tem os seguintes aa:

  • A = 5
  • C = 2
  • D = 4
  • E = 2
  • F = 1
  • G = 3
  • H = 2
  • I = 3
  • K = 2
  • L = 2
  • M = 2
  • P = 3
  • R = 1
  • S = 2
  • T = 1
  • V = 1
  • Y = 2

A proteína tem 38 aa. Utilizou-se 2 químicos para clivar a proteína em 3 aminoácidos específicos: K, M e R.

Nota: cada químico é utilizado em tubos de ensaio distintos com a mesma solução da proteína.

Para o químico Tripsina ( T ) obteve-se 4 sequências:

  • T-1 = GASMALIK
  • T-2 = EGAAYHDFEPIDPR
  • T-3 = DCVHSD
  • T-4 = YLIACGPMTK

Para o químico Brometo de Cianogénio ( C ) obteve-se 3 sequências:

  • C-1 = EGAAYHDFEPIDPRGASM
  • C-2 = TKDCVHSD
  • C-3 = ALIKYLIACGPM

Sabe-se que o N-terminal é um E (glucose).

Nota: não confundir as letras T e C dos químicos com as letras T e C dos aminoácidos. São coisas distintas!

A junção lógica destas 7 sequências provenientes das clivagens dos dois químicos deu o seguinte resultado:

proteinas_01.png

Objectivo:

Dado o resíduo do N-terminal, o número de químicos utilizados para clivar a proteína e dadas as sequências respectivas obtidas, mostrar a sequência da proteína, explicitando os N e C-terminais.

Exemplo de I/O:

Segundo este exemplo infra-apresentado (entre "/* */" estão comentários explicativos):

- Input:

E               /* informa qual o resíduo do N-terminal */
2               /* número de químicos utilizados para clivagem */
4               /* número de sequências obtidas com o 1º químico */
GASMALIK        /* as 4 sequências... */
EGAAYHDFEPIDPR
DCVHSD
YLIACGPMTK
3                   /* número de sequências obtidas com o 2º químico */
EGAAYHDFEPIDPRGASM  /* as 3 sequências... */
TKDCVHSD
ALIKYLIACGPM

- Output:

(N-terminal) EGAAYHDFEPIDPRGASMALIKYLIACGPMTKDCVHSD (C-terminal)

Restrições:

As letras que não representam aminoácidos não devem ser aceites no input:

BJOUXZ

Linguagens admitidas:

Qualquer uma.

Divirtam-se ;)


Knowledge is free!

Share this post


Link to post
Share on other sites
HappyHippyHippo

só uma questão

então o N-terminal não é mais do que o caracter inicial da cadeia final, certo ?


IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites
thoga31

só uma questão

então o N-terminal não é mais do que o caracter inicial da cadeia final, certo ?

Em termos biológicos, o N-terminal é o aminoácido cujo grupo amina está livre (numa das pontas da proteína) (por convenção é onde a proteína começa).

Por isso sim, é um só aa. ;)

Edited by thoga31

Knowledge is free!

Share this post


Link to post
Share on other sites
mjamado

Duas questões:

1. Tens mais inputs? É que uma solução pode resolver este input concreto, mas depois falhar noutros...

2. É suposto haver uma soluções mais eficazes do que qualquer coisa tipo O(n^2)?


"Para desenhar um website, não tenho que saber distinguir server-side de client-side" - um membro do fórum que se auto-intitula webdesigner. Temo pelo futuro da web.

Share this post


Link to post
Share on other sites
thoga31

1. Tens mais inputs? É que uma solução pode resolver este input concreto, mas depois falhar noutros...

Só tenho aqui "à mão" (algures xD) mais 2 exemplos muito específicos e pequenos, e que nem utilizam a numeclatura de letras mas sim de 3 letras: em vez de "E" escrevemos "Glu". Deixa-mos encontrar e já os coloco segundo as "normas" do desafio :)

2. É suposto haver uma soluções mais eficazes do que qualquer coisa tipo O(n^2)?

Para inputs pequenos, a eficiência não importa muito. Mas como gostaria de dar um lado prático e útil a este desafio - as grandes proteínas têm mais de 1000 aminoácidos e são utilizados pelo menos 4-5 químicos - a eficiência poderá vir a ser útil.

Mas deixo isso ao critério de cada um. Após horas de trabalho a obter os dados, alguns segundos a mais ou a menos para obter o puzzle resolvido não fazem diferença, garanto :P

Edited by thoga31

Knowledge is free!

Share this post


Link to post
Share on other sites
pedrosorio

Duas questões:

1. Tens mais inputs? É que uma solução pode resolver este input concreto, mas depois falhar noutros...

2. É suposto haver uma soluções mais eficazes do que qualquer coisa tipo O(n^2)?

1. De facto era interessante ter mais inputs mas repara que podes gerá-los tu facilmente.

2. Sim.

Spoiler:

O(n) usando Euler paths num de Brujin graph dos fragmentos para obter o alinhamento das sequências.

P.S.: Isto é muito relevante para alinhamento de sequências de ADN que são enormes, para o caso de proteínas a eficiência computacional do algoritmo não é tão crítica.


Não respondo a dúvidas por mensagem.

Share this post


Link to post
Share on other sites
thoga31

Exemplo 2:

A
2
2
AGS
AH
2
AA
AHG

AAHGS

Exemplo 3:

D
2
3
AGSQ
KWRP
QHK
2
DAG
GSQ

DAGSQHKWRP

Acho que não me enganei :)

P.S.: Isto é muito relevante para alinhamento de sequências de ADN que são enormes, para o caso de proteínas a eficiência computacional do algoritmo não é tão crítica.

Sim, para o DNA a eficiência é crítica. São mais de 200 milhões de pb's (se não me falha a memória).


Knowledge is free!

Share this post


Link to post
Share on other sites
thoga31

Script para gerar proteínas e sequenciações (feito à pressa, mas funciona minimamente):

# Python 3.x

# Gera lista de aa
aa = [chr(c) for c in range(ord('A'), ord('Z') + 1) if chr(c) not in 'BJOUXZ']
proteina = ''
import random

# Cria proteina
for i in range(100):
   proteina += random.choice(aa)

# Sequencia proteina (totalmente aleatorio, sem caracter cientifico)
sequencia = []
for vezes in range(2, random.randint(2, 11)):
   seq = []
   li, ls = 0, 0
   while ls < len(proteina):
       li = ls
       while ls - li > 30 or ls - li == 0:
           ls = random.randint(li + 1, len(proteina))
       seq.append(proteina[li:ls])
   sequencia.append(seq)

# Gera o input do desafio
print(sequencia[0][0][0])
print(len(sequencia))
for s1 in sequencia:
   print(len(s1))
   for s2 in s1:
       print(s2)

Exemplo 4, gerado pelo script:

G
6
6
GYNASVHLKDHHFKEHKSHENFN
SHTIQMIKWHWYSAQ
NVQTDFKTYLFWMYTWHLWTVRMWWH
PA
HEVNQYQNSVAMYRQHMGIHEYDIHRWDGC
GMVI
6
GYNASVHLKDH
HFKEHKSHENFNSHTIQMIKWHWYSAQNVQ
TDFKTYLFWMYTWHLWTVRMWWHPA
HEVNQYQNSVAMYRQHMGIHEY
DIHRWDGC
GMVI
11
GYNA
SVHLKDHHFKEHKSHENFNS
HTIQMIKWHWYS
A
Q
NVQTDFKTYLFWMYTWHLWTV
RMWWHPAHEVNQYQNSVAMYRQHMGIH
EYDIHRWDGC
GM
V
I
5
GYNASVHLKDHHFKEHKSHENFNSHTIQMI
KWHWYSAQNVQTDFKTYLFWMYT
WHLWTVRMWWHPAHE
VNQYQNSVAMYRQHMGIHEYDIHRWDG
CGMVI
6
GYNASVHLKDHHFKEHKSHENFNS
HTIQMIKWHWYS
AQNVQTDFKTYLFWMYTWHLWTVRMW
WHPAHEVNQYQNSVAMYRQHMGIHE
YDI
HRWDGCGMVI
9
GYNAS
VHLKDHH
FKEHKSHENFN
SHTIQMIKWHWYSAQN
VQTDFKTYLFWMYTWHLWTVRMWWHPA
HEVNQY
QNSVAMYRQHMGIHEYDIHRW
DGCGMV
I

GYNASVHLKDHHFKEHKSHENFNSHTIQMIKWHWYSAQNVQTDFKTYLFWMYTWHLWTVRMWWHPAHEVNQYQNSVAMYRQHMGIHEYDIHRWDGCGMVI

Há sequências que, na realidade, podem ter 1 só aminoácido! Não é um "inédito" do script ;)

EDIT: a executar aqui: http://ideone.com/atjyI

Edited by thoga31

Knowledge is free!

Share this post


Link to post
Share on other sites
taviroquai

Não percebi nada do problema...

Só percebi a seguinte imagem:

proteinas_01.png

... ou seja das sequências do 1º químico pode-se achar sequências para o segundo químico... o resto é chinês :D

Share this post


Link to post
Share on other sites
pedrosorio

Não percebi nada do problema...

Se esqueceres o significado bioquíomico (i.e. as proteínas) resume-se a isto:

Existe uma string original, S. Um processo que pode ser realizado é dividir S em strings mais curtas que quando colocadas por ordem permitem obter a string original. Aquilo que recebes como input é:

-> O primeiro caracter da string S;

-> Quantas vezes realizámos o processo de dividir a string S em strings mais curtas;

-> Para cada processo realizado:

-> O número de strings mais curtas obtido

-> Cada uma dessas strings (mas não necessariamente pela ordem que apareciam em S)

Com esta informação deves conseguir devolver a string original S.


Não respondo a dúvidas por mensagem.

Share this post


Link to post
Share on other sites
thoga31

Não percebi nada do problema...

Só percebi a seguinte imagem: [...]

... ou seja das sequências do 1º químico pode-se achar sequências para o segundo químico... o resto é chinês :D

O @pedrosorio já explicou em termos de programação.

Mas em termos científicos, sem ofensa, nem a imagem entendeste. :P

Vamos lá ver se consigo explicar um pouco melhor... Para isso, esquece tudo o que "entendeste" até agora :)

Tens uma proteína, desconhecida, que é composta por uma sequência de aminoácidos, e queres sequenciá-la, ou seja, saber quais são esse aminoácidos por ordem.

Devido às limitações da técnica utilizada, tens de dividir a proteína em pedacinhos (utilizando um químico), e sequenciar um pedaço de cada vez. O problema é que, mesmo com os pedaços sequenciados, não sabes a ordem original deles!

Solução: por exemplo, pegas em 3 químicos diferentes, colocas uma mesma solução da proteína em 3 tubos de ensaio diferentes, metes cada químico em cada tubo, e sequencias os pedaços de cada tubo.

Vais obter 3 conjuntos de sequências. O objectivo é descobrir, com estes 3 conjuntos, a ordem original da proteína.

Exemplo:

Tens uma proteína e descobriste que tem 33 aminoácidos, sabes quais são e quantos são. Mas qual a sua ordem?

Fazes uma solução da proteína e colocas em 2 tubos de ensaio distintos. Num tubo metes um químico e noutro metes o outro químico. Isto faz com que a proteína se divida em pedaços. Entre cada tubo, os pedaços são diferentes porque cada químico cliva a proteína em sítios diferentes.

Sequências os pedaços do tubo nº 1:

GASMALIK
EGAAYHDFEPIDPR
DCVHSD
YLIACGPMTK

Sequências os pedaços do tubo nº 2:

EGAAYHDFEPIDPRGASM
TKDCVHSD
ALIKYLIACGPM

E agora, que tens estes dados, qual a ordem original da proteína?

O método utilizado à mão é eficaz para proteínas pequenas, mas é impraticável para proteínas enormes (1000+ aminoácidos), e este é simplesmente ir somando os pedaços de ambos os conjuntos... pura matemática, mas com uma "sopa de letras", ora vê:

EGAAYHDFEPIDPRGASM
EGAAYHDFEPIDPR
             GASMALIK
                 ALIKYLIACGPM
                     YLIACGPMTK
                             TKDCVHSD
                               DCVHSD
______________________________________
EGAAYHDFEPIDPRGASMALIKYLIACGPMTKDCVHSD

Como estás a ver, peguei em TODAS as sequências que tinhas dos 2 conjuntos de pedaços e comecei a somá-las. Como a proteína foi clivada em sítios diferentes, há pedaços que terminam com um conjunto igual ao início de outro pedaço, e assim por diante...

E assim, já entendes o nosso trabalho em laboratório? (e nas frequências :D )


Knowledge is free!

Share this post


Link to post
Share on other sites
thoga31

Parece que este desafio não cativou ninguém... :confused:

Bem, eu tentei resolver isto num quarto d'hora antes de ir dormir, e esta solução resolve alguns, dá erro noutros, e ainda há outros que saem um pouco mais curtos do que o esperado.

Pretendo estudar quando tiver tempo o que está a funcionar mal, mas o princípio está cá...

# Python 3.x

def long_substr(data):
   substr = ''
   if len(data) > 1 and len(data[0]) > 0:
       for i in range(len(data[0])):
           for j in range(len(data[0])-i+1):
               if j > len(substr) and all(data[0][i:i+j] in x for x in data):
                   substr = data[0][i:i+j]
   return substr

def proximo(actual, tamanho):
   return 0 if actual == tamanho else actual + 1

if __name__ == "__main__":
   n_terminal = input()
   n_quimicos = int(input())
   seqs = []
   for i in range(n_quimicos):
       n_seq = int(input())
       seq_temp = []
       for j in range(n_seq):
           seq_temp.append(input())
       seqs.append(seq_temp)

   x, y = 0, 0
   seq_final = seqs[0][0]
   del seqs[0][0]

   while sum([len(s) for s in seqs]) > 0:
       comum = long_substr([seq_final, seqs[x][y]])
       if seqs[x][y].startswith(comum):
           if seqs[x][y] not in seq_final:
               seq_final = seq_final[:seq_final.index(comum)] + seqs[x][y][seqs[x][y].index(comum):]
           del seqs[x][y]
           x = proximo(x, len(seqs) - 1)
           y = 0
           continue
       elif seqs[x][y].endswith(comum):
           if seqs[x][y] not in seq_final:
               seq_final = seqs[x][y][:seqs[x][y].index(comum)] + seq_final[seq_final.index(comum):]
           del seqs[x][y]
           x = proximo(x, len(seqs) - 1)
           y = 0
           continue
       else:
           y = proximo(y, len(seqs[x]) - 1)
           if y == 0:
               x = proximo(x, len(seqs) - 1)

   if seq_final[0] == n_terminal:
       seq_final = '(N-terminal) ' + seq_final + ' (C-terminal)'
   else:
       seq_final = '(C-terminal) ' + seq_final + ' (N-terminal)'
   print(seq_final)
   input()  # pausa windows


Knowledge is free!

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.