Portefolio_original.ipynb

{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "# Portefólio-Grupo 3\n",
        "\n",
        "- Afonso Sá pg(54434)\n",
        "- Duarte Velho pg(53481)\n",
        "- Ricardo Oliveira pg(53501)\n",
        "- Samuel Baptista pg(49130)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "y3M80NpQfegz"
      },
      "source": [
        "<!-- LTeX: language=pt -->\n",
        "\n",
        "## Tarefa 1- Métodos de strings\n",
        "\n",
        "<div align='justify'>\n",
        "Nesta primeira semana, vamos abordar alguns métodos que podem ser utilizados com strings, métodos que são bastante uteis quando é ncessário ao longo do codigo trabalhar com variaveis em formato string. Com o intuito de apresentar 3 métodos de strings, procedemos à criação de uma função que calcule o conteudo GC, em percentagem, numa cadeia de DNA.\n",
        "\n",
        "A função gc_content recebe como argumento uma sequência de nucleoticos em formato string e devolve um float que corresponde ao conteúdo de guaninas e citosinas, em percentagem, da sequência. Nesta função utilizaram-se métodos de strings de modo a trata a sequência fornecida com o intuito de padronizar a cadeia e permitir a contagem de \"C\" e \"G\". O método upper() garante que todos os caracteres fornecidos estão em letra maiúscula, enquanto o método strip () remove possíveis espaços em branco que possam ter sido inseridos nas extremidades da cadeia, o que levaria a erros no cálculo do conteudo CG. Este método apresenta um parâmetro opcional onde se pode forncer, em formato de string, os caracteres que se pretende eliminar, sendo que, por padrão, o método remove espaços em branco. Por fim, aplicou-se o método replace() de modo a garantir que a cadeia não possui espaços no seu interior. O método replace() apresenta 3 parâmetros, sendo 2 deles obrigatórios. O primeiro parâmetro corresponde ao caracter antigo que se pretende substituir, o segundo parâmetro diz respeito ao caracter que irá substituir o antigo e, por fim, o último parâmetro especifica quantas ocorrências do caracter antigo se pretendem substituir, por padrão ocorre a substituição de todas as ocorrências.<br>\n",
        "Para se realizar a contagem das bases de interesse usou-se o método count(), que possui 3 parâmetros. O primeiro parâmetro é obrigatório e corresponde ao caracter que se pretende realizar a contagem. O segundo (opcional) corresponde a um valor inteiro que indica a partir de que posição da string se pretende iniciar a contagem, definido por padrão definido como 0. Por fim, o último parâmetro (opcional) é um valor inteiro que vai indicar a posição do local na string onde se vai terminar a contagem, por padrão, está definido para terminar no fim da string.<br>\n",
        "\n",
        "A função valid_strand verifica se a cadeia de nucleotidos fornecida recebe como argumento uma cadeia de DNA ou RNA  valida devolvendo um booleano que será True se a cadeia for válida. Para verificar a validade da cadeia aplica-se os métodos strip(), upper() e replace dos caracteres A, C, G, T e ' ' por uma string vazia (''). Se a cadeia fornecida for válida é esperado que após a aplicação destes métodos se obtenha uma string vazia no final."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 77,
      "metadata": {
        "id": "EW7p49Avq1zn"
      },
      "outputs": [],
      "source": [
        "def gc_content(DNA : str) -> float:\n",
        "  '''\n",
        "  Função que recebe uma cadeia de DNA e calcula o teor de GC da cadeia\n",
        "  \n",
        "  Parameters\n",
        "  -----\n",
        "  DNA:str\n",
        "    cadeia de DNA na qual se pretende determinar o teor de GC\n",
        "\n",
        "  Returns\n",
        "  -----\n",
        "  Float\n",
        "    Valor do teor de GC calculada para a cadeia de DNA fornecida\n",
        "\n",
        "  Raises\n",
        "  ----\n",
        "  AssertionError\n",
        "    No caso de não ser fornecida nenhuma cadeia de DNA\n",
        " \n",
        "  '''\n",
        "  assert len(DNA) != 0, 'A cadeia fornecida não pode ser uma string vazia' #garante que uma string vazia nao e fornecida\n",
        "  DNA         = DNA.strip().upper().replace(' ','')\n",
        "  C_count     = DNA.count('C')\n",
        "  G_count     = DNA.count('G')\n",
        "  GC_content  = (C_count/len(DNA))*100 + (G_count/len(DNA))*100\n",
        "  GC_content  = round(GC_content, 2)\n",
        "  return GC_content\n",
        "\n",
        "\n",
        "assert gc_content  (\"aaataTaTTaa\") == (00.00)\n",
        "assert gc_content  ('atgc AG CT' ) == (50.00)\n",
        "assert gc_content  ('   atgGCT  ') == (50.00)\n",
        "assert gc_content  ('GGGCGCCCCGC') == (100.00)\n",
        "\n",
        "\n",
        "def valid_strand(strand : str) -> bool:\n",
        "  '''\n",
        "  Função que recebe uma cadeia e verifica se é uma cadeia válida de DNA\n",
        "  \n",
        "  Parameters\n",
        "  -----\n",
        "  Strand:str\n",
        "    cadeia que se pretende verificar se corresponde a uma cadeia de DNA válida\n",
        "\n",
        "  Returns\n",
        "  -----\n",
        "  Bool\n",
        "    Retorna verdadeiro se a sequência for uma cadeia de DNA válido, caso contrário retorna falso\n",
        "\n",
        "  '''\n",
        "  return strand.strip().upper().replace('A', '').replace('C', '').replace('G', '').replace('T', '').replace(' ','') == ''\n",
        "\n",
        "assert valid_strand          ('')\n",
        "assert valid_strand          ('AAAAT')\n",
        "assert valid_strand          ('AAaaaaAA')\n",
        "assert valid_strand          ('AAA ttttcg t')\n",
        "assert not valid_strand      ('Uu')\n",
        "assert not valid_strand      ('aaaGTTT1TCCCC0')\n",
        "assert not valid_strand      ('XAAABQR')\n",
        "assert not valid_strand      ('AGT_CCA-GGGGCAA')\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 79,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "PNUoRKcqblJ-",
        "outputId": "69517262-7e4d-4f25-dad0-2793c8597434"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "O teor de GC na cadeia fornecida é de 0.0%.\n"
          ]
        }
      ],
      "source": [
        "strand = input()\n",
        "\n",
        "if valid_strand (strand) == True:\n",
        "  print('O teor de GC na cadeia fornecida é de {}%.'.format(gc_content (strand)))\n",
        "else:\n",
        "  print('Ocorreu um erro, verifica a cadeia fornecida')\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "wBpKyqE5yfkf"
      },
      "source": [
        "<!-- LTeX: language=pt -->\n",
        "## Tarefa 2 - Complemento inverso e tradução de codões\n",
        "\n",
        "A tarefa da semana 2 consiste em criar um conjunto de funções que permitam realizar a tradução de uma sequência de nucleótidos bem como a obtenção do complemento inverso de uma dada sequência de nucleotidos.\n",
        "\n",
        "**Tradução de codões**\n",
        "<div align='justify'>\n",
        "Primeiramente definiou-se a função cadeia_valida, que é utilizada para verificar se a sequência de nucleotidos fornecida é uma sequência válida, pois apenas se pretende realizar a tradução de sequências de nucleótidos válidas. Esta função pode receber quer sequências de DNA, quer de RNA.<br> \n",
        "Em seguida, definui-se a função tipo_seq que é necesária para identificar se a sequência fornecida é de DNA ou de RNA de modo a escolher a tabela de tradução de codões adequada.<br> \n",
        "Depois definiu-se a função tabela_traducao, sendo que esta utiliza o resultado da função anterior e devolve a tabela de tradução de codões standard adequada para o tipo de ácido nucleico que se pretende realizar a tradução.<br>\n",
        "Após isto, criou-se a função acid_nuc_2codons que é a responsável por extrair todos os codões da sequência de nucleotidos sendo que a função começa a extrair os codões apartir do início da sequência e apenas permite a obtenção dos codões para uma grelha de leitura que corresponde a grelha fornecida.<br>\n",
        "Por fim, definiu-se a função traducao_acid_nuc que integra as 4 funções anteriores de modo a validar a sequência de nucleotidos, identificar o tipo da sequência de nucleotidos, escolher a tabela de tradução adequada e a obtenção de todos os codões presentes na sequência. Após isto, ocorre a tradução propiamente dita, onde os codões são substituidos pelo respetivo aminoacido e adicionados a variável seq_aa que no fim vai ser retornada e corresponde à sequência de aminoacidos obtida para a sequência de nucleotidos.<br> \n",
        "</div>\n",
        "\n",
        "**Complemento inverso**\n",
        "<div align='justify'>\n",
        "A funcão complemento_inverso, vai utilizar uma sequência de DNA e devolver o seu complemento inverso. Para isso utiliza a função tipo_seq que vai validar se a sequência de nucleotidos fornecida é valida e se corresponde a uma sequência de DNA. Caso isto se verifique, vai ocorrer a substituição de cada base pela sua base complementar e a inversão da sequência, isto é, a sequência passa a ser apresentada do fim para o início\n",
        "</div>"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 80,
      "metadata": {
        "id": "nszelJ0QyrC-"
      },
      "outputs": [],
      "source": [
        "# tradução de codões\n",
        "def cadeia_valida (strand : str) -> bool:\n",
        "  '''\n",
        "  Verifica se a cadeia de nucleotidos fornecida é válida\n",
        "\n",
        "  Parameters\n",
        "  ----------\n",
        "  strand: str\n",
        "    Uma sequência de nucleótidos\n",
        "  DNA: bool\n",
        "    Identifica que a sequencia de nucleotidos é de DNA\n",
        "\n",
        "  Returns\n",
        "  ---------\n",
        "  bool\n",
        "    Retorna verdadeiro se a cadeia fornecida for um cadeia de nucleótidos válida  \n",
        "\n",
        "  Raises\n",
        "  ---------\n",
        "  AssertionError\n",
        "    Se a sequencia não for fornecida no formato de string\n",
        "  '''\n",
        "  assert type(strand)==str, \"A cadeia deve ser fornecida no formato de string\"\n",
        "  \n",
        "  for pos,base in enumerate(strand.upper().replace(\" \",\"\")): \n",
        "    if base not in \"AGCTU\":\n",
        "      print(f'O elemento {base}, na posição {pos+1}, não é um nucleotido válido')\n",
        "      return False\n",
        "  \n",
        "  if \"T\" in strand.upper() and \"U\" in strand.upper():\n",
        "    print('A sequencia de nucleotidos não é valida, pois possui T e U na mesma cadeia')\n",
        "    return False\n",
        "  \n",
        "  return True\n",
        "\n",
        "def tipo_seq(strand : str) -> str:\n",
        "  '''\n",
        "  Identifica o tipo de acido nucleico da sequencia fornecida\n",
        "\n",
        "  Parameters\n",
        "  ----------\n",
        "  strand: str\n",
        "    Uma sequência de nucleótidos\n",
        "\n",
        "  Returns\n",
        "  ---------\n",
        "  str\n",
        "    Retorna a classificação da cadeia de nucleótidos fornecida\\n\n",
        "    Por padrão, caso não esteja presente na sequencia a base uracilo, a sequência vai ser classificada como DNA\n",
        "    \n",
        "  Raises\n",
        "  -------\n",
        "  AssertionError\n",
        "    Quando não é fornecida nenhuma sequência\\n\n",
        "    Se a sequência fornecida não for válida\n",
        "  '''\n",
        "\n",
        "  assert len(strand)!= 0, \"Nenhuma cadeia foi fornecida\"\n",
        "  strand_valida= cadeia_valida(strand) #verificacao da validade da cadeia\n",
        "  assert strand_valida,\"A cadeia fornecida não é válida\"\n",
        "\n",
        "  if \"U\" in strand.upper(): return \"RNA\"\n",
        "  else: return \"DNA\"\n",
        "   \n",
        "def tabela_traducao(tipo_acid_nuc : str) -> dict[str:str]:\n",
        "  '''\n",
        "  Devolve a respetiva tabela de tradução para o acido nucleico fornecido\n",
        "\n",
        "  Parameters\n",
        "  ----------\n",
        "  tipo_acid_nuc: str\n",
        "    Classificacao do acido nucleico. Apenas pode assumir o valor de DNA ou RNA\n",
        "  \n",
        "  Returns\n",
        "  ---------\n",
        "  dict\n",
        "    Devolve a tabela de tradução STANDARD para o respetivo acido nucleico\n",
        "\n",
        "  Raises\n",
        "  ---------\n",
        "  AssertionError\n",
        "    Quando o tipo de acido nucleico fornecido nao e valido\n",
        "  '''\n",
        "\n",
        "  assert tipo_acid_nuc.upper() in ['DNA','RNA'], f'O valor {tipo_acid_nuc} não é um tipo de acido nucleico valido'\n",
        "\n",
        "  if tipo_acid_nuc.upper()==\"RNA\":\n",
        "    RNA_codon_table={\n",
        "     \"UUU\":\"F\", \"CUU\":\"L\", \"AUU\":\"I\", \"GUU\":\"V\", \"UUC\":\"F\", \"CUC\":\"L\", \"AUC\":\"I\", \"GUC\":\"V\",\n",
        "     \"UUA\":\"L\", \"CUA\":\"L\", \"AUA\":\"I\", \"GUA\":\"V\", \"UUG\":\"L\", \"CUG\":\"L\", \"AUG\":\"M\", \"GUG\":\"V\",\n",
        "     \"UCU\":\"S\", \"CCU\":\"P\", \"ACU\":\"T\", \"GCU\":\"A\", \"UCC\":\"S\", \"CCC\":\"P\", \"ACC\":\"T\", \"GCC\":\"A\",\n",
        "     \"UCA\":\"S\", \"CCA\":\"P\", \"ACA\":\"T\", \"GCA\":\"A\", \"UCG\":\"S\", \"CCG\":\"P\", \"ACG\":\"T\", \"GCG\":\"A\",\n",
        "     \"UAU\":\"Y\", \"CAU\":\"H\", \"AAU\":\"N\", \"GAU\":\"D\", \"UAC\":\"Y\", \"CAC\":\"H\", \"AAC\":\"N\", \"GAC\":\"D\",\n",
        "     \"UAA\":\"_\", \"CAA\":\"Q\", \"AAA\":\"K\", \"GAA\":\"E\", \"UAG\":\"_\", \"CAG\":\"Q\", \"AAG\":\"K\", \"GAG\":\"E\",\n",
        "     \"UGU\":\"C\", \"CGU\":\"R\", \"AGU\":\"S\", \"GGU\":\"G\", \"UGC\":\"C\", \"CGC\":\"R\", \"AGC\":\"S\", \"GGC\":\"G\",\n",
        "     \"UGA\":\"_\", \"CGA\":\"R\", \"AGA\":\"R\", \"GGA\":\"G\", \"UGG\":\"W\", \"CGG\":\"R\", \"AGG\":\"R\", \"GGG\":\"G\"}\n",
        "    return RNA_codon_table\n",
        "  \n",
        "  else:\n",
        "    DNA_codon_table={\n",
        "      \"ATA\":\"I\", \"ATC\":\"I\", \"ATT\":\"I\", \"ATG\":\"M\", \"ACA\":\"T\", \"ACC\":\"T\", \"ACG\":\"T\", \"ACT\":\"T\",\n",
        "      \"AAC\":\"N\", \"AAT\":\"N\", \"AAA\":\"K\", \"AAG\":\"K\", \"AGC\":\"S\", \"AGT\":\"S\", \"AGA\":\"R\", \"AGG\":\"R\",                \n",
        "      \"CTA\":\"L\", \"CTC\":\"L\", \"CTG\":\"L\", \"CTT\":\"L\", \"CCA\":\"P\", \"CCC\":\"P\", \"CCG\":\"P\", \"CCT\":\"P\",\n",
        "      \"CAC\":\"H\", \"CAT\":\"H\", \"CAA\":\"Q\", \"CAG\":\"Q\", \"CGA\":\"R\", \"CGC\":\"R\", \"CGG\":\"R\", \"CGT\":\"R\",\n",
        "      \"GTA\":\"V\", \"GTC\":'V', \"GTG\":'V', \"GTT\":\"V\", \"GCA\":\"A\", \"GCC\":\"A\", \"GCG\":\"A\", \"GCT\":\"A\",\n",
        "      \"GAC\":\"D\", \"GAT\":\"D\", \"GAA\":\"E\", \"GAG\":\"E\", \"GGA\":\"G\", \"GGC\":\"G\", \"GGG\":\"G\", \"GGT\":\"G\",\n",
        "      \"TCA\":\"S\", \"TCC\":\"S\", \"TCG\":\"S\", \"TCT\":\"S\", \"TTC\":\"F\", \"TTT\":\"F\", \"TTA\":\"L\", \"TTG\":\"L\",\n",
        "      \"TAC\":\"Y\", \"TAT\":\"Y\", \"TAA\":\"_\", \"TAG\":\"_\", \"TGC\":\"C\", \"TGT\":\"C\", \"TGA\":\"_\", \"TGG\":\"W\"}\n",
        "    return DNA_codon_table\n",
        "\n",
        "def acid_nuc_2codons(strand : str) -> list[str]:\n",
        "  '''\n",
        "  Devolve todos os codões para uma determinada sequencia de nucleotidos\n",
        "  \n",
        "  Parameters\n",
        "  ----------\n",
        "  Strand: str\n",
        "    Uma sequência válida de um acido nucleico\n",
        "\n",
        "  Returns\n",
        "  ---------\n",
        "  codoes: list\n",
        "    Devolve uma lista de strings que contem todos os codões\n",
        "\n",
        "  Raises\n",
        "  -------\n",
        "  AssertionError\n",
        "    Quando a sequencia fornecida não é valida\\n\n",
        "    Caso a sequência possua tamanho inferior a 3\n",
        "  '''\n",
        "  cad_valida=cadeia_valida(strand)\n",
        "  assert cad_valida, 'A cadeia fornecida não é valida'\n",
        "  assert len(strand)>=3, 'A cadeia fornecida apenas possui {} bases. São necessárias pelo menos 3 bases para formar codões'.format(len(strand))\n",
        "  codoes=[]\n",
        "  for I in range(0,len(strand)-2,3):\n",
        "    codao=strand[I:I+3]\n",
        "    codoes.append(codao.upper())\n",
        "  return codoes\n",
        "\n",
        "def traducao_acid_nuc(strand : str) -> str:\n",
        "  '''\n",
        "  Realiza a traducao da sequencia de nucleotidos para uma sequencia de aminoacidos\n",
        "\n",
        "  Parameters\n",
        "  ----------\n",
        "  Strand: str\n",
        "    Sequência de um acido nucleico\n",
        "\n",
        "  Returns\n",
        "  ---------\n",
        "  seq_aa: str\n",
        "    Sequência de aminoácidos resultantes da tradução\n",
        "\n",
        "  Raises\n",
        "  -------\n",
        "  AssertionError\n",
        "    Se a cadeia fornecida não for uma sequencia de nucleotidos valida\\n\n",
        "    Quando a cadeia fornecida é uma string vazia\\n\n",
        "    Caso a cadeia fornecida possua tamanho inferior a 3\n",
        "  '''\n",
        "\n",
        "  tipo_acid_nuc=tipo_seq(strand) #classificacao do acido nucleico\n",
        "  codoes= acid_nuc_2codons(strand) #gerarcao de todos os codoes da sequencia\n",
        "  tabela_codoes=tabela_traducao(tipo_acid_nuc) #obtencao da tabela de traducao \n",
        "  seq_aa=\"\"\n",
        "\n",
        "  for codao in codoes: seq_aa+=tabela_codoes[codao] #traducao dos codoes\n",
        "  return seq_aa"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 81,
      "metadata": {},
      "outputs": [],
      "source": [
        "# complemento inverso\n",
        "def complemento_inverso (strand : str) -> str:\n",
        "  '''\n",
        "  Determina a cadeia complementar inversa de uma sequencia de DNA \n",
        "\n",
        "  Parameters\n",
        "  ----------\n",
        "  Strand: str\n",
        "    Sequência de nucleotidos\n",
        "\n",
        "  Returns\n",
        "  ---------\n",
        "  complementar_inv: str\n",
        "    Complementar inverso da sequência de DNA fornecida\n",
        "\n",
        "  Raises\n",
        "  -------\n",
        "  AssertionError\n",
        "    Se não for fornecida nenhuma sequencia\\n\n",
        "    Caso a sequencia de nucleotidos não seja valida\\n\n",
        "    Quando a sequencia é de RNA\n",
        "  '''\n",
        "  tip_seq=tipo_seq(strand) #classificacao do acido nucleico e verificacao da sua validade\n",
        "  assert tip_seq==\"DNA\", \"A sequência fornecida tem de ser de DNA\"\n",
        "  complementar=\"\"\n",
        "  \n",
        "  DNA_bases_complementares={\"A\":\"T\",\"T\":\"A\",\"G\":\"C\",\"C\":\"G\"}\n",
        "  for base in strand.upper(): complementar+=DNA_bases_complementares[base]\n",
        "  \n",
        "  return complementar[::-1]"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 82,
      "metadata": {},
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "O resultado da tradução da cadeia fornecida é IPGETL\n",
            "O resultado do complemento inverso da cadeia fornecida é AAAAGGGTTTCCCCGGGAAT\n"
          ]
        }
      ],
      "source": [
        "#Exemplos práticos:\n",
        "#tradução\n",
        "traducao = traducao_acid_nuc(\"ATTCCCGGGGAAACCCTTTT\")\n",
        "\n",
        "#complemento inverso\n",
        "ci = complemento_inverso (\"ATTCCCGGGGAAACCCTTTT\")\n",
        "\n",
        "print(f\"O resultado da tradução da cadeia fornecida é {traducao}\")\n",
        "print(f\"O resultado do complemento inverso da cadeia fornecida é {ci}\")"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "<!-- LTeX: language=pt -->\n",
        "### Testes de unidade"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 83,
      "metadata": {
        "id": "T2etBLCW0_7h"
      },
      "outputs": [
        {
          "name": "stderr",
          "output_type": "stream",
          "text": [
            "test_acid_nuc_2codons (__main__.Test_traducao.test_acid_nuc_2codons) ... ok\n",
            "test_cadeia_valida (__main__.Test_traducao.test_cadeia_valida) ... ok\n",
            "test_complemento_inverso (__main__.Test_traducao.test_complemento_inverso) ... ok\n",
            "test_tabela_traducao (__main__.Test_traducao.test_tabela_traducao) ... ok\n",
            "test_tipo_sequencia (__main__.Test_traducao.test_tipo_sequencia) ... ok\n",
            "test_traducao_acid_nuc (__main__.Test_traducao.test_traducao_acid_nuc) ... ok\n",
            "\n",
            "----------------------------------------------------------------------\n",
            "Ran 6 tests in 0.022s\n",
            "\n",
            "OK\n"
          ]
        },
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "A sequencia de nucleotidos não é valida, pois possui T e U na mesma cadeia\n",
            "O elemento P, na posição 1, não é um nucleotido válido\n",
            "O elemento 3, na posição 6, não é um nucleotido válido\n",
            "A sequencia de nucleotidos não é valida, pois possui T e U na mesma cadeia\n"
          ]
        },
        {
          "data": {
            "text/plain": [
              "<unittest.runner.TextTestResult run=6 errors=0 failures=0>"
            ]
          },
          "execution_count": 83,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "#testes de unidade\n",
        "import unittest\n",
        "\n",
        "class Test_traducao(unittest.TestCase):\n",
        "    def test_cadeia_valida(self):\n",
        "        validas   = [\"\",\"AAA\",\"ATTCG\",\"UUAGAAGCAG\",\"attcg\",\"AAA UUUGCGA\",\"aTTcg\"]\n",
        "        invalidas = [\"UAAGT\",\"PANDA\",\"AAGCG324G\",\"AAAaaggttgU\"]\n",
        "        for x in validas:\n",
        "            self.assertTrue(cadeia_valida(x))\n",
        "        for y in invalidas:\n",
        "            self.assertFalse(cadeia_valida(y))\n",
        "\n",
        "    def test_tipo_sequencia(self):\n",
        "        rna = [\"AAAUGCUA\",\"UUU\",\"GGCgauCA\"]\n",
        "        dna = [\"AAAGTCG\",\"AAGGTCCCAG\",\"AAA\",\"TTTT\",\"GGGG\",\"CCCC\",\"ATcGT\"]\n",
        "        for x in rna:\n",
        "            self.assertEqual(tipo_seq(x),\"RNA\")\n",
        "        \n",
        "        for y in dna:\n",
        "            self.assertEqual(tipo_seq(y),\"DNA\")\n",
        "\n",
        "    def test_complemento_inverso(self):\n",
        "        sequencia         = [\"ATA\",\"ATAGC\",\"GGGGaaaaaaaatttatatat\"]\n",
        "        complento_reverso = [\"TAT\",\"GCTAT\",\"ATATATAAATTTTTTTTCCCC\"]\n",
        "\n",
        "        for x,y in zip(sequencia,complento_reverso):\n",
        "            self.assertEqual(complemento_inverso(x),y)\n",
        "        \n",
        "    def test_tabela_traducao(self):\n",
        "        DNA_codon_table={\n",
        "      \"ATA\":\"I\", \"ATC\":\"I\", \"ATT\":\"I\", \"ATG\":\"M\", \"ACA\":\"T\", \"ACC\":\"T\", \"ACG\":\"T\", \"ACT\":\"T\",\n",
        "      \"AAC\":\"N\", \"AAT\":\"N\", \"AAA\":\"K\", \"AAG\":\"K\", \"AGC\":\"S\", \"AGT\":\"S\", \"AGA\":\"R\", \"AGG\":\"R\",                \n",
        "      \"CTA\":\"L\", \"CTC\":\"L\", \"CTG\":\"L\", \"CTT\":\"L\", \"CCA\":\"P\", \"CCC\":\"P\", \"CCG\":\"P\", \"CCT\":\"P\",\n",
        "      \"CAC\":\"H\", \"CAT\":\"H\", \"CAA\":\"Q\", \"CAG\":\"Q\", \"CGA\":\"R\", \"CGC\":\"R\", \"CGG\":\"R\", \"CGT\":\"R\",\n",
        "      \"GTA\":\"V\", \"GTC\":'V', \"GTG\":'V', \"GTT\":\"V\", \"GCA\":\"A\", \"GCC\":\"A\", \"GCG\":\"A\", \"GCT\":\"A\",\n",
        "      \"GAC\":\"D\", \"GAT\":\"D\", \"GAA\":\"E\", \"GAG\":\"E\", \"GGA\":\"G\", \"GGC\":\"G\", \"GGG\":\"G\", \"GGT\":\"G\",\n",
        "      \"TCA\":\"S\", \"TCC\":\"S\", \"TCG\":\"S\", \"TCT\":\"S\", \"TTC\":\"F\", \"TTT\":\"F\", \"TTA\":\"L\", \"TTG\":\"L\",\n",
        "      \"TAC\":\"Y\", \"TAT\":\"Y\", \"TAA\":\"_\", \"TAG\":\"_\", \"TGC\":\"C\", \"TGT\":\"C\", \"TGA\":\"_\", \"TGG\":\"W\"}\n",
        "        \n",
        "        RNA_codon_table={\n",
        "      \"UUU\":\"F\", \"CUU\":\"L\", \"AUU\":\"I\", \"GUU\":\"V\", \"UUC\":\"F\", \"CUC\":\"L\", \"AUC\":\"I\", \"GUC\":\"V\",\n",
        "      \"UUA\":\"L\", \"CUA\":\"L\", \"AUA\":\"I\", \"GUA\":\"V\", \"UUG\":\"L\", \"CUG\":\"L\", \"AUG\":\"M\", \"GUG\":\"V\",\n",
        "      \"UCU\":\"S\", \"CCU\":\"P\", \"ACU\":\"T\", \"GCU\":\"A\", \"UCC\":\"S\", \"CCC\":\"P\", \"ACC\":\"T\", \"GCC\":\"A\",\n",
        "      \"UCA\":\"S\", \"CCA\":\"P\", \"ACA\":\"T\", \"GCA\":\"A\", \"UCG\":\"S\", \"CCG\":\"P\", \"ACG\":\"T\", \"GCG\":\"A\",\n",
        "      \"UAU\":\"Y\", \"CAU\":\"H\", \"AAU\":\"N\", \"GAU\":\"D\", \"UAC\":\"Y\", \"CAC\":\"H\", \"AAC\":\"N\", \"GAC\":\"D\",\n",
        "      \"UAA\":\"_\", \"CAA\":\"Q\", \"AAA\":\"K\", \"GAA\":\"E\", \"UAG\":\"_\", \"CAG\":\"Q\", \"AAG\":\"K\", \"GAG\":\"E\",\n",
        "      \"UGU\":\"C\", \"CGU\":\"R\", \"AGU\":\"S\", \"GGU\":\"G\", \"UGC\":\"C\", \"CGC\":\"R\", \"AGC\":\"S\", \"GGC\":\"G\",\n",
        "      \"UGA\":\"_\", \"CGA\":\"R\", \"AGA\":\"R\", \"GGA\":\"G\", \"UGG\":\"W\", \"CGG\":\"R\", \"AGG\":\"R\", \"GGG\":\"G\"}\n",
        "\n",
        "        self.assertEqual(tabela_traducao(\"RNA\"),RNA_codon_table) \n",
        "        self.assertEqual(tabela_traducao(\"DNA\"),DNA_codon_table)\n",
        "\n",
        "    def test_acid_nuc_2codons(self):\n",
        "        seq    =[\"AAA\", \"AAGA\",\"CGAAGUACG\"]\n",
        "        codoes =[[\"AAA\"],[\"AAG\"],[\"CGA\",\"AGU\",\"ACG\"]]\n",
        "\n",
        "        for x,y in zip(seq,codoes):\n",
        "            self.assertEqual(acid_nuc_2codons(x),y)\n",
        "    \n",
        "    def test_traducao_acid_nuc(self):\n",
        "        seq    = [\"AUGUGGUUC\",\"ATGTGGTTC\",\"AUGAUCUCGUAA\",\"ATGATCTCGTAA\"]\n",
        "        seq_aa = [\"MWF\",\"MWF\",\"MIS_\", \"MIS_\"]\n",
        "\n",
        "        for x,y in zip(seq,seq_aa):\n",
        "            self.assertEqual(traducao_acid_nuc(x),y)\n",
        "    \n",
        "suite = unittest.TestLoader().loadTestsFromTestCase(Test_traducao)\n",
        "unittest.TextTestRunner(verbosity=3).run(suite)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "W25Qvc7syufp"
      },
      "source": [
        "<!-- LTeX: language=pt -->\n",
        "## Tarefa 3 - Tradução do DNA, ORF (open reading frames) e extração de todas as proteínas possíveis\n",
        "\n",
        "<div align='justify'>\n",
        "\n",
        "Nesta tarefa é proposto que a partir de uma sequência de DNA se proceda à extração de todas as proteínas que podem ser codificadas por uma sequência de DNA nas várias reading frames existentes. Para se realizar a extração de todas as proteínas que se encontram codificadas numa sequência de DNA é necessário determinar os codões de cada reading frame, realizar a tradução dos codões de acordo com uma tabela de tradução de codões considerando que podem existir vários codões de iniciação para cada tabela de tradução utilizada, extrair, para cada sequência de aminoacidos resultante, todas as possíveis proteínas e, por fim, apresentar as diversas proteínas que é possível obter da sequência de DNA.<br>\n",
        "\n",
        "Para atingir este objetivo é necessário definir as seguintes funções:<br>\n",
        "Uma função que valide a sequência de DNA fornecida e uma função que permita obter o complementar inverso do DNA em estudo. Estas funções foram definidas na tarefa anterior (tipo_sep e complemento_inverso)<br>\n",
        "Para se obter os codões de uma determinada reading frame criou-se a função rf_codoes, que foi posteriormente integrada na função all_rfs que permite obter os codões para todas as reading frames possíveis.<br>\n",
        "Definiu-se a função codon_table de modo a poder selecionar a tablela de tradução adequada, isto é, permitir ajustar a tabela de tradução conforme o organismo da qual proveem o DNA. A função start_codon foi definida para verificar se o codão que se pretende usar para iniciar a tradução de proteínas constitui uma alternativa válida para a tabela de tradução utilizada enquanto a função stop_codons foi definida com o mesmo inuito, mas para os codões de stop.\n",
        "Em seguida criou-se a função traducao_rf de modo a poder realizar a tradução dos codões para cada reading frame. Por fim, definiu-se a função find_prots que encontra as possíveis proteínas existentes na sequência de aminoacidos que resulta da tradução.<br>\n",
        "A função all_prots integra todas as funções abordadas anteriormente e devolve um conjunto de proteínas que corresponde a todas as proteínas distinas que são codificadas.\n",
        "</div>"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 84,
      "metadata": {},
      "outputs": [],
      "source": [
        "def rf_codoes(strand : str, reading_frame = 0) -> list[str]:\n",
        "  '''\n",
        "  Extrai todos os codões de uma sequência de DNA para uma determinada reading frame\n",
        "\n",
        "  Parameters\n",
        "  -----\n",
        "  strand: str\n",
        "    Cadeia de DNA da qual se pretende realizar a extração dos codões para um determinada ORF\n",
        "    \n",
        "  reading_frame: int\n",
        "    Corresponde à reanding frame que se pretende utilizar. Por padrão assume o valor 0, mas pode também assumir o valor 1 e 2\n",
        "\n",
        "  Returns\n",
        "  -------\n",
        "  codoes: list[str]\n",
        "    Corresponde aos vários codões para a reading frame indicada\n",
        "\n",
        "  Raises\n",
        "  ------\n",
        "  AssertionError\n",
        "    Se a variavél strand não for do tipo string\\n\n",
        "    Caso a cadeia fornecida não seja válida e/ou não seja uma cadeia de DNA\\n\n",
        "    Quando o valor do parametro reading_frame não está entre 0 e 2 inclusive e/ou não é um inteiro\n",
        "  '''\n",
        "  assert type(strand)==str #forcar a variavel strand a ser uma string\n",
        "  assert tipo_seq(strand)=='DNA','A sequência fornecida deve ser de DNA' #funcao da semana anterior\n",
        "  assert reading_frame >=0 and reading_frame<=2 and type(reading_frame)==int,\"A reading frame fornecida deve ser um inteiro entre 0 e 2\"\n",
        "    \n",
        "  codoes=[strand[indice:indice+3].upper() for indice in range(reading_frame,len(strand)-2,3)]\n",
        "    \n",
        "  return codoes\n",
        "\n",
        "def all_rfs(strand : str) -> list[list[str]] :\n",
        "  '''\n",
        "  Devolve todos os codões para cada reading frame possível da sequencia de DNA indicada\n",
        "\n",
        "  Parameters\n",
        "  ----------\n",
        "  strand: str\n",
        "    Cadeia de DNA em estudo\n",
        "\n",
        "  Returns\n",
        "  ----------\n",
        "  rfs_codoes: list[list[str]]\n",
        "    Corresponde a todos os codões possíveis para as várias reading frames\n",
        "\n",
        "  Raises\n",
        "  -------\n",
        "  AssertionError\n",
        "    Se a sequencia fornecida não for válida e/ou não for uma sequência de DNA\\n\n",
        "    Quando a strand é uma string vazia\n",
        "  '''\n",
        "  assert type(strand)==str\n",
        "  inv=complemento_inverso(strand) #funcao da semana passada\n",
        "  rfs_codoes=[rf_codoes(strand,I)for I in range(3)] + [rf_codoes(inv,I) for I in range(3)]\n",
        "  return rfs_codoes\n",
        "\n",
        "def codon_table(genetic_code : str, nomes = False) -> dict[str,str]:\n",
        "  '''\n",
        "  Devolve a tabela de tradução adequada para o codigo genético indicado\n",
        "\n",
        "  Parameters\n",
        "  ----------\n",
        "  genetic_code: str\n",
        "    String que identifica o codigo genético a utilizar. Quando assume o valor de 'Vertebrate Mitochondrial' a\n",
        "    tabela fornecida é a da mitocondria do humano\n",
        "\n",
        "  nomes: bool\n",
        "    Por padrao encontra-se definido como False. Pode também assumir o valor de True\n",
        "    \n",
        "  Returns\n",
        "  ---------\n",
        "  dict\n",
        "    Quando o parâmetros nomes assume o booleano False, devolve a tabela de tradução de codões para o \n",
        "    respetivo codigo genético na forma de dicionario\n",
        "\n",
        "  codigos: list[str]\n",
        "    Quando o parâmetro nomes assume o valor True é devolvida uma lista com todos os códigos genéticos\n",
        "    que possuem uma tabela de tradução associada\n",
        "\n",
        "  Raises\n",
        "  -------\n",
        "  AssertionError\n",
        "    Caso o codigo genético não seja fornecido em formato de string\\n\n",
        "    Quando o código genético fornecido não possui nenhuma tabela associada\n",
        "  '''\n",
        "  codigos=[\"Standard\",\"Vertebrate Mitochondrial\",\"Bacterial\"]\n",
        "  \n",
        "  if nomes:\n",
        "    return codigos\n",
        "\n",
        "  else:\n",
        "    assert type(genetic_code)==str,'O parâmetro genetic_code apenas pode ser do tipo string'\n",
        "    assert genetic_code in codigos,f'O codigo genetico {genetic_code} não está disponível'\n",
        "    \n",
        "    if genetic_code==\"Standard\":\n",
        "      standard_table={\n",
        "        \"ATA\":\"I\", \"ATC\":\"I\", \"ATT\":\"I\", \"ATG\":\"M\", \"ACA\":\"T\", \"ACC\":\"T\", \"ACG\":\"T\", \"ACT\":\"T\",\n",
        "        \"AAC\":\"N\", \"AAT\":\"N\", \"AAA\":\"K\", \"AAG\":\"K\", \"AGC\":\"S\", \"AGT\":\"S\", \"AGA\":\"R\", \"AGG\":\"R\",                \n",
        "        \"CTA\":\"L\", \"CTC\":\"L\", \"CTG\":\"L\", \"CTT\":\"L\", \"CCA\":\"P\", \"CCC\":\"P\", \"CCG\":\"P\", \"CCT\":\"P\",\n",
        "        \"CAC\":\"H\", \"CAT\":\"H\", \"CAA\":\"Q\", \"CAG\":\"Q\", \"CGA\":\"R\", \"CGC\":\"R\", \"CGG\":\"R\", \"CGT\":\"R\",\n",
        "        \"GTA\":\"V\", \"GTC\":'V', \"GTG\":'V', \"GTT\":\"V\", \"GCA\":\"A\", \"GCC\":\"A\", \"GCG\":\"A\", \"GCT\":\"A\",\n",
        "        \"GAC\":\"D\", \"GAT\":\"D\", \"GAA\":\"E\", \"GAG\":\"E\", \"GGA\":\"G\", \"GGC\":\"G\", \"GGG\":\"G\", \"GGT\":\"G\",\n",
        "        \"TCA\":\"S\", \"TCC\":\"S\", \"TCG\":\"S\", \"TCT\":\"S\", \"TTC\":\"F\", \"TTT\":\"F\", \"TTA\":\"L\", \"TTG\":\"L\",\n",
        "        \"TAC\":\"Y\", \"TAT\":\"Y\", \"TAA\":\"_\", \"TAG\":\"_\", \"TGC\":\"C\", \"TGT\":\"C\", \"TGA\":\"_\", \"TGG\":\"W\"}\n",
        "      return standard_table\n",
        "  \n",
        "    elif genetic_code == \"Vertebrate Mitochondrial\":\n",
        "      homo_verte_mito_table={\n",
        "        \"TTT\": \"F\", \"TCT\": \"S\", \"TAT\": \"Y\", \"TGT\": \"C\", \"TTC\": \"F\", \"TCC\": \"S\", \"TAC\": \"Y\", \"TGC\": \"C\", \n",
        "        \"TTA\": \"L\", \"TCA\": \"S\", \"TAA\": \"_\", \"TGA\": \"W\", \"TTG\": \"L\", \"TCG\": \"S\", \"TAG\": \"_\", \"TGG\": \"W\",\n",
        "        \"CTT\": \"L\", \"CCT\": \"P\", \"CAT\": \"H\", \"CGT\": \"R\", \"CTC\": \"L\", \"CCC\": \"P\", \"CAC\": \"H\", \"CGC\": \"R\",\n",
        "        \"CTA\": \"L\", \"CCA\": \"P\", \"CAA\": \"Q\", \"CGA\": \"R\", \"CTG\": \"L\", \"CCG\": \"P\", \"CAG\": \"Q\", \"CGG\": \"R\",\n",
        "        \"ATT\": \"I\", \"ACT\": \"T\", \"AAT\": \"N\", \"AGT\": \"S\", \"ATC\": \"I\", \"ACC\": \"T\", \"AAC\": \"N\", \"AGC\": \"S\",\n",
        "        \"ATA\": \"M\", \"ACA\": \"T\", \"AAA\": \"K\", \"AGA\": \"_\", \"ATG\": \"M\", \"ACG\": \"T\", \"AAG\": \"K\", \"AGG\": \"_\",\n",
        "        \"GTT\": \"V\", \"GCT\": \"A\", \"GAT\": \"D\", \"GGT\": \"G\", \"GTC\": \"V\", \"GCC\": \"A\", \"GAC\": \"D\", \"GGC\": \"G\",\n",
        "        \"GTA\": \"V\", \"GCA\": \"A\", \"GAA\": \"E\", \"GGA\": \"G\", \"GTG\": \"V\", \"GCG\": \"A\", \"GAG\": \"E\", \"GGG\": \"G\"}\n",
        "      return homo_verte_mito_table\n",
        "  \n",
        "    elif genetic_code==\"Bacterial\":\n",
        "      bacterial_table={\n",
        "        \"TTT\": \"F\", \"TCT\": \"S\", \"TAT\": \"Y\", \"TGT\": \"C\", \"TTC\": \"F\", \"TCC\": \"S\", \"TAC\": \"Y\", \"TGC\": \"C\",\n",
        "        \"TTA\": \"L\", \"TCA\": \"S\", \"TAA\": \"_\", \"TGA\": \"_\", \"TTG\": \"L\", \"TCG\": \"S\", \"TAG\": \"_\", \"TGG\": \"W\",\n",
        "        \"CTT\": \"L\", \"CCT\": \"P\", \"CAT\": \"H\", \"CGT\": \"R\", \"CTC\": \"L\", \"CCC\": \"P\", \"CAC\": \"H\", \"CGC\": \"R\",\n",
        "        \"CTA\": \"L\", \"CCA\": \"P\", \"CAA\": \"Q\", \"CGA\": \"R\", \"CTG\": \"L\", \"CCG\": \"P\", \"CAG\": \"Q\", \"CGG\": \"R\",\n",
        "        \"ATT\": \"I\", \"ACT\": \"T\", \"AAT\": \"N\", \"AGT\": \"S\", \"ATC\": \"I\", \"ACC\": \"T\", \"AAC\": \"N\", \"AGC\": \"S\",\n",
        "        \"ATA\": \"I\", \"ACA\": \"T\", \"AAA\": \"K\", \"AGA\": \"R\", \"ATG\": \"M\", \"ACG\": \"T\", \"AAG\": \"K\", \"AGG\": \"R\",\n",
        "        \"GTT\": \"V\", \"GCT\": \"A\", \"GAT\": \"D\", \"GGT\": \"G\", \"GTC\": \"V\", \"GCC\": \"A\", \"GAC\": \"D\", \"GGC\": \"G\", \n",
        "        \"GTA\": \"V\", \"GCA\": \"A\", \"GAA\": \"E\", \"GGA\": \"G\", \"GTG\": \"V\", \"GCG\": \"A\", \"GAG\": \"E\", \"GGG\": \"G\"}\n",
        "      return bacterial_table\n",
        "    \n",
        "def start_codons(genetic_code : str) -> list:\n",
        "  '''\n",
        "  Devolve todos os codões de iniciação possíveis para o codigo genético indicado\n",
        "\n",
        "  Parameters\n",
        "  ----------\n",
        "  genetic_code: str\n",
        "    String que identifica o codigo genético a utilizar. Quando assume o valor de 'Vertebrate Mitochondrial' devolve os codões de iniciação\n",
        "    para a mitocondria do humano\n",
        "    \n",
        "  Returns\n",
        "  ----------\n",
        "  start: list[str]\n",
        "    Lista que contem todos os codões de iniciação possíveis para determinado código genético\n",
        "\n",
        "  Raises\n",
        "  -------\n",
        "  AssertionError\n",
        "    Caso o codigo genético não seja fornecido em formato de string\\n\n",
        "    Quando o código genético fornecido não possui nenhuma tabela associada\n",
        "  '''\n",
        "  codigos=[\"Standard\",\"Vertebrate Mitochondrial\",\"Bacterial\"]\n",
        "  assert type(genetic_code)==str,'O parâmetro genetic_code apenas pode ser do tipo string'\n",
        "  assert genetic_code in codigos,f'O codigo genetico {genetic_code} não está disponível'\n",
        "    \n",
        "  if genetic_code==\"Standard\":\n",
        "    start=['ATG','CTG','TTG']\n",
        "    return start\n",
        "  \n",
        "  elif genetic_code == \"Vertebrate Mitochondrial\":\n",
        "    start=['ATG','ATT']\n",
        "    return start\n",
        "    \n",
        "  elif genetic_code==\"Bacterial\":\n",
        "    start=['ATG','ATA','ATC','ATT','CTG','TTG','GTC']\n",
        "    return start\n",
        "  \n",
        "def stop_codons(genetic_code : str) -> list[str]:\n",
        "  '''\n",
        "  Devolve todos os codões de stop possíveis para o codigo genético indicado\n",
        "\n",
        "  Parameters\n",
        "  ----------\n",
        "  genetic_code: str\n",
        "    String que identifica o codigo genético a utilizar.\n",
        "    \n",
        "  Returns\n",
        "  ----------\n",
        "  stop: list[str]\n",
        "    Lista que contem todos os codões de stop possíveis para um determinado código genético\n",
        "\n",
        "  Raises\n",
        "  -------\n",
        "  AssertionError\n",
        "    Caso o codigo genético não seja fornecido em formato de string\\n\n",
        "    Quando o código genético fornecido não possui nenhuma tabela associada\n",
        "  '''\n",
        "  codigos=[\"Standard\",\"Vertebrate Mitochondrial\",\"Bacterial\"]\n",
        "  assert type(genetic_code)==str,'O parâmetro genetic_code apenas pode ser do tipo string'\n",
        "  assert genetic_code in codigos,f'O codigo genetico {genetic_code} não está disponível'\n",
        "    \n",
        "  if genetic_code==\"Standard\":\n",
        "    stop=['TAA','TAG','TGA']\n",
        "    return stop\n",
        "  \n",
        "  elif genetic_code == \"Vertebrate Mitochondrial\":\n",
        "    stop=['TAA','TAG','AGA','AGG']\n",
        "    return stop\n",
        "    \n",
        "  elif genetic_code==\"Bacterial\":\n",
        "    stop=['TAA','TAG','TGA']\n",
        "    return stop\n",
        "\n",
        "def traducao_rf(all_rf_codoes : list[list[str]], genetic_code = \"Standard\", start_codon = 'ATG') -> list[str]:\n",
        "  '''\n",
        "  Devolve uma sequência de aminoácidos para cada reading frame\n",
        "\n",
        "  Parameters\n",
        "  ----------\n",
        "  rf_codoes: list[list[str]]\n",
        "    Lista que contêm todos os codões em formato de string para uma determinada reading frame\n",
        "\n",
        "  genetic_code: str\n",
        "    Indica que tabela de tradução deve ser utilizada. Por padrão utiliza a tabela standard\n",
        "\n",
        "  start_codon: str\n",
        "    Indica qual o codão de iniciação a ser utilizada. Utiliza o codão ATG como default\n",
        " \n",
        "  Returns\n",
        "  ---------\n",
        "  seq_aas: list[str]\n",
        "    Sequência de aminoácidos resultantes da tradução para cada reading frame\n",
        "\n",
        "  Raises\n",
        "  -------\n",
        "  AssertionError\n",
        "    Caso o codão de start fornecido não seja um codão válido ou não seja fornecido no formato de string\\n\n",
        "    Se o código genético não for fornecido em formato de string ou não possuir tabela de tradução associada\n",
        "  '''\n",
        "  trans_table=codon_table(genetic_code)\n",
        "  assert type(start_codon)==str,'O codão de iniciação deve ser do tipo string'\n",
        "  start=start_codons(genetic_code)\n",
        "  assert start_codon.upper() in start,f'O codão de iniciação {start_codon} não ocorre no codigo genético {genetic_code}'\n",
        "  stop=stop_codons(genetic_code)\n",
        "  estado=False\n",
        "  seq_aas=[]\n",
        "  \n",
        "  for rf in all_rf_codoes:\n",
        "    seq_aa=''\n",
        "    for codao in rf:\n",
        "      if estado:\n",
        "       seq_aa+=trans_table[codao.upper()]\n",
        "       if codao.upper() in stop:\n",
        "         estado=False\n",
        "         continue\n",
        "\n",
        "      if not estado:\n",
        "        if codao.upper()==start_codon.upper():\n",
        "         seq_aa+='M'\n",
        "         estado=True\n",
        "        \n",
        "        else:seq_aa+=trans_table[codao.upper()]\n",
        "\n",
        "    seq_aas.append(seq_aa)\n",
        "\n",
        "  return seq_aas\n",
        "\n",
        "def find_prots(seq_aa : str) -> list[str]:\n",
        "  '''\n",
        "  Devolve todos as proteínas hipotéticas presentes em uma sequência de aminoácidos\n",
        "\n",
        "  Parameters\n",
        "  ----------\n",
        "  seq_aa: str\n",
        "    Sequência de aminoacidos da qual se prende extrair todas as proteinas existentes na sequencia\n",
        " \n",
        "  Returns\n",
        "  ---------\n",
        "  seq_aas: list[str]\n",
        "      Sequência de aminoácidos resultantes da tradução para cada reading frame\n",
        "\n",
        "  Raises\n",
        "  -------\n",
        "  AssertionError\n",
        "    Quando a sequencia fornecida não está no formato de string\\n\n",
        "    Caso o aminoacido presente na sequencia não seja um aminoácido válido\n",
        "  '''\n",
        "  assert type(seq_aa)==str,'A sequencia de aminoacidos deve ser do tipo str'\n",
        "  alfabeto='ACDEFGHIKLMNPQRSTVWY_'\n",
        "  prots=[]\n",
        "  prot=''\n",
        "  estado=False\n",
        "\n",
        "  for aa in seq_aa.upper():\n",
        "    assert aa in alfabeto,f'O aminoacido {aa} não esta presente no alfabeto dos aminoacidos'\n",
        "    if estado:\n",
        "      if aa==\"_\":\n",
        "        estado=False\n",
        "        prots.append(prot)\n",
        "        prot=''\n",
        "        continue\n",
        "      else:prot+=aa\n",
        "\n",
        "    else:\n",
        "      if aa=='M':\n",
        "        prot+=aa\n",
        "        estado=True\n",
        "\n",
        "  return prots\n",
        "\n",
        "def all_prots(strand : str, gen_code = 'Standard', start = 'ATG') -> set:\n",
        "  '''\n",
        "  Devolve todos as proteínas possíveis que são codificas pela cadeia fornecida em todas as reading frames\n",
        "\n",
        "  Parameters\n",
        "  ----------\n",
        "  strand: str\n",
        "    Cadeia de DNA da qual se pretende extrair todas as proteínas existentes nas 6 reading frames\n",
        "\n",
        "  gen_code: str\n",
        "    Corresponde ao código genético a utilizar para realizar a tradução\n",
        "\n",
        "  start: str\n",
        "    Codão de iniciação a utilizar para realizar a tradução dos codões\n",
        "\n",
        "  Returns\n",
        "  ---------\n",
        "  todas_proteinas: set()\n",
        "    Corresonde ao conjunto de todas as proteínas distintas que podem ser codificadas pela sequênica nas 6\n",
        "    reading frames possíveis\n",
        "\n",
        "  Raises\n",
        "  -------\n",
        "  AssertionError\n",
        "    Se a sequência fornecida não for válida e/ou não for uma sequência de DNA\\n\n",
        "    Quando a strand corresponde a uma string vazia\\n\n",
        "    Caso o codão start fornecido não seja válido ou não seja fornecido em formato de string\\n\n",
        "    Se o código não for fornecido em formato de string ou não possua tablea de tradução associada\\n\n",
        "  '''\n",
        "  rfs_cod=all_rfs(strand) #obtenção dos codoes para todas as reading frames\n",
        "  rfs_seq_aa=traducao_rf(rfs_cod,genetic_code=gen_code,start_codon=start) #traducao dos codoes de cada reading frame\n",
        "  todas_proteinas=set()\n",
        "  for seq in rfs_seq_aa: #navegacao entre as várias sequencias de aminoacidos\n",
        "    prots=find_prots(seq) #obtenção de todas as proteinas existens na sequencia de aminoacidos\n",
        "    for prot in prots:\n",
        "      todas_proteinas|=set([prot])\n",
        "\n",
        "  if len(todas_proteinas)==0:\n",
        "    print('A sequência não codifica nenhuma proteína')\n",
        "    return todas_proteinas\n",
        "    \n",
        "  else:\n",
        "    print(f'A sequência codifica {len(todas_proteinas)} proteinas diferentes em todas as reading frames possíveis')\n",
        "    return todas_proteinas\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 85,
      "metadata": {},
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "Exemplo variando a tabela de tradução:\n",
            "A sequência codifica 1 proteinas diferentes em todas as reading frames possíveis\n",
            "{'MLIM'}\n",
            "A sequência codifica 1 proteinas diferentes em todas as reading frames possíveis\n",
            "{'MLIM'}\n",
            "A sequência não codifica nenhuma proteína\n",
            "set()\n",
            "\n",
            "Exemplo variando o codão de iniciação:\n",
            "A sequência codifica 1 proteinas diferentes em todas as reading frames possíveis\n",
            "{'MLIM'}\n",
            "A sequência codifica 1 proteinas diferentes em todas as reading frames possíveis\n",
            "{'MLMLIM'}\n",
            "A sequência codifica 1 proteinas diferentes em todas as reading frames possíveis\n",
            "{'MISIN'}\n"
          ]
        }
      ],
      "source": [
        "strand='CTGTTGATGCTGATTATGTGA'\n",
        "#Exemplo do funcionamento da função all_prots variando a tabela de tradução\n",
        "print('Exemplo variando a tabela de tradução:') \n",
        "print(all_prots(strand,'Bacterial',start='ATG'))\n",
        "print(all_prots(strand,'Standard',start='ATG'))\n",
        "print(all_prots(strand,'Vertebrate Mitochondrial',start='ATG'),end='\\n\\n')\n",
        "#Exemplo do funcionamento da função all_prots variando o codão de iniciação\n",
        "print('Exemplo variando o codão de iniciação:') # os codões de inicação para cada codigo genético foram retirados da pagina do NCBI\n",
        "print(all_prots(strand,'Bacterial',start='ATC'))\n",
        "print(all_prots(strand,'Standard',start='CTG'))\n",
        "print(all_prots('ATT'+strand,'Vertebrate Mitochondrial',start='ATT'))\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "### Testes de unidade"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 86,
      "metadata": {
        "id": "u_59x6Hu1Iax"
      },
      "outputs": [
        {
          "name": "stderr",
          "output_type": "stream",
          "text": [
            "test_all_prots (__main__.Test_ORFs.test_all_prots) ... ok\n",
            "test_all_rfs (__main__.Test_ORFs.test_all_rfs) ... ok\n",
            "test_find_prots (__main__.Test_ORFs.test_find_prots) ... ok\n",
            "test_rf_codoes (__main__.Test_ORFs.test_rf_codoes) ... ok\n",
            "test_traducao_rf (__main__.Test_ORFs.test_traducao_rf) ... ok\n",
            "\n",
            "----------------------------------------------------------------------\n",
            "Ran 5 tests in 0.023s\n",
            "\n",
            "OK\n"
          ]
        },
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "A sequência não codifica nenhuma proteína\n",
            "A sequência codifica 1 proteinas diferentes em todas as reading frames possíveis\n",
            "A sequência não codifica nenhuma proteína\n",
            "A sequência codifica 1 proteinas diferentes em todas as reading frames possíveis\n"
          ]
        },
        {
          "data": {
            "text/plain": [
              "<unittest.runner.TextTestResult run=5 errors=0 failures=0>"
            ]
          },
          "execution_count": 86,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "import unittest\n",
        "\n",
        "class Test_ORFs(unittest.TestCase):\n",
        "    def test_rf_codoes(self):\n",
        "        seqs=['ACGTAACGATTTAGCCAGCT','ACCTGAatgctagA']\n",
        "        rf_0=[['ACG','TAA','CGA','TTT','AGC','CAG'],['ACC','TGA','ATG','CTA']]\n",
        "        rf_1=[['CGT','AAC','GAT','TTA','GCC','AGC'],['CCT','GAA','TGC','TAG']]\n",
        "        rf_2=[['GTA','ACG','ATT','TAG','CCA','GCT'],['CTG','AAT','GCT','AGA']]\n",
        "        \n",
        "        for x,y,w,z in zip(seqs,rf_0,rf_1,rf_2):\n",
        "            self.assertEqual(rf_codoes(x,reading_frame=0),y)\n",
        "            self.assertEqual(rf_codoes(x,reading_frame=1),w)\n",
        "            self.assertEqual(rf_codoes(x,reading_frame=2),z)\n",
        "\n",
        "    def test_all_rfs(self):\n",
        "        seqs={1:'ACGTAACGATTTAGCCAGCT', 2:'CTGTTGATGCTGATTATGTGa'}\n",
        "        rfs={\n",
        "            1:[ ['ACG','TAA','CGA','TTT','AGC','CAG'],['CGT','AAC','GAT','TTA','GCC','AGC'],\n",
        "                ['GTA','ACG','ATT','TAG','CCA','GCT'],['AGC','TGG','CTA','AAT','CGT','TAC'],\n",
        "                ['GCT','GGC','TAA','ATC','GTT','ACG'],['CTG','GCT','AAA','TCG','TTA','CGT']],\n",
        "            2:[ ['CTG','TTG','ATG','CTG','ATT','ATG','TGA'],['TGT','TGA','TGC','TGA','TTA','TGT'],\n",
        "                ['GTT','GAT','GCT','GAT','TAT','GTG'],['TCA','CAT','AAT','CAG','CAT','CAA','CAG'],\n",
        "                ['CAC','ATA','ATC','AGC','ATC','AAC'],['ACA','TAA','TCA','GCA','TCA','ACA']]}\n",
        "\n",
        "        for I in seqs:\n",
        "            self.assertEqual(all_rfs(seqs[I]),rfs[I])\n",
        "    \n",
        "    def test_traducao_rf(self):\n",
        "        rfs_codoes={\n",
        "            1:[ ['ACG','TAA','CGA','TTT','AGC','CAG'],['CGT','AAC','GAT','TTA','GCC','AGC'],\n",
        "                ['GTA','ACG','ATT','TAG','CCA','GCT'],['AGC','TGG','CTA','AAT','CGT','TAC'],\n",
        "                ['GCT','GGC','TAA','ATC','GTT','ACG'],['CTG','GCT','AAA','TCG','TTA','CGT']],\n",
        "            2:[ ['CTG','TTG','ATG','CTG','ATT','ATG','TGA'],['TGT','TGA','TGC','TGA','TTA','TGT'],\n",
        "                ['GTT','GAT','GCT','GAT','TAT','GTG'],['TCA','CAT','AAT','CAG','CAT','CAA','CAG'],\n",
        "                ['CAC','ATA','ATC','AGC','ATC','AAC'],['ACA','TAA','TCA','GCA','TCA','ACA']]}\n",
        "        \n",
        "        res_traducao_standard_ATG={\n",
        "            1:['T_RFSQ','RNDLAS','VTI_PA','SWLNRY','AG_IVT','LAKSLR'],\n",
        "            2:['LLMLIM_', 'C_C_LC', 'VDADYV', 'SHNQHQQ', 'HIISIN', 'T_SAST']}\n",
        "        \n",
        "        res_traducao_standard_CTG={\n",
        "            1:['T_RFSQ', 'RNDLAS', 'VTI_PA', 'SWLNRY', 'AG_IVT', 'MAKSLR'],\n",
        "            2:['MLMLIM_','C_C_LC','VDADYV','SHNQHQQ','HIISIN','T_SAST']}\n",
        "\n",
        "        res_traducao_mito_ATT={\n",
        "            1:['T_RFSQ', 'RNDLAS', 'VTM_PA', 'SWLNRY', 'AG_IVT', 'LAKSLR'],\n",
        "            2:['LLMLMMW','CWCWLC','VDADYV','SHNQHQQ','HMISIN','T_SAST']\n",
        "        }\n",
        "\n",
        "        res_traducao_bacteria_TTG={\n",
        "            1:['T_RFSQ', 'RNDLAS', 'VTI_PA', 'SWLNRY', 'AG_IVT', 'LAKSLR'],\n",
        "            2:['LMMLIM_', 'C_C_LC', 'VDADYV', 'SHNQHQQ', 'HIISIN', 'T_SAST']\n",
        "        }\n",
        "        \n",
        "        for I in rfs_codoes:\n",
        "            self.assertEqual(traducao_rf(rfs_codoes[I]),res_traducao_standard_ATG[I]) #resultado tabela standard start codon ATG\n",
        "            self.assertEqual(traducao_rf(rfs_codoes[I],start_codon='CTG'),res_traducao_standard_CTG[I]) #resultado tabela standard start codon CTG\n",
        "            self.assertEqual(traducao_rf(rfs_codoes[I],genetic_code='Vertebrate Mitochondrial',start_codon='att'),res_traducao_mito_ATT[I]) #resultado tabela mito start codon ATT\n",
        "            self.assertEqual(traducao_rf(rfs_codoes[I],genetic_code='Bacterial',start_codon='TTG'),res_traducao_bacteria_TTG[I]) #resultado tabela bacteria start codon TTG\n",
        "    \n",
        "    def test_find_prots(self):\n",
        "        seqs_aa={\n",
        "            1:['T_RFSQ', 'RNDLAS', 'VTI_PA', 'SWLNRY', 'AG_IVT', 'LAKSLR'],\n",
        "            2:['LMMLIM_', 'C_C_LC', 'VDADYV', 'SHNQHQQ', 'HIISIN', 'T_SAST'],\n",
        "            3:['CMCCLCIV_SWLASMIFTADS_MT','VDAMADYA_','SHNQHQQ', 'HIISIN']}\n",
        "                    \n",
        "        prots={\n",
        "            1:[],\n",
        "            2:[['MMLIM']],\n",
        "            3:[['MCCLCIV','MIFTADS'],['MADYA']]}\n",
        "\n",
        "        for I in seqs_aa:\n",
        "            for seq,res in zip(seqs_aa[I],prots[I]):\n",
        "                self.assertEqual(find_prots(seq),res)\n",
        "\n",
        "    def test_all_prots(self):\n",
        "        seqs={\n",
        "            1:'ACGTAACGATTTAGCCAGCT', \n",
        "            2:'CTGTTGATGCTGATTATGTGa',\n",
        "            3:'ACCTGAatgctagA',\n",
        "            4:'CTGTTGATGCTGATTATGTGACTGTTGATGCTGATTATGTGA' }# o 4 possui a mesma proteina reptida 2 vezes\n",
        "        \n",
        "        res={\n",
        "            1:set() ,\n",
        "            2:{'MLIM'} ,\n",
        "            3: set(),\n",
        "            4:{'MLIM'}}\n",
        "        \n",
        "        for I in seqs:\n",
        "            self.assertEqual(all_prots(seqs[I]),res[I])\n",
        "\n",
        "suite = unittest.TestLoader().loadTestsFromTestCase(Test_ORFs)\n",
        "unittest.TextTestRunner(verbosity=3).run(suite)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "E6uw5EbfzHog"
      },
      "source": [
        "<!-- LTeX: language=pt -->\n",
        "## Tarefa 4 - Alinhamento através de programação dinâmica/ recursividade\n",
        "\n",
        "<div align='justify'>\n",
        "\n",
        "Na tarefa da semana 4, é proposto a resolução do alinhamento através de programação dinâmica/ recursividade.<br>\n",
        "A programação dinâmica e a recursividade são técnicas fundamentais na computação, oferecendo abordagens poderosas para a resolução eficiente de problemas complexos. Ambas desempenham papéis cruciais na elaboração de algoritmos eficazes, permitindo aos programadores enfrentar desafios computacionais de maneira elegante e eficiente.<br>\n",
        "A recursividade é um conceito central, onde uma função se chama a si mesma para resolver subproblemas menores. Essa técnica espelha a estrutura de muitos problemas reais, facilitando a representação e solução de maneira natural. Ao dividir um problema grande em instâncias menores e mais gerenciáveis, a recursividade proporciona clareza conceitual e modularidade no código. No entanto, é essencial otimizar as chamadas recursivas para evitar custos excessivos de tempo e memória.<br>\n",
        "Já a programação dinâmica é uma técnica de otimização que visa resolver subproblemas uma única vez e armazenar as suas soluções para reutilização. Ao invés de resolver um problema repetidamente, a programação dinâmica economiza recursos computacionais, resultando em algoritmos mais rápidos e eficientes. A ideia central é construir uma tabela ou matriz para armazenar as soluções dos subproblemas, evitando redundâncias e acelerando a computação.<br>\n",
        "No entanto, é importante notar que, embora poderosas, essas técnicas também têm limitações. A recursividade, se não controlada adequadamente, pode levar a chamadas excessivas, enquanto que por outro lado, a programação dinâmica, embora eficiente, não recalcula o mesmo problema e armazena todos os subproblemas numa estrutura de dados.<br>\n",
        "\n",
        "Neste algoritmo, construiu-se a função score_basic, que utiliza recursão para calcular o score de alinhamento básico entre duas sequências. De seguida, defeniu-se a função memoize, que armazena os resultados previamente calculados num dicionário de memória Sempre que a função memoizada é chamada com determinados argumentos, verifica-se se esses argumentos já foram calculados anteriormente. Se sim, o resultado armazenado é retornado; caso contrário, a função original é chamada para calcular o resultado, que é então armazenado na memória para uso futuro. Porúltimo, a função score, que utiliza recursão para calcular o score de alinhamento entre duas sequências.<br>\n",
        "</div>"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 87,
      "metadata": {},
      "outputs": [
        {
          "data": {
            "text/plain": [
              "-2"
            ]
          },
          "execution_count": 87,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "#Sem memoizing\n",
        "def score_basic(s1 :str, s2 : str, g : int= -4, match : int = 2, mismatch : int = -1) -> int:\n",
        "    \"\"\"\n",
        "    Calcula o score de alinhamento básico entre duas sequências utilizando a recursão.\n",
        "        \n",
        "    Parameters\n",
        "    ----------\n",
        "    s1 : str\n",
        "      Primeira sequência.\n",
        "\n",
        "    s2 : str\n",
        "      Segunda sequência.\n",
        "\n",
        "    g : int\n",
        "      Valor a ser utilizado para penalizar os espaçamentos. Por padrão, considera-se o valor de penalização como -4.\n",
        "\n",
        "    match : int\n",
        "      Valor a ser utilizado quando os caracteres são iguais. Por padrão, é 2.\n",
        "\n",
        "    mismatch : int\n",
        "      Valor a ser utilizado quando os caracteres são diferentes. Por padrão, é -1.\n",
        "\n",
        "    Returns\n",
        "    -------\n",
        "    int\n",
        "      O score de alinhamento básico entre as duas sequências.\n",
        "\n",
        "    Raises\n",
        "    ------\n",
        "    AssetionError\n",
        "      Gap penalty tem de ser valor inteiro e negativo.\n",
        "      Mismatch tem de ser valor inteiro e negativo.\n",
        "      Match tem de ser valor inteiro e positiv\n",
        "    \"\"\"\n",
        "    assert g <0 and isinstance(g,int) , \"Gap penalty tem de ser valor inteiro e negativo \"\n",
        "    assert mismatch <0 and isinstance(mismatch,int) , \"Mismatch tem de ser valor inteiro e negativo\"\n",
        "    assert match > 0 and isinstance(match,int) , \"Match tem de ser valor inteiro e positivo\"\n",
        "    \n",
        "    subst = lambda X, Y: match if X == Y else mismatch\n",
        "    if s1 and s2:\n",
        "        return max(\n",
        "            score_basic(s1[:-1], s2[:-1]) + subst(s1[-1], s2[-1]),\n",
        "            score_basic(s1[:-1], s2) + g,\n",
        "            score_basic(s1, s2[:-1]) + g\n",
        "            )\n",
        "    else: return max(len(s1), len(s2)) * g\n",
        "\n",
        "score_basic(\"HGWAG\",\"PHSWG\")"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 88,
      "metadata": {},
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "                    Alinhamento recursivo de s1: 'H' com s2: 'P' com indent: 4\n",
            "                    Alinhamento recursivo de s1: 'H' com s2: 'PH' com indent: 4\n",
            "                    Alinhamento recursivo de s1: 'HG' com s2: 'P' com indent: 4\n",
            "               Alinhamento recursivo de s1: 'HG' com s2: 'PH' com indent: 3\n",
            "                    Alinhamento recursivo de s1: 'H' com s2: 'PHS' com indent: 4\n",
            "               Alinhamento recursivo de s1: 'HG' com s2: 'PHS' com indent: 3\n",
            "                    Alinhamento recursivo de s1: 'HGW' com s2: 'P' com indent: 4\n",
            "               Alinhamento recursivo de s1: 'HGW' com s2: 'PH' com indent: 3\n",
            "          Alinhamento recursivo de s1: 'HGW' com s2: 'PHS' com indent: 2\n",
            "                    Alinhamento recursivo de s1: 'H' com s2: 'PHSW' com indent: 4\n",
            "               Alinhamento recursivo de s1: 'HG' com s2: 'PHSW' com indent: 3\n",
            "          Alinhamento recursivo de s1: 'HGW' com s2: 'PHSW' com indent: 2\n",
            "                    Alinhamento recursivo de s1: 'HGWA' com s2: 'P' com indent: 4\n",
            "               Alinhamento recursivo de s1: 'HGWA' com s2: 'PH' com indent: 3\n",
            "          Alinhamento recursivo de s1: 'HGWA' com s2: 'PHS' com indent: 2\n",
            "     Alinhamento recursivo de s1: 'HGWA' com s2: 'PHSW' com indent: 1\n",
            "                    Alinhamento recursivo de s1: 'H' com s2: 'PHSWG' com indent: 4\n",
            "               Alinhamento recursivo de s1: 'HG' com s2: 'PHSWG' com indent: 3\n",
            "          Alinhamento recursivo de s1: 'HGW' com s2: 'PHSWG' com indent: 2\n",
            "     Alinhamento recursivo de s1: 'HGWA' com s2: 'PHSWG' com indent: 1\n",
            "                    Alinhamento recursivo de s1: 'HGWAG' com s2: 'P' com indent: 4\n",
            "               Alinhamento recursivo de s1: 'HGWAG' com s2: 'PH' com indent: 3\n",
            "          Alinhamento recursivo de s1: 'HGWAG' com s2: 'PHS' com indent: 2\n",
            "     Alinhamento recursivo de s1: 'HGWAG' com s2: 'PHSW' com indent: 1\n",
            "Alinhamento recursivo de s1: 'HGWAG' com s2: 'PHSWG' com indent: 0\n"
          ]
        },
        {
          "data": {
            "text/plain": [
              "-2"
            ]
          },
          "execution_count": 88,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "#Com memoizing usando um decorador\n",
        "def memoize(func):\n",
        "    \"\"\"\n",
        "    Memoiza uma função, armazenando os resultados previamente calculados para evitar recálculos.\n",
        "        \n",
        "    Parameters\n",
        "    ----------\n",
        "    func : function\n",
        "      A função a ser memoizada.\n",
        "\n",
        "    Returns\n",
        "    -------\n",
        "    function\n",
        "      A função memoizada.\n",
        "    \"\"\"\n",
        "    memoria = {}\n",
        "    def organizador(*positional_args, **keyword_args):\n",
        "        if positional_args not in memoria:\n",
        "            memoria[positional_args] = func(*positional_args, **keyword_args)\n",
        "        return memoria[positional_args]\n",
        "    return organizador\n",
        "\n",
        "@memoize\n",
        "def score_memo(s1 : str, s2 : str, g : int = -4, match : int=2, mismatch : int = -1, indent : int =0, check_indent : bool = False) -> int:\n",
        "    \"\"\"\n",
        "    Calcula o score de alinhamento entre duas sequências utilizando a recursão.\n",
        "        \n",
        "    Parameters\n",
        "    ----------\n",
        "    s1 : str\n",
        "      Primeira sequência.\n",
        "\n",
        "    s2 : str\n",
        "      Segunda sequência.\n",
        "\n",
        "    g : int\n",
        "      Valor a ser utilizado para penalizar os espaçamentos. Por padrão, considera-se o valor de penalização como -4.\n",
        "\n",
        "    match : int\n",
        "      Valor a ser utilizado quando os caracteres são iguais. Por padrão, é 2.\n",
        "\n",
        "    mismatch : int\n",
        "      Valor a ser utilizado quando os caracteres são diferentes. Por padrão, é -1.\n",
        "\n",
        "    indent : int\n",
        "      Nível de indentação para exibição de informações (usado apenas se check_indent=True). Por padrão, é 0.\n",
        "\n",
        "    check_indent : bool\n",
        "      Indica se deve imprimir informações de indentação durante o processo de recursão. Por padrão, é False.\n",
        "\n",
        "    Returns\n",
        "    -------\n",
        "    int\n",
        "      O score de alinhamento entre as sequências.\n",
        "\n",
        "    Raises\n",
        "    ------\n",
        "    AssetionError\n",
        "      Gap penalty tem de ser valor inteiro e negativo.\n",
        "      Mismatch tem de ser valor inteiro e negativo.\n",
        "      Match tem de ser valor inteiro e positivo.\n",
        "    \"\"\"\n",
        "    assert g <0 and isinstance(g,int) , \"Gap penalty tem de ser valor inteiro e negativo \"\n",
        "    assert mismatch <0 and isinstance(mismatch,int) , \"Mismatch tem de ser valor inteiro e negativo\"\n",
        "    assert match > 0 and isinstance(match,int) , \"Match tem de ser valor inteiro e positivo\"\n",
        "    subst = lambda X, Y: match if X == Y else mismatch\n",
        "\n",
        "    \n",
        "    if s1 and s2:\n",
        "        val = max(\n",
        "            score_memo(s1[:-1], s2[:-1], g, match, mismatch, indent=indent + 1, check_indent=check_indent) + subst(s1[-1], s2[-1]),\n",
        "            score_memo(s1[:-1], s2,      g, match, mismatch, indent=indent + 1, check_indent=check_indent) + g,\n",
        "            score_memo(s1,      s2[:-1], g, match, mismatch, indent=indent + 1, check_indent=check_indent) + g\n",
        "        )\n",
        "        if check_indent==True:\n",
        "            print(\"     \" * indent + f\"Alinhamento recursivo de s1: '{s1}' com s2: '{s2}' com indent: {indent}\")\n",
        "        return val\n",
        "    else:\n",
        "        return max(len(s1), len(s2)) * g\n",
        "    \n",
        "score_memo(\"HGWAG\",\"PHSWG\", check_indent=True)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "### Testes de unidade"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 89,
      "metadata": {
        "id": "-rgnERFA1LKP"
      },
      "outputs": [
        {
          "name": "stderr",
          "output_type": "stream",
          "text": [
            "test_score_basic_gap_valor_positivo (__main__.TestAlinhamentoRecursivo.test_score_basic_gap_valor_positivo) ... ok\n",
            "test_score_basic_gap_valor_real (__main__.TestAlinhamentoRecursivo.test_score_basic_gap_valor_real) ... ok\n",
            "test_score_basic_match_valor_negativo (__main__.TestAlinhamentoRecursivo.test_score_basic_match_valor_negativo) ... ok\n",
            "test_score_basic_match_valor_real (__main__.TestAlinhamentoRecursivo.test_score_basic_match_valor_real) ... ok\n",
            "test_score_basic_mismatch_valor_positivo (__main__.TestAlinhamentoRecursivo.test_score_basic_mismatch_valor_positivo) ... ok\n",
            "test_score_basic_mismatch_valor_real (__main__.TestAlinhamentoRecursivo.test_score_basic_mismatch_valor_real) ... ok\n",
            "test_validar_score_basic (__main__.TestAlinhamentoRecursivo.test_validar_score_basic) ... ok\n",
            "\n",
            "----------------------------------------------------------------------\n",
            "Ran 7 tests in 0.035s\n",
            "\n",
            "OK\n"
          ]
        },
        {
          "data": {
            "text/plain": [
              "<unittest.runner.TextTestResult run=7 errors=0 failures=0>"
            ]
          },
          "execution_count": 89,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "import unittest\n",
        "\n",
        "class TestAlinhamentoRecursivo(unittest.TestCase):\n",
        "\n",
        "    def test_score_basic_gap_valor_positivo(self):\n",
        "        with self.assertRaises(AssertionError):\n",
        "            score_basic(\"HGWAG\",\"PHSWG\",g=9)\n",
        "    \n",
        "    def test_score_basic_gap_valor_real(self):\n",
        "        with self.assertRaises(AssertionError):\n",
        "            score_basic(\"HGWAG\",\"PHSWG\",g=-2.5)\n",
        "\n",
        "    def test_score_basic_match_valor_negativo(self):\n",
        "        with self.assertRaises(AssertionError):\n",
        "            score_basic(\"HGWAG\",\"PHSWG\",match=-3)\n",
        "\n",
        "    def test_score_basic_match_valor_real(self):\n",
        "        with self.assertRaises(AssertionError):\n",
        "            score_basic(\"HGWAG\",\"PHSWG\",match=3.2)\n",
        "\n",
        "    def test_score_basic_mismatch_valor_positivo(self):\n",
        "        with self.assertRaises(AssertionError):\n",
        "            score_basic(\"HGWAG\",\"PHSWG\",mismatch=3)\n",
        "\n",
        "    def test_score_basic_mismatch_valor_real(self):\n",
        "        with self.assertRaises(AssertionError):\n",
        "            score_basic(\"HGWAG\",\"PHSWG\",mismatch=-1.5)\n",
        "\n",
        "    def test_validar_score_basic(self):\n",
        "        self.assertEqual(score_basic(\"HGWAG\",\"PHSWG\"),-2)\n",
        "\n",
        "suite = unittest.TestLoader().loadTestsFromTestCase(TestAlinhamentoRecursivo)\n",
        "unittest.TextTestRunner(verbosity=3).run(suite)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "0ShqoNyHzRqo"
      },
      "source": [
        "<!-- LTeX: language=pt -->\n",
        "## Tarefa 5 - Algoritmo de Needleman Wunsch\n",
        "\n",
        "<div align='justify'>\n",
        "\n",
        "Nesta tarefa, desenvolvemos o algoritmo Needleman-Wunsch, que retorna a matriz de pontuação, a matriz de rastreamento, o score do alinhamento e as sequências alinhadas.\n",
        "\n",
        "No inicio criamos uma função validar_prot(seq), esta desempenha um papel crucial ao garantir que uma sequência de aminoácidos esteja no formato adequado. Essa função verifica se a sequência é uma string não vazia contendo apenas aminoácidos válidos, assegurando a integridade dos dados de entrada.\n",
        "\n",
        "De seguida fez-se a função formatar(x) tem como função formatar valores, sejam eles inteiros ou strings. Essa formatação visa garantir que os valores sejam exibidos com pelo menos 3 dígitos.\n",
        "\n",
        "A função print_matrix(S1, S2, M) desempenha um papel crucial na visualização do processo de alinhamento. Esta imprime uma matriz formatada, exibindo as duas sequências (S1 e S2) e a matriz associada (M).\n",
        "\n",
        "Para avaliar a similaridade entre nucleotídeos ou aminoácidos, criou-se a função score_sub_acid_nuc(x1, x2, match, mismatch). Esta função calcula o score de substituição, retornando o valor de correspondência (match) se os elementos forem iguais ou o valor de não correspondência (mismatch) se forem diferentes.\n",
        "\n",
        "Para o alinhamento de proteínas, utilizou-se a função score_subst_prot(nome_matriz, aa1, aa2). Esta função lê uma matriz de substituição de um ficheiro específico e retorna o score correspondente ao alinhamento de dois aminoácidos específicos.\n",
        "\n",
        "Criou-se a função reconstrucao(seq1, seq2, trace, matrizes=True) para reconstruir as sequências alinhadas a partir da matriz de rastreamento (trace).\n",
        "\n",
        "Por fim, a função  needleman_wunsch(seq1, seq2, seq_tipo, gap, matriz, match, mismatch, matrizes=True) implementa o algoritmo Needleman-Wunsch. realizando o alinhamento global de duas sequências, e oferecendo flexibilidade para considerar diferentes parâmetros, como penalização por espaçamento (gap), matriz de substituição (para proteínas) e valores de correspondência/mismatch (para ácidos nucleicos). Ao ser executada, essa função retorna o score do alinhamento e as sequências alinhadas\n",
        "</div>"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 90,
      "metadata": {},
      "outputs": [],
      "source": [
        "def validar_prot(seq : str)->bool:\n",
        "  \"\"\"\n",
        "  Esta função recebe uma sequência de aminoácidos e realiza as seguintes operações:\n",
        "      1. Verifica se a sequência é do tipo string.\n",
        "      2. Verifica se a sequência não é vazia.\n",
        "      3. Verifica se a sequência contém apenas os aminoácidos permitidos (A, C, D, E, F, G, H, I, K, L, M, N, P, Q, R, S, T, V, W, Y, _).\n",
        "\n",
        "  Parameters\n",
        "  ----------\n",
        "  seq : str\n",
        "    A sequência de aminoácidos que será validada.\n",
        "\n",
        "  Returns\n",
        "  -------\n",
        "  bool\n",
        "    Retorna True se a sequência de aminoacidos for válida, caso contrário, retorna False.\n",
        "\n",
        "  Raises\n",
        "  ------\n",
        "  AssertionError\n",
        "    - Se a sequência não for fornecida no formato de string.\n",
        "    - Se a sequência fornecida for vazia.\n",
        "  \"\"\"\n",
        "  assert type(seq)==str,'A sequência não foi fornecida em formato de string'\n",
        "  assert len(seq) !=0 ,'Não foi fornecida nenhuma sequência'\n",
        "  lista_aminoacidos = ['A','C','D','E','F','G','H','I','K','L','M','N','P','Q','R','S','T','V','W','Y','_']\n",
        "  for aa in seq.upper():\n",
        "      if aa not in lista_aminoacidos:\n",
        "          return False\n",
        "    \n",
        "  return True\n",
        "\n",
        "def formatar(x : int or str) -> str:\n",
        "  \"\"\"\n",
        "  Esta função recebe um valor x e realiza as seguintes operações:\n",
        "    1. Se x for do tipo inteiro, formata o valor como uma string com pelo menos 3 dígitos, preenchendo com espaços à esquerda se necessário.\n",
        "    2. Se x não for do tipo inteiro, formata o valor como uma string com pelo menos 3 caracteres, preenchendo com espaços à esquerda se necessário.\n",
        "\n",
        "  Parameters\n",
        "  ----------\n",
        "  x : int or str\n",
        "    O valor que será formatado.\n",
        "\n",
        "  Returns\n",
        "  -------\n",
        "  str\n",
        "    O valor formatado.\n",
        "\n",
        "  Raises\n",
        "  ------\n",
        "  ValueError\n",
        "    Se x não for do tipo inteiro nem string.\n",
        "  \"\"\"\n",
        "  if type(x) is int:\n",
        "      return f\"{x:>3d}\"\n",
        "  else:\n",
        "      return f\"{x:>3}\"\n",
        "    \n",
        "def print_matrix(S1 : str, S2 : str, M : list) -> None:\n",
        "  \"\"\"\n",
        "  Esta função recebe duas sequências (S1 e S2) e uma matriz (M) e realiza as seguintes operações:\n",
        "    1. Imprime uma representação formatada da matriz.\n",
        "    2. Utiliza a função 'formatar' para formatar os valores da matriz.\n",
        "\n",
        "  Parameters\n",
        "  ----------\n",
        "  S1 : str\n",
        "    A primeira sequência.\n",
        "\n",
        "  S2 : str\n",
        "    A segunda sequência.\n",
        "\n",
        "  M : list\n",
        "    A matriz a ser impressa.\n",
        "\n",
        "  Returns\n",
        "  -------\n",
        "  None\n",
        "    A função imprime a matriz formatada.\n",
        "\n",
        "  Raises\n",
        "  ------\n",
        "  ValueError\n",
        "    Se S1 ou S2 não forem fornecidos como strings.\n",
        "    Se M não for uma lista válida.\n",
        "  \"\"\"\n",
        "  print(*list(\" \" + S1), sep=\"   \")\n",
        "  for x2, L in zip(S2,M): #x2 caracter que vem da string S2\n",
        "      LL=[formatar(x) for x in L]\n",
        "      print(x2,*LL)\n",
        "  print()\n",
        "\n",
        "def score_sub_acid_nuc(x1 : str, x2 : str, match : int, mismatch : int) -> int:\n",
        "  \"\"\"\n",
        "  Esta função recebe dois caracteres x1 e x2, representando nucleotídos ou aminoácidos, e realiza as seguintes operações:\n",
        "    - Retorna o valor de correspondência (match) se x1 e x2 são iguais.\n",
        "    - Retorna o valor de não correspondência (mismatch) se x1 e x2 são diferentes.\n",
        "\n",
        "  Parameters\n",
        "  ----------\n",
        "  x1 : str\n",
        "    O primeiro caractere (nucleotídeo ou aminoácido).\n",
        "\n",
        "  x2 : str\n",
        "    O segundo caractere (nucleotídeo ou aminoácido).\n",
        "\n",
        "  match : int\n",
        "    O valor atribuído quando x1 e x2 são iguais. O valor padrão para match é 2.\n",
        "\n",
        "  mismatch : int\n",
        "    O valor atribuído quando x1 e x2 são diferentes. O valor padrão para mismatch é -1.\n",
        "\n",
        "  Returns\n",
        "  -------\n",
        "  int\n",
        "    O valor de correspondência (match) se x1 e x2 são iguais, caso contrário, o valor de não correspondência (mismatch).\n",
        "  \"\"\"\n",
        "  if x1==x2:return match\n",
        "  else: return mismatch\n",
        "\n",
        "def score_subst_prot(nome_matriz : str, aa1 : str, aa2 : str) -> int:\n",
        "  \"\"\"\n",
        "  Esta função abre e lê um destes ficheiros de texto: \"BLOSSOM62.txt\", \"BLOSSOM80.txt\", \"PAM30.txt\", \"PAM70.txt\" \n",
        "  retirando a matriz de substituição do ficheiro como uma matriz bidimensional.\n",
        "  Depois navega na matriz de substituição obtida e retorna o score correspondente ao alinhamento de dois dos seguintes caracteres: \n",
        "  'A','C','D','E','F','G','H','I','K','L','M','N','P','Q','R','S','T','V','W','Y','_',\n",
        "  sendo que as letras representam os aminoácidos e o caracter '_' representa o codão stop.\n",
        "    \n",
        "  Parameters\n",
        "  ----------\n",
        "  nome_matriz : str\n",
        "    Nome da matriz de substituição que se pretende que seja lida e utilizada para fornecer os scores de substituição\n",
        "\n",
        "  aa1 : str\n",
        "    Aminoácido que vai ser procurado ao longo da primeira coluna da matriz de substituição\n",
        "\n",
        "  aa2 : str\n",
        "    Aminoácido que vai ser procurado ao longo da primeira linha da matriz de substituição\n",
        "\n",
        "  Returns\n",
        "  -------\n",
        "  score : int\n",
        "    Score obtido para o alinhamento dos dois aminoácidos na matriz de substituição\n",
        "\n",
        "  Raises\n",
        "  ------\n",
        "  AssertionError\n",
        "    - Quando o nome da matriz fornecido não corresponde a uma das matrizes aceites pela função:\n",
        "    \"BLOSSOM62\", \"BLOSSOM80\", \"PAM30\", \"PAM70\"\n",
        "    - Quando o caracter inserido correspondente ao 'aa1' não é válido como aminoácido ou codão stop\n",
        "    - Quando o caracter inserido correspondente ao 'aa2' não é válido como aminoácido ou codão stop\n",
        "  \"\"\"\n",
        "  assert nome_matriz.upper() in [\"BLOSSOM62\", \"BLOSSOM80\", \"PAM30\", \"PAM70\"],\"A matriz de substituição escolhida é inválida, apenas aceita as matrizes 'BLOSSOM62', 'BLOSSOM80', 'PAM30', 'PAM70'\"\n",
        "  with open(nome_matriz.upper()+\".txt\", \"r\") as file:\n",
        "      matriz = []\n",
        "      for line in file:\n",
        "          line = line.strip()\n",
        "          linha = []\n",
        "          valor = \"\"\n",
        "          for elem in line:\n",
        "              if elem == \" \":\n",
        "                  if len(valor) != 0:\n",
        "                      linha.append(valor)\n",
        "                      valor = \"\"\n",
        "              else:\n",
        "                  valor += elem\n",
        "          linha.append(valor)\n",
        "          matriz.append(linha)\n",
        "  aa1, aa2 = aa1.upper(), aa2.upper()\n",
        "  lista_aminoacidos = ['A','R','N','D','C','Q','E','G','H','I','L','K','M','F','P','S','T','W','Y','V','B','J','Z','X','_']\n",
        "  assert aa1 in lista_aminoacidos,f\"O caracter {aa1} não é válido como aminoácido ou codão stop\"\n",
        "  assert aa2 in lista_aminoacidos,f\"O caracter {aa2} não é válido como aminoácido ou codão stop\"\n",
        "  coluna, linha = 0, 0\n",
        "  for i in range(1,len(matriz)):\n",
        "      if aa1 == matriz[i][0]:\n",
        "          linha = i\n",
        "          break\n",
        "  for pos, elem in enumerate(matriz[0]):\n",
        "      if elem == aa2:\n",
        "          coluna = pos\n",
        "          break\n",
        "  score = matriz[linha][coluna]\n",
        "  return int(score)\n",
        "\n",
        "def reconstrucao(seq1 : str, seq2 : str, trace : list[list],matrizes=True) -> tuple[str,str]:\n",
        "  \"\"\"\n",
        "  Esta função recebe duas sequências seq1 e seq2, juntamente com uma matriz de rastreamento trace,\n",
        "  e realiza as seguintes operações:\n",
        "    - Reconstrói as sequências alinhadas a partir da matriz de rastreamento.\n",
        "\n",
        "  Parameters\n",
        "  ----------\n",
        "  seq1 : str\n",
        "    A primeira sequência.\n",
        "\n",
        "  seq2 : str\n",
        "    A segunda sequência.\n",
        "\n",
        "  trace : list\n",
        "    A matriz de rastreamento utilizada para alinhar as sequências.\n",
        "  \n",
        "  matrizes: bool\n",
        "    Indica se se pretende realizar o print das matrizes trace, score e das sequências alinhadas\n",
        "    \n",
        "  Returns\n",
        "  -------\n",
        "  tuple of str\n",
        "    Um tuplo contendo as sequências alinhadas (aligned_seq1, aligned_seq2).\n",
        "  \"\"\"\n",
        "  aligned_seq1 = ''\n",
        "  aligned_seq2 = ''\n",
        "  linha=len(seq1)-1\n",
        "  coluna=len(seq2)-1\n",
        "\n",
        "  while trace[linha][coluna]!=0:\n",
        "      if trace[linha][coluna] == '↖':\n",
        "          aligned_seq1 = seq1[linha] + aligned_seq1\n",
        "          aligned_seq2 = seq2[coluna] + aligned_seq2\n",
        "          linha -= 1\n",
        "          coluna -= 1\n",
        "      elif trace[linha][coluna] == '↑':\n",
        "          aligned_seq1 = seq1[linha] + aligned_seq1\n",
        "          aligned_seq2 = '-' + aligned_seq2\n",
        "          linha -= 1\n",
        "      elif trace[linha][coluna] == '←':\n",
        "          aligned_seq1 = '-' + aligned_seq1\n",
        "          aligned_seq2 = seq2[coluna] + aligned_seq2\n",
        "          coluna-= 1\n",
        "  \n",
        "  if matrizes:\n",
        "    print(aligned_seq1,aligned_seq2,sep='\\n')\n",
        "  return (aligned_seq1,aligned_seq2)\n",
        "\n",
        "def needleman_wunsch(seq1 : str, seq2 : str, seq_tipo : str, gap : int=-4, matriz : str='Blossom62', match : int=2, mismatch : int=-1, matrizes=True ):\n",
        "  \"\"\"\n",
        "  Realiza o alinhamento global de duas sequências recorrendo o algoritmo Needleman-Wunsch.\n",
        "\n",
        "  Parameters\n",
        "  ----------\n",
        "  seq1 : str\n",
        "    Primeira sequência\n",
        "\n",
        "  seq2 : str\n",
        "    Segunda sequência\n",
        "\n",
        "  seq_tipo : str\n",
        "    Identifica o tipo das sequências que se pretende alinhar\n",
        "\n",
        "  gap : int\n",
        "    Valor a utilizar para penalizar os espaçamentos. Por padrão considera-se o valor de penalização como -4\n",
        "\n",
        "  matriz : str\n",
        "    Matriz de substituição de aminoacidos a utilizar para realizar o alinhamento de proteínas\n",
        "\n",
        "  match : int\n",
        "    Valor a utilizar para quando as duas bases nucleicas são iguais. Por default é 2. Apenas para o alinhamento de DNA/RNA\n",
        "\n",
        "  mismatch : int\n",
        "    Valor a utilizar para quando as duas bases nucleicas são diferentes. Por default é -1. Apenas para o alinhamento de DNA/RNA\n",
        "\n",
        "  matrizes : bool\n",
        "    Indica se se prende realizar o print das matrizes de score e de traceback bem como as sequências alinhadas\n",
        "\n",
        "  Returns\n",
        "  ----------\n",
        "  Tuple[str,[Tuple[str,str]]\n",
        "    Devolve um tuplo com o score com um tuplo do alinhamento ótimo de cada sequência\n",
        "\n",
        "  Raises\n",
        "  ------\n",
        "  AssertionError\n",
        "     - Se seq1 e seq2 não forem do tipo string\n",
        "     - Se seq 1 ou seq2 forem strings vazias\n",
        "     - Se seq_tipo não for 'DNA', 'RNA' ou 'PROTEIN'.\n",
        "     - Se uma das sequencias fornecidas não é um acido nucleico válido quando seq_tipo assume o valor DNA ou RNA.\n",
        "     - Se seq_tipo for 'PROTEIN' e as sequências não forem proteínas válidas.\n",
        "  \"\"\"\n",
        "  assert type(seq1)==str and type(seq2)==str\n",
        "  assert seq_tipo.upper() in ['DNA','RNA','PROTEIN'], 'O tipo de sequência fornecido não é valido, apenas pode assumir o valor de DNA, RNA ou protein'\n",
        "    \n",
        "  if seq_tipo.upper()=='DNA' or seq_tipo.upper()=='RNA':\n",
        "      assert tipo_seq(seq1) in ['DNA','RNA'], 'A sequencia 1 não é um acido nucleico'\n",
        "      assert tipo_seq(seq2) in ['DNA','RNA'], 'A sequencia 2 não é um acido nucleico'\n",
        "      assert tipo_seq(seq1)==tipo_seq(seq2), 'As cadeias fornecidas não são do mesmo tipo'\n",
        "\n",
        "  else:\n",
        "      assert validar_prot(seq1), 'A sequencia 1 não é uma proteina'\n",
        "      assert validar_prot(seq2), 'A sequencia 2 não é uma proteina'\n",
        "\n",
        "  seq1='-'+seq1\n",
        "  seq2='-'+seq2\n",
        "  nrows = len(seq1)\n",
        "  ncols = len(seq2)\n",
        "\n",
        "  score_matrix=[[0]*ncols for linhas in range(nrows)] # iniciar a matriz score apenas com 0\n",
        "  score_matrix[0]=[c*gap for c in range(ncols)] #prenchimento da primeira linha da matriz score\n",
        "  for linha in range(1, nrows):score_matrix[linha][0] = linha * gap # preenchimento da primeira coluna da matriz score\n",
        "\n",
        "  traceback_matrix = [[0] * ncols for linhas in range(nrows)] # iniciar a matriz traceback com 0\n",
        "  traceback_matrix[0] =[0 if col==0 else '←' for col in range(ncols)] # prenchimento da primeira linha da matriz traceback\n",
        "  for linha in range(1,nrows): traceback_matrix[linha][0]='↑' # preenchimento da primeira coluna da matriz traceback\n",
        "\n",
        "  if seq_tipo.upper()=='DNA' or seq_tipo.upper()=='RNA': #alinhamento de acidos nucleicos\n",
        "    for linha in range(1, nrows):\n",
        "      for coluna in range(1, ncols):\n",
        "        diagonal = score_matrix[linha - 1][coluna - 1] + score_sub_acid_nuc(seq1[linha],seq2[coluna],match,mismatch)\n",
        "        cima = score_matrix[linha - 1][coluna] + gap\n",
        "        esquerda = score_matrix[linha][coluna - 1] + gap\n",
        "\n",
        "        max_score = max(diagonal, esquerda, cima)\n",
        "        score_matrix[linha][coluna] = max_score\n",
        "\n",
        "        if max_score == diagonal: traceback_matrix[linha][coluna] = '↖'\n",
        "        elif max_score == cima: traceback_matrix[linha][coluna] = '↑'\n",
        "        elif max_score == esquerda: traceback_matrix[linha][coluna] = '←'\n",
        "\n",
        "  else: # alinhamento de proteinas\n",
        "    for linha in range(1, nrows):\n",
        "      for coluna in range(1, ncols):\n",
        "        diagonal = score_matrix[linha - 1][coluna - 1] + score_subst_prot(matriz,seq1[linha],seq2[coluna])\n",
        "        cima = score_matrix[linha - 1][coluna] + gap\n",
        "        esquerda = score_matrix[linha][coluna - 1] + gap\n",
        "\n",
        "        max_score = max(diagonal, esquerda, cima)\n",
        "        score_matrix[linha][coluna] = max_score\n",
        "\n",
        "        if max_score == diagonal: traceback_matrix[linha][coluna] = '↖'\n",
        "        elif max_score == cima: traceback_matrix[linha][coluna] = '↑'\n",
        "        elif max_score == esquerda: traceback_matrix[linha][coluna] = '←'\n",
        "\n",
        "  if matrizes:\n",
        "      print(\"Matriz de Pontuação:\")\n",
        "      print_matrix(seq2,seq1,score_matrix)\n",
        "      print(\"Matriz de Rastreamento:\")\n",
        "      print_matrix(seq2,seq1,traceback_matrix)\n",
        "      return score_matrix[-1][-1],reconstrucao(seq1,seq2,traceback_matrix,matrizes)\n",
        "    \n",
        "  else:\n",
        "      return score_matrix[-1][-1],reconstrucao(seq1,seq2,traceback_matrix,matrizes)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 91,
      "metadata": {},
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "Matriz de Pontuação:\n",
            "    -   A   G   A\n",
            "-   0  -4  -8 -12\n",
            "A  -4   2  -2  -6\n",
            "C  -8  -2   1  -3\n",
            "T -12  -6  -3   0\n",
            "G -16 -10  -4  -4\n",
            "G -20 -14  -8  -5\n",
            "\n",
            "Matriz de Rastreamento:\n",
            "    -   A   G   A\n",
            "-   0   ←   ←   ←\n",
            "A   ↑   ↖   ←   ↖\n",
            "C   ↑   ↑   ↖   ↖\n",
            "T   ↑   ↑   ↖   ↖\n",
            "G   ↑   ↑   ↖   ↖\n",
            "G   ↑   ↑   ↖   ↖\n",
            "\n",
            "ACTGG\n",
            "A--GA\n"
          ]
        },
        {
          "data": {
            "text/plain": [
              "(-5, ('ACTGG', 'A--GA'))"
            ]
          },
          "execution_count": 91,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "# exemplo de alinhamento de DNA\n",
        "needleman_wunsch(\"ACTGG\", \"AGA\",'DNA')"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "### Testes de unidade"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 92,
      "metadata": {
        "id": "qjG57vPT1NuE"
      },
      "outputs": [
        {
          "name": "stderr",
          "output_type": "stream",
          "text": [
            "test_alinhamento_DNA_correto (__main__.Testneedlemanwunch.test_alinhamento_DNA_correto) ... ok\n",
            "test_alinhamento_PROTEIN_correto (__main__.Testneedlemanwunch.test_alinhamento_PROTEIN_correto) ... ERROR\n",
            "test_alinhamento_RNA_correto (__main__.Testneedlemanwunch.test_alinhamento_RNA_correto) ... ok\n",
            "test_needleman_wunsch_letras_maiusculas (__main__.Testneedlemanwunch.test_needleman_wunsch_letras_maiusculas) ... ok\n",
            "test_needleman_wunsch_letras_minusculas (__main__.Testneedlemanwunch.test_needleman_wunsch_letras_minusculas) ... ok\n",
            "test_nw_caracter_seq1_DNA_errado (__main__.Testneedlemanwunch.test_nw_caracter_seq1_DNA_errado) ... ok\n",
            "test_nw_caracter_seq1_PROTEINA_errado (__main__.Testneedlemanwunch.test_nw_caracter_seq1_PROTEINA_errado) ... ok\n",
            "test_nw_caracter_seq1_RNA_errado (__main__.Testneedlemanwunch.test_nw_caracter_seq1_RNA_errado) ... ok\n",
            "test_nw_caracter_seq2_DNA_errado (__main__.Testneedlemanwunch.test_nw_caracter_seq2_DNA_errado) ... ok\n",
            "test_nw_caracter_seq2_PROTEINA_errado (__main__.Testneedlemanwunch.test_nw_caracter_seq2_PROTEINA_errado) ... ok\n",
            "test_nw_caracter_seq2_RNA_errado (__main__.Testneedlemanwunch.test_nw_caracter_seq2_RNA_errado) ... ok\n",
            "test_nw_seq1_not_dna (__main__.Testneedlemanwunch.test_nw_seq1_not_dna) ... ok\n",
            "test_nw_seq1_not_rna (__main__.Testneedlemanwunch.test_nw_seq1_not_rna) ... ok\n",
            "test_nw_seq2_not_dna (__main__.Testneedlemanwunch.test_nw_seq2_not_dna) ... ok\n",
            "test_nw_seq2_not_rna (__main__.Testneedlemanwunch.test_nw_seq2_not_rna) ... ok\n",
            "test_nw_seq_tipo_caracter_errado_DNA (__main__.Testneedlemanwunch.test_nw_seq_tipo_caracter_errado_DNA) ... ok\n",
            "test_nw_seq_tipo_caracter_errado_PROTEIN (__main__.Testneedlemanwunch.test_nw_seq_tipo_caracter_errado_PROTEIN) ... ok\n",
            "test_nw_seq_tipo_caracter_errado_RNA (__main__.Testneedlemanwunch.test_nw_seq_tipo_caracter_errado_RNA) ... ok\n",
            "test_seq1_vazio (__main__.Testneedlemanwunch.test_seq1_vazio) ... ok\n",
            "test_seq2_vazio (__main__.Testneedlemanwunch.test_seq2_vazio) ... ok\n",
            "\n",
            "======================================================================\n",
            "ERROR: test_alinhamento_PROTEIN_correto (__main__.Testneedlemanwunch.test_alinhamento_PROTEIN_correto)\n",
            "----------------------------------------------------------------------\n",
            "Traceback (most recent call last):\n",
            "  File \"C:\\Users\\Utilizador\\AppData\\Local\\Temp\\ipykernel_4780\\3590752401.py\", line 79, in test_alinhamento_PROTEIN_correto\n",
            "    self.assertEqual(needleman_wunsch(\"PHSWG\",\"HGWAG\",\"PROTEIN\"),(17, ('PHSW-G', '-HGWAG')))\n",
            "                     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\n",
            "  File \"C:\\Users\\Utilizador\\AppData\\Local\\Temp\\ipykernel_4780\\566759394.py\", line 320, in needleman_wunsch\n",
            "    diagonal = score_matrix[linha - 1][coluna - 1] + score_subst_prot(matriz,seq1[linha],seq2[coluna])\n",
            "                                                     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\n",
            "  File \"C:\\Users\\Utilizador\\AppData\\Local\\Temp\\ipykernel_4780\\566759394.py\", line 154, in score_subst_prot\n",
            "    with open(nome_matriz.upper()+\".txt\", \"r\") as file:\n",
            "         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\n",
            "  File \"C:\\Users\\Utilizador\\AppData\\Local\\Packages\\PythonSoftwareFoundation.Python.3.11_qbz5n2kfra8p0\\LocalCache\\local-packages\\Python311\\site-packages\\IPython\\core\\interactiveshell.py\", line 286, in _modified_open\n",
            "    return io_open(file, *args, **kwargs)\n",
            "           ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\n",
            "FileNotFoundError: [Errno 2] No such file or directory: 'BLOSSOM62.txt'\n",
            "\n",
            "----------------------------------------------------------------------\n",
            "Ran 20 tests in 0.096s\n",
            "\n",
            "FAILED (errors=1)\n"
          ]
        },
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "Matriz de Pontuação:\n",
            "    -   A   C   T   A\n",
            "-   0  -4  -8 -12 -16\n",
            "A  -4   2  -2  -6 -10\n",
            "G  -8  -2   1  -3  -7\n",
            "A -12  -6  -3   0  -1\n",
            "T -16 -10  -7  -1  -1\n",
            "T -20 -14 -11  -5  -2\n",
            "\n",
            "Matriz de Rastreamento:\n",
            "    -   A   C   T   A\n",
            "-   0   ←   ←   ←   ←\n",
            "A   ↑   ↖   ←   ←   ↖\n",
            "G   ↑   ↑   ↖   ↖   ↖\n",
            "A   ↑   ↖   ↖   ↖   ↖\n",
            "T   ↑   ↑   ↖   ↖   ↖\n",
            "T   ↑   ↑   ↖   ↖   ↖\n",
            "\n",
            "AGATT\n",
            "A-CTA\n",
            "Matriz de Pontuação:\n",
            "    -   A   G   A   U\n",
            "-   0  -4  -8 -12 -16\n",
            "U  -4  -1  -5  -9 -10\n",
            "A  -8  -2  -2  -3  -7\n",
            "C -12  -6  -3  -3  -4\n",
            "A -16 -10  -7  -1  -4\n",
            "A -20 -14 -11  -5  -2\n",
            "\n",
            "Matriz de Rastreamento:\n",
            "    -   A   G   A   U\n",
            "-   0   ←   ←   ←   ←\n",
            "U   ↑   ↖   ↖   ↖   ↖\n",
            "A   ↑   ↖   ↖   ↖   ←\n",
            "C   ↑   ↑   ↖   ↖   ↖\n",
            "A   ↑   ↖   ↖   ↖   ↖\n",
            "A   ↑   ↖   ↖   ↖   ↖\n",
            "\n",
            "UACAA\n",
            "-AGAU\n",
            "Matriz de Pontuação:\n",
            "    -   A   G   A\n",
            "-   0  -4  -8 -12\n",
            "A  -4   2  -2  -6\n",
            "C  -8  -2   1  -3\n",
            "T -12  -6  -3   0\n",
            "G -16 -10  -4  -4\n",
            "G -20 -14  -8  -5\n",
            "\n",
            "Matriz de Rastreamento:\n",
            "    -   A   G   A\n",
            "-   0   ←   ←   ←\n",
            "A   ↑   ↖   ←   ↖\n",
            "C   ↑   ↑   ↖   ↖\n",
            "T   ↑   ↑   ↖   ↖\n",
            "G   ↑   ↑   ↖   ↖\n",
            "G   ↑   ↑   ↖   ↖\n",
            "\n",
            "ACTGG\n",
            "A--GA\n",
            "Matriz de Pontuação:\n",
            "    -   a   g   a\n",
            "-   0  -4  -8 -12\n",
            "a  -4   2  -2  -6\n",
            "c  -8  -2   1  -3\n",
            "t -12  -6  -3   0\n",
            "g -16 -10  -4  -4\n",
            "g -20 -14  -8  -5\n",
            "\n",
            "Matriz de Rastreamento:\n",
            "    -   a   g   a\n",
            "-   0   ←   ←   ←\n",
            "a   ↑   ↖   ←   ↖\n",
            "c   ↑   ↑   ↖   ↖\n",
            "t   ↑   ↑   ↖   ↖\n",
            "g   ↑   ↑   ↖   ↖\n",
            "g   ↑   ↑   ↖   ↖\n",
            "\n",
            "actgg\n",
            "a--ga\n",
            "O elemento -, na posição 6, não é um nucleotido válido\n",
            "O elemento -, na posição 6, não é um nucleotido válido\n",
            "O elemento %, na posição 4, não é um nucleotido válido\n",
            "O elemento /, na posição 4, não é um nucleotido válido\n"
          ]
        },
        {
          "data": {
            "text/plain": [
              "<unittest.runner.TextTestResult run=20 errors=1 failures=0>"
            ]
          },
          "execution_count": 92,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "import unittest\n",
        "\n",
        "class Testneedlemanwunch(unittest.TestCase):\n",
        "    def test_nw_seq_tipo_caracter_errado_DNA(self): \n",
        "        with self.assertRaises(AssertionError):\n",
        "            needleman_wunsch(\"ACTGG\", \"AGA\",\"DNA/\") \n",
        "    \n",
        "    def test_nw_seq_tipo_caracter_errado_RNA(self): \n",
        "        with self.assertRaises(AssertionError):\n",
        "            needleman_wunsch(\"ACUGG\", \"AUA\",\"RNA/\")\n",
        "    \n",
        "    def test_nw_seq_tipo_caracter_errado_PROTEIN(self): \n",
        "        with self.assertRaises(AssertionError):\n",
        "            needleman_wunsch(\"CREATINNA\", \"BEEFFAA\",\"/PROTEIN\") \n",
        "    \n",
        "    def test_nw_caracter_seq1_DNA_errado(self): \n",
        "        with self.assertRaises(AssertionError):\n",
        "            needleman_wunsch(\"ACTGG-\", \"AGA\",\"DNA\")\n",
        "\n",
        "    def test_nw_caracter_seq2_DNA_errado(self): \n",
        "        with self.assertRaises(AssertionError):\n",
        "            needleman_wunsch(\"ACTGG\", \"AGA%\",\"DNA\") \n",
        "\n",
        "    def test_nw_caracter_seq1_RNA_errado(self): \n",
        "        with self.assertRaises(AssertionError):\n",
        "            needleman_wunsch(\"ACUGG-\", \"AUA\",\"RNA\")\n",
        "\n",
        "    def test_nw_caracter_seq2_RNA_errado(self): \n",
        "        with self.assertRaises(AssertionError):\n",
        "            needleman_wunsch(\"ACUGG\", \"AUA/\",\"RNA\")\n",
        "\n",
        "    def test_nw_caracter_seq1_PROTEINA_errado(self): \n",
        "        with self.assertRaises(AssertionError):\n",
        "            needleman_wunsch(\"CREATINNA%\", \"BEEFFAA\",\"PROTEIN\")\n",
        "\n",
        "    def test_nw_caracter_seq2_PROTEINA_errado(self): \n",
        "        with self.assertRaises(AssertionError):\n",
        "            needleman_wunsch(\"CREATINNA\", \"BEEFFAA%/\",\"PROTEIN\")\n",
        "    \n",
        "    def test_nw_seq1_not_dna(self):\n",
        "        with self.assertRaises(AssertionError):\n",
        "            needleman_wunsch(\"ACUGG\", \"AGA\",\"DNA\")\n",
        "    \n",
        "    def test_nw_seq2_not_dna(self):\n",
        "        with self.assertRaises(AssertionError):\n",
        "            needleman_wunsch(\"ACTGG\", \"AUA\",\"DNA\")\n",
        "    \n",
        "    def test_nw_seq1_not_rna(self):\n",
        "        with self.assertRaises(AssertionError):\n",
        "            needleman_wunsch(\"ACTGG\", \"AUA\",\"RNA\")\n",
        "    \n",
        "    def test_nw_seq2_not_rna(self):\n",
        "        with self.assertRaises(AssertionError):\n",
        "            needleman_wunsch(\"ACUGG\", \"ATA\",\"RNA\")\n",
        "    \n",
        "    def test_seq1_vazio(self):\n",
        "        with self.assertRaises(AssertionError):\n",
        "            needleman_wunsch(\"\", \"ATA\",\"DNA\")\n",
        "\n",
        "    def test_seq2_vazio(self):\n",
        "        with self.assertRaises(AssertionError):\n",
        "            needleman_wunsch(\"ACTGG\",\"\",\"DNA\")\n",
        "\n",
        "    def test_needleman_wunsch_letras_maiusculas(self):\n",
        "        score, _ = needleman_wunsch(\"ACTGG\", \"AGA\", \"DNA\")\n",
        "        self.assertEqual(score, -5)\n",
        "\n",
        "    def test_needleman_wunsch_letras_minusculas(self):\n",
        "        score, _ = needleman_wunsch(\"actgg\", \"aga\", \"dna\")\n",
        "        self.assertEqual(score, -5)\n",
        "\n",
        "    def test_alinhamento_DNA_correto(self):\n",
        "        self.assertEqual(needleman_wunsch(\"AGATT\",\"ACTA\",\"DNA\"),(-2, ('AGATT', 'A-CTA')))\n",
        "\n",
        "    def test_alinhamento_RNA_correto(self):\n",
        "        self.assertEqual(needleman_wunsch(\"UACAA\",\"AGAU\",\"RNA\"),(-2, ('UACAA', '-AGAU')))\n",
        "    \n",
        "    def test_alinhamento_PROTEIN_correto(self):\n",
        "        self.assertEqual(needleman_wunsch(\"PHSWG\",\"HGWAG\",\"PROTEIN\"),(17, ('PHSW-G', '-HGWAG')))\n",
        "\n",
        "suite = unittest.TestLoader().loadTestsFromTestCase(Testneedlemanwunch)\n",
        "unittest.TextTestRunner(verbosity=3).run(suite)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "<!-- LTeX: language=pt -->\n",
        "## Tarefa 6 - Blast\n",
        "\n",
        "<div align='justify'>\n",
        "\n",
        "Na tarefa 6, foi propostoa construção do algoritmo Blast. Neste notebook, discutiu-se os algoritmos heurísticos e as ferramentas existentes para esta tarefa e procedeu-se à implementação de uma versão simplificada do algoritmo para comparação de sequências biológicas mais popular, o BLAST.<br>\n",
        "A tentativa de inferir a função a partir de sequências semelhantes é uma forma de abordar esta tarefa, em que se tentou\n",
        "identificar sequências que sejam semelhantes à sequência alvo (de consulta) e que já estejam anotadas com uma determinada função.<br> \n",
        "O algoritmo BLAST é atualmente o mais utilizado para efetuar pesquisas em bases de dados de sequências de DNA ou de proteínas. O objetivo é procurar bons alinhamentos entre uma sequência de consulta e as sequências de uma base de dados definida. A ideia básica dos algoritmos é utilizar \"palavras\" curtas (ou seja, sub-sequências) e procurar correspondências de elevada semelhança destas palavras na consulta e nas sequências da base de dados. Estas correspondências formarão uma base que pode ser\n",
        "que pode ser alargada, em ambas as direcções, para obter alinhamentos de alta qualidade de maior dimensão.<br>\n",
        "\n",
        "Inicialmente, há uma string (a query), que é a sequência que queremos procurar dentro de uma sequência alvo (seq); e um parâmetro do algoritmo, W (tamanho), que nos indica as sub-sequências de comprimento w que ocorrem na sequência de consulta.<br>\n",
        "Começou-se por construir a função parse_query, que recebe uma sequência (query) e realiza as operações de remoção de espaços em branco, converção da sequência para maiúsculas e verificação se a sequência contém apenas as letras permitidas (A, C, G, T). Assim, consegue-se que o input dado pelo utilizador seja válida, pois a função retorna a a sequência processada.<br>\n",
        "De seguida, construiu-se a função query_map, que recebe a sequência que se quer procurar dentro de uma sequência alvo (query) e o tamanho da janela de procura(parâmetro w), e  devolve um dicionário que tem como chaves as palavras da consulta e como valores as listas de posições onde estas ocorrem como valores.<br>\n",
        "Passou-se para a construção da função hits, que recebe um dicionário que contem um mapeamento de queries para offsets (resultado da função query_map) e uma sequência alvo, e realiza buscas utilizando as queries na sequência alvo, retornando uma lista de tuplos, onde cada tuplo contém dois valores: o offset na query e o offset na sequência.<br>\n",
        "Para o auxílio desta função, foram ainda construidas duas funções auxiliares: procura, que procura uma subsequência específica (codao) numa sequência dada (seq) e retorna uma lista contendo os offsets onde a subsequência é encontrada; e criar_tuplos, que cria tuplos contendo o offset fornecido e os elementos da lista de índices.<br>\n",
        "Para estender o hit na sequência até que não seja mais possível, mantendo um número mínimo de matches, montou-se a função extend_hit.\n",
        "Por último, com a função best_hit, realizou-se extensões de hits, retornando o melhor hit de todos.Esta identifica o melhor alinhamento entre a consulta e uma dada sequência, com todos os resultados de tamanho w. O que tivar com a melhor pontuação global (maior número de correspondências) será selecionado.<br>\n",
        "</div>"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 93,
      "metadata": {},
      "outputs": [],
      "source": [
        "#Exemplo prático\n",
        "query=\"AATATAT\" \n",
        "seq=\"AATATGTTATATAATAATATTT\"\n",
        "w=3 "
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 29,
      "metadata": {},
      "outputs": [],
      "source": [
        "#Exemplo para testar o Blast\n",
        "query = input()\n",
        "seq = input()\n",
        "w = int(input())"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 94,
      "metadata": {},
      "outputs": [],
      "source": [
        "def parse_query(query : str) -> str:\n",
        "  \"\"\"\n",
        "    Esta função recebe uma sequência (query) e realiza as seguintes operações:\n",
        "      1. Remove espaços em branco.\n",
        "      2. Converte a sequência para maiúsculas.\n",
        "      3. Verifica se a sequência contém apenas as letras permitidas (A, C, G, T).\n",
        "\n",
        "    Parameters\n",
        "    ----------\n",
        "    query : str\n",
        "      a sequência que será processada.\n",
        "\n",
        "    Returns\n",
        "    -------\n",
        "    str\n",
        "      a sequência processada, após a remoção de espaços, conversão para maiúsculas e validação das letras permitidas.\n",
        "\n",
        "    Raises\n",
        "    ------\n",
        "    ValueError\n",
        "      se a sequência for vazia ou conter caracteres não permitidos.\n",
        "  \"\"\"\n",
        "\n",
        "  query = query.replace(\" \", \"\").upper()\n",
        "\n",
        "  if query == \"\": \n",
        "      raise ValueError(\"A sequência não pode ser vazia\")\n",
        "    \n",
        "  letras_permitidas = set(['A', 'C', 'G', 'T'])\n",
        "\n",
        "  if set(query) <= letras_permitidas:\n",
        "      return query\n",
        "\n",
        "  else:\n",
        "      raise ValueError(\"A sequência deve conter apenas as letras A, C, G, T\")\n",
        "\n",
        "def query_map(query : str, w: int) -> dict[str, list[int]]:\n",
        "  \"\"\"\n",
        "  Esta função recebe a sequência que queremos procurar dentro de uma sequência alvo (query) devolve um dicionário que\n",
        "  tem como chaves as palavras da consulta e como valores as listas de posições onde estas ocorrem como valores.\n",
        "\n",
        "  Parameters\n",
        "  ----------\n",
        "  query : str\n",
        "    a string que procuramos.\n",
        "\n",
        "  w : int\n",
        "    o tamanho da janela. O valor de w por padrão é 3.\n",
        "\n",
        "  Returns\n",
        "  -------\n",
        "  dict : str, list[int]\n",
        "    Devolve um dicionário:\n",
        "      cuja chave são todas as strings de tamanho w da query e;\n",
        "      cujo valor é uma lista com todos os offsets onde aparecem.\n",
        "\n",
        "  Raises\n",
        "  ------\n",
        "  TypeError\n",
        "    A sequência deve ser uma string.\n",
        "  \n",
        "  ValueError\n",
        "    O tamanho da janela deve ser um inteiro positivo\n",
        "  \"\"\"\n",
        "  if not isinstance(query, str):\n",
        "    raise TypeError(\"A sequência deve ser uma string\")\n",
        "  \n",
        "  if not isinstance(w, int) or w <= 0:\n",
        "    raise ValueError(\"O tamanho da janela deve ser um inteiro positivo\")\n",
        "\n",
        "  query = parse_query(query)\n",
        "\n",
        "  res={}\n",
        "  for I in range(len(query)):\n",
        "    sub_string=query[I:I+w]\n",
        "\n",
        "    if sub_string not in res and len(sub_string)==w:\n",
        "      res[sub_string]=[I]\n",
        "    elif sub_string in res and len(sub_string)==w:\n",
        "      res[sub_string].append(I)\n",
        "  return res\n",
        "\n",
        "qm = query_map(query, w)\n",
        "\n",
        "def procura(codao : str, seq : str) -> list[int]:\n",
        "  \"\"\"\n",
        "  Função auxiliar da função hits.\n",
        "  Esta função procura uma subsequência específica (codao) numa sequência dada (seq) e\n",
        "  retorna uma lista contendo os offsets onde a subsequência é encontrada.\n",
        "\n",
        "  Parameters\n",
        "  ----------\n",
        "  codao : str\n",
        "    a subsequência que estamos a procurar na sequência.\n",
        "\n",
        "  seq : str\n",
        "    a sequência na qual estamos a procurar a subsequência.\n",
        "\n",
        "  Returns\n",
        "  -------\n",
        "  list[int]\n",
        "    uma lista que contem os offsets (índices) onde a subsequência é encontrada na sequência.\n",
        "  \"\"\"\n",
        "  tm = len(codao)\n",
        "  indices = []\n",
        "  for i in range(len(seq)):\n",
        "      sub_string = seq[i: i + tm]\n",
        "      if codao == sub_string:\n",
        "          indices.append(i)\n",
        "  return indices\n",
        "\n",
        "def criar_tuplos(indices : list[int], offset : int) -> list[tuple[int, int]]: \n",
        "  \"\"\"\n",
        "  Função auxiliar da função hits.\n",
        "  Esta função cria tuplos contendo o offset fornecido e os elementos da lista de índices.\n",
        "\n",
        "  Parameters\n",
        "  ----------\n",
        "  indices : list[int]\n",
        "    lista que contem os índices para os quais os tuplos serão criados.\n",
        "\n",
        "  offset : int\n",
        "    o valor do offset que será incluído nos tuplos.\n",
        "\n",
        "  Returns\n",
        "  -------\n",
        "  list[tuple[int, int]]\n",
        "    Lista de tuplos que contem o offset e cada elemento da lista de índices.\n",
        "  \"\"\"\n",
        "  tuplos = []\n",
        "\n",
        "  for l in indices:\n",
        "      tuplos.append((offset, l))\n",
        "  return tuplos\n",
        "\n",
        "def hits(qm : dict[str, list[int]], seq : str) -> list[tuple[int, int]]:\n",
        "  \"\"\"\n",
        "  Esta função recebe um dicionário que contem um mapeamento de queries para offsets e uma sequência alvo,\n",
        "  realiza buscas utilizando as queries na sequência alvo e retorna uma lista de tuplos,\n",
        "  onde cada tuplo contém dois valores: o offset na query e o offset na sequência.\n",
        "\n",
        "  Parameters\n",
        "  ----------\n",
        "  qm : dict[str, list[int]]\n",
        "    o que é devolvido ao invocar a função query_map.\n",
        "\n",
        "  seq : str\n",
        "    a sequência alvo.\n",
        "\n",
        "  Returns\n",
        "  -------\n",
        "  list : tuple[int, int]\n",
        "    Devolve uma lista em que cada elemento é um tuplo com dois valores:\n",
        "      1. O Offset na query;\n",
        "      2. O offset na seq.\n",
        "\n",
        "  Raises\n",
        "  ------\n",
        "  TypeError\n",
        "    A sequência deve ser uma string.\n",
        "  \"\"\"\n",
        "  if not isinstance(seq, str):\n",
        "    raise TypeError(\"A sequência deve ser uma string\")\n",
        "  hits_list = [] \n",
        "\n",
        "  seq = parse_query(seq)\n",
        "\n",
        "  for query, offsets in qm.items():\n",
        "      # seq <- indices query\n",
        "      res = procura(query, seq)\n",
        "      # [0 , 12, 15] 0 -> 0,0 0,12 0,15\n",
        "      for offset in offsets:\n",
        "          hits_list += criar_tuplos(res, offset) \n",
        "\n",
        "  return hits_list\n",
        "\n",
        "res = hits(qm, seq)\n",
        "\n",
        "def extend_hit(query : str, seq : str, hit : tuple[int, int], w: int) -> tuple[int, int, int, int]:\n",
        "  \"\"\"\n",
        "  Esta função recebe uma query, uma sequência alvo, um hit e um tamanho de janela,\n",
        "  e estende o hit na sequência até que não seja possível mais, mantendo um número mínimo de matches.\n",
        "      \n",
        "  Parameters\n",
        "  ----------\n",
        "  query : str\n",
        "    a string que procuramos.\n",
        "\n",
        "  seq : str\n",
        "    a sequência alvo.\n",
        "\n",
        "  hit : tuple[int, int]\n",
        "    um dos elementos devolvidos pela invocação da função hits.\n",
        "\n",
        "  w : int\n",
        "    o tamanho da janela. O valor de w por padrão é 3.\n",
        "\n",
        "  Returns\n",
        "  -------\n",
        "  tuple : [int, int, int, int]\n",
        "    Devolve um tuplo com:\n",
        "        1. O offset inicial na query;\n",
        "        2. O offset inicial na seq;\n",
        "        3. O tamanho do resultado;\n",
        "        4. O nº de matches corretos.\n",
        "\n",
        "  Raises\n",
        "  ------\n",
        "  TypeError\n",
        "    A sequência deve ser uma string.\n",
        "  ValueError\n",
        "    O tamanho da janela deve ser um inteiro positivo.\n",
        "  \"\"\"\n",
        "  if not isinstance(query, str):\n",
        "    raise TypeError(\"A sequência deve ser uma string\")\n",
        "  if not isinstance(seq, str):\n",
        "    raise TypeError(\"A sequência deve ser uma string\")\n",
        "  if not isinstance(w, int) or w <= 0:\n",
        "    raise ValueError(\"O tamanho da janela deve ser um inteiro positivo\")\n",
        "  \n",
        "  query = parse_query(query)\n",
        "  seq = parse_query(seq)\n",
        "\n",
        "  num_matches = w\n",
        "  tam_extensao = w \n",
        "  i_min_query = hit[0]\n",
        "  i_min_seq = hit[1]\n",
        "  i_max_query = hit[0] + w - 1\n",
        "  i_max_seq = hit[1] + w - 1\n",
        "    \n",
        "  while num_matches >= tam_extensao / 2 and ((i_min_seq > 0 and i_min_query > 0) or (i_max_seq < len(seq) - 1 and i_max_query < len(query) - 1)):\n",
        "      # esquerda \n",
        "      if i_min_query>0 and i_min_seq>0:\n",
        "          i_min_query -= 1\n",
        "          i_min_seq -= 1 \n",
        "          tam_extensao += 1\n",
        "          if query[i_min_query] == seq[i_min_seq]:\n",
        "              num_matches += 1\n",
        "      # direita \n",
        "      if i_max_query < len(query) - 1 and i_max_seq < len(seq) - 1:\n",
        "          i_max_query += 1\n",
        "          i_max_seq += 1 \n",
        "          tam_extensao += 1\n",
        "          if query[i_max_query] == seq[i_max_seq]:\n",
        "              num_matches += 1\n",
        "            \n",
        "  return (i_min_query, i_min_seq, i_max_query - i_min_query + 1, num_matches)\n",
        "\n",
        "def best_hit(query : str, seq : str, w: int) -> tuple[int, int, int, int]:\n",
        "  \"\"\"\n",
        "  Esta função recebe uma query, uma sequência alvo, e um tamanho de janela,\n",
        "  realiza extensões de hits usando a função extend_hit, e retorna o melhor hit encontrado.\n",
        "\n",
        "  Parameters\n",
        "  ----------\n",
        "  query : str\n",
        "    a string que procuramos.\n",
        "\n",
        "  seq : str\n",
        "    a sequência alvo.\n",
        "\n",
        "  w : int\n",
        "    o tamanho da janela. O valor de w por padrão é 3.\n",
        "\n",
        "  Returns\n",
        "  -------\n",
        "  tuple : [int, int, int, int]\n",
        "    Devolve um tuplo com:\n",
        "      1. O offset inicial na query;\n",
        "      2. O offset inicial na seq;\n",
        "      3. O tamanho do resultado;\n",
        "      4. O nº de matches corretos.\n",
        "\n",
        "  Raises\n",
        "  ------\n",
        "  TypeError\n",
        "    A sequência deve ser uma string.\n",
        "  ValueError\n",
        "    O tamanho da janela deve ser um inteiro positivo\n",
        "  \"\"\"\n",
        "  if not isinstance(query, str):\n",
        "    raise TypeError(\"A sequência deve ser uma string\")\n",
        "  if not isinstance(seq, str):\n",
        "    raise TypeError(\"A sequência deve ser uma string\")\n",
        "  if not isinstance(w, int) or w <= 0:\n",
        "    raise ValueError(\"O tamanho da janela deve ser um inteiro positivo\")\n",
        "  \n",
        "  query = parse_query(query)\n",
        "  seq = parse_query(seq)\n",
        "\n",
        "  qm = query_map(query, w)\n",
        "  hits_list = hits(qm, seq)\n",
        "  \n",
        "  best_hit_result = None\n",
        "  best_score = 0\n",
        "\n",
        "  for hit in hits_list:\n",
        "      extended_hit = extend_hit(query, seq, hit, w)\n",
        "      score = extended_hit[3]\n",
        "\n",
        "      if score > best_score or (score == best_score and extended_hit[2] < best_hit_result[2]):\n",
        "        best_hit_result = extended_hit\n",
        "        best_score = score\n",
        "\n",
        "  return best_hit_result"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 95,
      "metadata": {},
      "outputs": [
        {
          "data": {
            "text/plain": [
              "(0, 0, 7, 6)"
            ]
          },
          "execution_count": 95,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "best_hit(query, seq, w)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "### Testes de unidade"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 96,
      "metadata": {},
      "outputs": [
        {
          "name": "stderr",
          "output_type": "stream",
          "text": [
            "test_query_map_invalida (__main__.TestBlast.test_query_map_invalida) ... ok\n",
            "test_query_map_output (__main__.TestBlast.test_query_map_output) ... ok\n",
            "test_query_map_output_false (__main__.TestBlast.test_query_map_output_false) ... ok\n",
            "test_query_map_vazia (__main__.TestBlast.test_query_map_vazia) ... ok\n",
            "test_query_map_w_negativo (__main__.TestBlast.test_query_map_w_negativo) ... ok\n",
            "test_query_map_w_number (__main__.TestBlast.test_query_map_w_number) ... ok\n",
            "\n",
            "----------------------------------------------------------------------\n",
            "Ran 6 tests in 0.023s\n",
            "\n",
            "OK\n"
          ]
        },
        {
          "data": {
            "text/plain": [
              "<unittest.runner.TextTestResult run=6 errors=0 failures=0>"
            ]
          },
          "execution_count": 96,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "import unittest\n",
        "\n",
        "#Para a função query_map\n",
        "class TestBlast(unittest.TestCase):\n",
        "    def test_query_map_vazia(self):\n",
        "        # Testa se a função lança um erro ao receber uma sequência vazia\n",
        "        with self.assertRaises(ValueError):\n",
        "            query_map(\"\", 3)\n",
        "\n",
        "    def test_query_map_w_negativo(self):\n",
        "        # Testa se a função lança um erro ao receber um valor negativo para w\n",
        "        with self.assertRaises(ValueError):\n",
        "            query_map(\"ACT\", -3)\n",
        "\n",
        "    def test_query_map_w_number(self):\n",
        "        # Testa se a função lança um erro ao receber um valor não string para a sequência\n",
        "        with self.assertRaises(TypeError):\n",
        "            query_map(1, \"3\")\n",
        "\n",
        "    def test_query_map_invalida(self):\n",
        "        # Testa se a função lança um erro ao receber uma sequência com letras inválidas\n",
        "        with self.assertRaises(ValueError):\n",
        "            query_map(\"epQINM\", 3)\n",
        "            \n",
        "    def test_query_map_output(self):\n",
        "        # Testa se a função dá o resultado esperado para esses parâmetros\n",
        "        output = {'ATG': [0], 'TGC': [1], 'GCG': [2], 'CGG': [3], 'GGT': [4]}\n",
        "        self.assertEqual(query_map(\"ATGCGGT\", 3), output)\n",
        "\n",
        "    def test_query_map_output_false(self):\n",
        "        # Testa se a função dá o erro para o resultado não esperado para esses parâmetros\n",
        "        output = {'AAT': [0], 'ATA': [1, 4], 'TAT': [2, 3]}\n",
        "        self.assertFalse(query_map(\"AATATAT\", 3) == output)\n",
        "\n",
        "suite = unittest.TestLoader().loadTestsFromTestCase(TestBlast)\n",
        "unittest.TextTestRunner(verbosity=3).run(suite)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 97,
      "metadata": {},
      "outputs": [
        {
          "name": "stderr",
          "output_type": "stream",
          "text": [
            "test_hit_invalida (__main__.TestBlast.test_hit_invalida) ... ok\n",
            "test_hit_output (__main__.TestBlast.test_hit_output) ... ok\n",
            "test_hit_output_false (__main__.TestBlast.test_hit_output_false) ... ok\n",
            "test_hit_vazia (__main__.TestBlast.test_hit_vazia) ... ok\n",
            "test_hit_w_number (__main__.TestBlast.test_hit_w_number) ... ok\n",
            "\n",
            "----------------------------------------------------------------------\n",
            "Ran 5 tests in 0.017s\n",
            "\n",
            "OK\n"
          ]
        },
        {
          "data": {
            "text/plain": [
              "<unittest.runner.TextTestResult run=5 errors=0 failures=0>"
            ]
          },
          "execution_count": 97,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "#Para a função hits\n",
        "class TestBlast(unittest.TestCase):\n",
        "    def test_hit_vazia(self):\n",
        "        # Testa se a função lança um erro ao receber uma sequência vazia\n",
        "        with self.assertRaises(ValueError):\n",
        "            hits(qm, \"\")\n",
        "\n",
        "    def test_hit_w_number(self):\n",
        "        # Testa se a função lança um erro ao receber um valor não string para a sequência\n",
        "        with self.assertRaises(TypeError):\n",
        "            hits(qm, 34)\n",
        "\n",
        "    def test_hit_invalida(self):\n",
        "        # Testa se a função lança um erro ao receber uma sequência com letras inválidas\n",
        "        with self.assertRaises(ValueError):\n",
        "            hits(qm, \"Efehsw\")\n",
        "            \n",
        "    def test_hit_output(self):\n",
        "        # Testa se a função dá o resultado esperado para esses parâmetros\n",
        "        q = query_map(\"AATATAT\", 3)\n",
        "        output = [(0, 0), (0, 12), (0, 15), (1, 1), (1, 8), (1, 10), (1, 13), (1, 16), (3, 1), (3, 8), (3, 10), (3, 13), (3, 16), (2, 2), (2, 7), (2, 9), (2, 17), (4, 2), (4, 7), (4, 9), (4, 17)]\n",
        "        self.assertEqual(hits(q, \"AATATGTTATATAATAATATTT\"), output)\n",
        "\n",
        "    def test_hit_output_false(self):\n",
        "        # Testa se a função dá o erro para o resultado não esperado para esses parâmetros\n",
        "        output = [(0, 0), (0, 12), (0, 11), (1, 1), (1, 9), (1, 7), (1, 13), (1, 16), (3, 1), (3, 8), (3, 10), (3, 13), (3, 16), (2, 2), (2, 7), (2, 9), (2, 17), (4, 2), (4, 7), (4, 9), (4, 17)]\n",
        "        q = query_map(\"AATATAT\", 3)\n",
        "        self.assertFalse(hits(q, \"AATATGTTATATAATAATATTT\") == output)\n",
        "\n",
        "suite = unittest.TestLoader().loadTestsFromTestCase(TestBlast)\n",
        "unittest.TextTestRunner(verbosity=3).run(suite)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 98,
      "metadata": {},
      "outputs": [
        {
          "name": "stderr",
          "output_type": "stream",
          "text": [
            "test_extend_hit_output (__main__.TestBlast.test_extend_hit_output) ... ok\n",
            "test_extend_hit_output_false (__main__.TestBlast.test_extend_hit_output_false) ... ok\n",
            "test_extend_hit_query_invalida (__main__.TestBlast.test_extend_hit_query_invalida) ... ok\n",
            "test_extend_hit_query_vazia (__main__.TestBlast.test_extend_hit_query_vazia) ... ok\n",
            "test_extend_hit_seq_invalida (__main__.TestBlast.test_extend_hit_seq_invalida) ... ok\n",
            "test_extend_hit_seq_vazia (__main__.TestBlast.test_extend_hit_seq_vazia) ... ok\n",
            "test_extend_hit_w_negativo (__main__.TestBlast.test_extend_hit_w_negativo) ... ok\n",
            "test_extend_hit_w_number_query (__main__.TestBlast.test_extend_hit_w_number_query) ... ok\n",
            "test_extend_hit_w_number_seq (__main__.TestBlast.test_extend_hit_w_number_seq) ... ok\n",
            "\n",
            "----------------------------------------------------------------------\n",
            "Ran 9 tests in 0.029s\n",
            "\n",
            "OK\n"
          ]
        },
        {
          "data": {
            "text/plain": [
              "<unittest.runner.TextTestResult run=9 errors=0 failures=0>"
            ]
          },
          "execution_count": 98,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "#Para a função extend_hit\n",
        "class TestBlast(unittest.TestCase):\n",
        "    def test_extend_hit_seq_vazia(self):\n",
        "        # Testa se a função lança um erro ao receber uma sequência vazia\n",
        "        with self.assertRaises(ValueError):\n",
        "            extend_hit(\"AATATAT\", \"\", (0, 12), 3)\n",
        "\n",
        "    def test_extend_hit_query_vazia(self):\n",
        "        # Testa se a função lança um erro ao receber uma query vazia\n",
        "        with self.assertRaises(ValueError):\n",
        "            extend_hit(\"\", \"AATATGTTATATAATAATATTT\", (0, 12), 3)\n",
        "\n",
        "    def test_extend_hit_w_negativo(self):\n",
        "        # Testa se a função lança um erro ao receber um valor negativo para w\n",
        "        with self.assertRaises(ValueError):\n",
        "            extend_hit(\"AATATAT\", \"AATATGTTATATAATAATATTT\", (0, 12), -9)\n",
        "\n",
        "    def test_extend_hit_w_number_seq(self):\n",
        "        # Testa se a função lança um erro ao receber um valor não string para a sequência\n",
        "        with self.assertRaises(TypeError):\n",
        "            extend_hit(\"AATATAT\", 33, (0, 12), 3)\n",
        "\n",
        "    def test_extend_hit_w_number_query(self):\n",
        "        # Testa se a função lança um erro ao receber um valor não string para a query\n",
        "        with self.assertRaises(TypeError):\n",
        "            extend_hit(33, \"AATATGTTATATAATAATATTT\", (0, 12), 3)\n",
        "\n",
        "    def test_extend_hit_seq_invalida(self):\n",
        "        # Testa se a função lança um erro ao receber uma sequência com letras inválidas\n",
        "        with self.assertRaises(ValueError):\n",
        "            extend_hit(\"AATATAT\", \"SWiopgF\", (0, 12), 3)\n",
        "\n",
        "    def test_extend_hit_query_invalida(self):\n",
        "        # Testa se a função lança um erro ao receber uma query com letras inválidas\n",
        "        with self.assertRaises(ValueError):\n",
        "            extend_hit(\"qwiofgr\", \"AATATGTTATATAATAATATTT\", (0, 12), 3)\n",
        "            \n",
        "    def test_extend_hit_output(self):\n",
        "        # Testa se a função dá o resultado esperado para esses parâmetros\n",
        "        output = (0, 12, 7, 4)\n",
        "        self.assertEqual(extend_hit(\"AATATAT\", \"AATATGTTATATAATAATATTT\", (0, 12), 3), output)\n",
        "\n",
        "    def test_extend_hit_output_false(self):\n",
        "        # Testa se a função dá erro para o resultado não esperado para esses parâmetros\n",
        "        output = (0, 12, 4, 3)\n",
        "        self.assertFalse(extend_hit(\"AATATAT\", \"AATATGTTATATAATAATATTT\", (0, 12), 3) == output)\n",
        "\n",
        "suite = unittest.TestLoader().loadTestsFromTestCase(TestBlast)\n",
        "unittest.TextTestRunner(verbosity=3).run(suite)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 99,
      "metadata": {},
      "outputs": [
        {
          "name": "stderr",
          "output_type": "stream",
          "text": [
            "test_best_hit_output (__main__.TestBlast.test_best_hit_output) ... ok\n",
            "test_best_hit_output_false (__main__.TestBlast.test_best_hit_output_false) ... ok\n",
            "test_best_hit_query_invalida (__main__.TestBlast.test_best_hit_query_invalida) ... ok\n",
            "test_best_hit_query_vazia (__main__.TestBlast.test_best_hit_query_vazia) ... ok\n",
            "test_best_hit_seq_invalida (__main__.TestBlast.test_best_hit_seq_invalida) ... ok\n",
            "test_best_hit_seq_vazia (__main__.TestBlast.test_best_hit_seq_vazia) ... ok\n",
            "test_best_hit_w_negativo (__main__.TestBlast.test_best_hit_w_negativo) ... ok\n",
            "test_best_hit_w_number_query (__main__.TestBlast.test_best_hit_w_number_query) ... ok\n",
            "test_best_hit_w_number_seq (__main__.TestBlast.test_best_hit_w_number_seq) ... ok\n",
            "\n",
            "----------------------------------------------------------------------\n",
            "Ran 9 tests in 0.032s\n",
            "\n",
            "OK\n"
          ]
        },
        {
          "data": {
            "text/plain": [
              "<unittest.runner.TextTestResult run=9 errors=0 failures=0>"
            ]
          },
          "execution_count": 99,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "#Para a função best_hit\n",
        "class TestBlast(unittest.TestCase):\n",
        "    def test_best_hit_seq_vazia(self):\n",
        "        # Testa se a função lança um erro ao receber uma sequência vazia\n",
        "        with self.assertRaises(ValueError):\n",
        "            best_hit(\"AATATAT\", \"\", 3)\n",
        "\n",
        "    def test_best_hit_query_vazia(self):\n",
        "        # Testa se a função lança um erro ao receber uma query vazia\n",
        "        with self.assertRaises(ValueError):\n",
        "            best_hit(\"\", \"AATATGTTATATAATAATATTT\", 3)\n",
        "\n",
        "    def test_best_hit_w_negativo(self):\n",
        "        # Testa se a função lança um erro ao receber um valor negativo para w\n",
        "        with self.assertRaises(ValueError):\n",
        "            best_hit(\"AATATAT\", \"AATATGTTATATAATAATATTT\", -3)\n",
        "\n",
        "    def test_best_hit_w_number_seq(self):\n",
        "        # Testa se a função lança um erro ao receber um valor não string para a sequência\n",
        "        with self.assertRaises(TypeError):\n",
        "            best_hit(\"AATATAT\", 33, 3)\n",
        "\n",
        "    def test_best_hit_w_number_query(self):\n",
        "        # Testa se a função lança um erro ao receber um valor não string para a query\n",
        "        with self.assertRaises(TypeError):\n",
        "            best_hit(33, \"AATATGTTATATAATAATATTT\", 3)\n",
        "\n",
        "    def test_best_hit_seq_invalida(self):\n",
        "        # Testa se a função lança um erro ao receber uma sequência com letras inválidas\n",
        "        with self.assertRaises(ValueError):\n",
        "            best_hit(\"AATATAT\", \"SWiopgF\", 3)\n",
        "\n",
        "    def test_best_hit_query_invalida(self):\n",
        "        # Testa se a função lança um erro ao receber uma query com letras inválidas\n",
        "        with self.assertRaises(ValueError):\n",
        "            best_hit(\"qwiofgr\", \"AATATGTTATATAATAATATTT\", 3)\n",
        "            \n",
        "    def test_best_hit_output(self):\n",
        "        # Testa se a função dá o resultado esperado para esses parâmetros\n",
        "        output = (0, 0, 7, 6)\n",
        "        self.assertEqual(best_hit(\"AATATAT\", \"AATATGTTATATAATAATATTT\", 3), output)\n",
        "\n",
        "    def test_best_hit_output_false(self):\n",
        "        # Testa se a função dá erro para o resultado não esperado para esses parâmetros\n",
        "        output = (0, 0, 5, 6)\n",
        "        self.assertFalse(best_hit(\"AATATAT\", \"AATATGTTATATAATAATATTT\", 3) == output)\n",
        "\n",
        "suite = unittest.TestLoader().loadTestsFromTestCase(TestBlast)\n",
        "unittest.TextTestRunner(verbosity=3).run(suite)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "<!-- LTeX: language=pt -->\n",
        "## Tarefa 7 - Motifs\n",
        "\n",
        "<div align='justify'>\n",
        "\n",
        "Na tarefa 7, desenvolvemos um algoritmo sobre Motifs.<br>\n",
        "Motifs probabilísticos são padrões ou sequências específicas que ocorrem em moléculas biológicas, como DNA, RNA e proteínas, e são fundamentais para compreender os mecanismos subjacentes à regulação genética, à identificação de famílias de proteínas e à análise de evolução molecular. Ao contrário dos motifs simples, os motifs probabilísticos levam em consideração a variabilidade nas sequências, reconhecendo a natureza estocástica e flexível dos processos biológicos.<br>\n",
        "Esses motifs são frequentemente utilizados para representar sítios de ligação de proteínas, regiões promotoras de genes e outras características funcionais em sequências biológicas. A principal distinção dos motifs probabilísticos reside na consideração das probabilidades de ocorrência de diferentes nucleotídeos ou aminoácidos em posições específicas dentro do motif.<br>\n",
        "Em resumo, os motifs probabilísticos representam uma abordagem avançada e poderosa para a análise de sequências biológicas. <br>\n",
        "Neste algoritmo, começou-se por construir a função alfabeto que aceita um tipo de sequência (DNA, RNA ou proteína) e retorna o alfabeto correspondente, de seguida criou-se a função pwm, esta gera uma matriz PWM a partir de um conjunto de sequências alinhadas, essa matriz representa as probabilidades de cada letra num alfabeto biológico estar presente numa posição específica nas sequências, fez-se posteriormente a função prob_seq que calcula a probabilidade de uma sequência específica ter sido gerada pela PWM e a função seq_mais_provavel que utiliza a PWM para determinar a subsequência mais provável de ter sido gerada por ela numa sequência maior, e por fim fez-se a função pssm, que calcula a Matriz de Pontuação Específica ao Posicionamento (PSSM) para um conjunto de sequências.<br>\n",
        "</div>"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 100,
      "metadata": {},
      "outputs": [],
      "source": [
        "def alfabeto(tipo_seq : str) -> list[str]:\n",
        "    '''\n",
        "    Esta função recebe o tipo de uma sequência e devolve o seu respetivo alfabeto.\n",
        "\n",
        "    Parameters\n",
        "    ---------\n",
        "    tipo_seq : str\n",
        "        Tipo válido de uma sequência biológica. Pode assumir os valores de DNA, RNA, ou\n",
        "        proteína.\n",
        "\n",
        "    Returns\n",
        "    -------\n",
        "    list(str)\n",
        "        Composto pelo tipo de sequência e o seu respetivo alfabeto\n",
        "    \n",
        "    Raises\n",
        "    ------\n",
        "    ValueError\n",
        "        O tipo não é válido. Os tipos de cadeia válida são: DNA, RNA ou proteina.\n",
        "    '''\n",
        "    from unidecode import unidecode\n",
        "    if tipo_seq.upper()==\"DNA\":\n",
        "        DNA=\"ACGT\"\n",
        "        return [tipo_seq.upper(),DNA]\n",
        "    elif tipo_seq.upper()==\"RNA\":\n",
        "        RNA=\"ACGU\"\n",
        "        return [tipo_seq.upper(),RNA]\n",
        "    elif unidecode(tipo_seq.upper()) in [\"PROTEIN\",\"PROTEINA\",\"PROT\"]:\n",
        "        protein=\"ABCDEFGHIKLMNPQRSTVWYZ\"\n",
        "        return [\"Proteína\", protein]\n",
        "    else:\n",
        "        raise ValueError(f\"O tipo {tipo_seq} não é válido. Os tipos de cadeia válida são: DNA, RNA ou proteina\") \n",
        "\n",
        "def pwm(seqs : list[str], tipo_seq : str, pseudo : int = 0) -> list[dict[str,float]]:\n",
        "    '''\n",
        "    Esta função recebe uma lista de sequências alinhadas e devolve uma matriz desingada de position weigth matrix (PWM), onde se representa\n",
        "    a probabilidade de cada letra de um dado alfabeto biológico estar presente numa determinada posição.\n",
        "\n",
        "    Parameters\n",
        "    ----------\n",
        "    seqs : list(str)\n",
        "        Contêm um conjunto de sequências alinhadas em formato de string.\n",
        "\n",
        "    tipo_seq : str\n",
        "        Tipo da sequência que se pretende realiazar a PWM. Pode assumir o valor de DNA, RNA ou proteína.\n",
        "\n",
        "    pseudo : int ou float\n",
        "        Valor a utilizar para realizar a pseudocontagem. Por padrão o valor é 0.\n",
        "\n",
        "    Returns\n",
        "    -------\n",
        "    PWM : list(dict)\n",
        "        Valor da probabilidade de cada letra do alfabeto estar presente em cada posição das sequências.\n",
        "    \n",
        "    Raises\n",
        "    ------\n",
        "    AssertionError\n",
        "        Na sequencia {seq}, o elemento {elem} na posição {pos+1} não se encontra no alfabeto do {alfa[0]}.\n",
        "        A sequência {seq} não possui o mesmo tamanho que as restantes.\n",
        "    '''\n",
        "    alfa=alfabeto(tipo_seq)\n",
        "    \n",
        "    tamanho=[]\n",
        "    \n",
        "    for I,seq in enumerate(seqs):\n",
        "        tamanho.append(len(seq))\n",
        "        for pos,elem in enumerate(seq):\n",
        "            assert elem in alfa[1],f\"Na sequencia {seq}, o elemento {elem} na posição {pos+1} não se encontra no alfabeto do {alfa[0]}\"\n",
        "        assert tamanho[I]==tamanho[I-1],f\"A sequência {seq} não possui o mesmo tamanho que as restantes\"\n",
        "\n",
        "    elementos_coluna=list(zip(*seqs))\n",
        "\n",
        "    PWM=[]\n",
        "\n",
        "    for coluna in elementos_coluna:\n",
        "        contagem={}\n",
        "        for elem in alfa[1]:\n",
        "            contagem[elem]=(coluna.count(elem) + pseudo)/(len(seqs)+len(alfa[1])*pseudo)\n",
        "        \n",
        "        PWM.append(contagem)  \n",
        "    \n",
        "    return PWM\n",
        "\n",
        "def prob_seq (seq : str, pwm : list[dict[str,float]]) -> float:\n",
        "    '''\n",
        "    Esta função calcula a probabilidade de uma determinada sequencia ter sido gerada pela PWM.\n",
        "\n",
        "    Parameters\n",
        "    ---------\n",
        "    seq:str\n",
        "        Sequência que se pretende calcular a probabilidade de ter sido gerada pela PWM.\n",
        "    \n",
        "    pwm:list(dict[str,floar])\n",
        "        Corresponde às probabilidades de cada elemento aparecer nas várias posições da sequência.\n",
        "\n",
        "    Returns\n",
        "    -------\n",
        "    prod : float\n",
        "        Probabilidade de a sequencia fornecida ter sido gerada pela PWM.\n",
        "\n",
        "    Raises\n",
        "    ------\n",
        "    AssertionError\n",
        "        A sequência não é do mesmo tamanho que a PWM.\n",
        "    '''\n",
        "    assert len(seq)<=len(pwm),f\"A sequência {seq} não é do mesmo tamanho que a PWM\"\n",
        "\n",
        "    prod=1\n",
        "    for I,elem in enumerate(seq):\n",
        "        prod=prod*pwm[I][elem]\n",
        "    return prod\n",
        "\n",
        "def seq_mais_provavel(seq : str, pwm : list[dict[str,float]], resultado : str = \"Max\") -> str:\n",
        " '''\n",
        "  Esta função recebe uma sequência e utiliza a PWM para determinar qual a subsequência mais provável de ter sido gerada pela PWM.\n",
        "\n",
        "  Parameters\n",
        "  --------\n",
        "  seq : str\n",
        "    sequência na qual se pretende analisar a probablidade de cada subsequência ter sido gerada pela PWM.\n",
        "\n",
        "  pwm : list(dict[str,float])\n",
        "    PWM de um determinado alinhamento\n",
        "\n",
        "  resultado : \n",
        "  str\n",
        "    Corresponde ao valor que se pretende obter, por exemplo, quando assume o valor \"Máximo\" devolve a(s) subsequência(s) \n",
        "    com maior probabilidade de ter sido gerada pela PWM, quando assume o valor mínimo devolve a(s) sequência(s) com menor probabildade\n",
        "    de serem formadas pela PWM\n",
        "\n",
        "  Returns\n",
        "  -------\n",
        "  str\n",
        "    Corresponde à sequência de maior/menor probabilidade\n",
        "  Raises\n",
        "  ------\n",
        "  AssertionError\n",
        "    A sequência não pode ser utilizada para determinar a sequência mais próvavel. A sequência deve ter, no mínimo, o mesmo tamnho da PWM.\n",
        " '''\n",
        "\n",
        " assert len(seq)>=len(pwm),f'''\n",
        " A sequência {seq} não pode ser utilizada para determinar a sequência mais próvavel. A sequência deve ter, no mínimo, o mesmo tamnho da PWM\n",
        " '''\n",
        " w=len(pwm)\n",
        " snips=[seq[P:P+w] for P in range(len(seq)-w+1)]\n",
        " res={}\n",
        " for snip in snips:\n",
        "    prob=prob_seq(snip,pwm)\n",
        "    res[snip]=prob\n",
        "  \n",
        " if resultado.upper() in ['MAX','MAXIMO']:\n",
        "    return max(res, key=res.get)\n",
        " \n",
        " if resultado.upper() in ['MIN','MINIMO']:\n",
        "     return min(res, key=res.get)\n",
        " \n",
        "def pssm(seqs : list[str], tipo_seq : str, pseudo : int = 1) -> list[dict]:\n",
        "    '''\n",
        "    Calcula a Matriz de Pontuação Específica ao Posicionamento (PSSM) para um conjunto de sequências.\n",
        "\n",
        "    Parameters\n",
        "    --------\n",
        "    seqs : list(str)\n",
        "      Lista de sequências a serem processadas.\n",
        "\n",
        "    tipo_seq : str\n",
        "      Tipo de sequência ('DNA', 'RNA' ou 'PROTEIN').\n",
        "\n",
        "    pseudo : int\n",
        "      Valor a ser adicionado para evitar problemas com contagens zero\n",
        "\n",
        "    Returns\n",
        "    -------\n",
        "    list of dict\n",
        "      Lista de dicionários representando a PSSM.\n",
        "    \n",
        "    Raises\n",
        "    ------\n",
        "    AssetionError\n",
        "      Na sequencia, o elemento na posição {pos+1} não se encontra no alfabeto do {alfa[0]}.\n",
        "      A sequência {seq} não possui o mesmo tamanho que as restantes.\n",
        "    '''\n",
        "    import math\n",
        "    alfa=alfabeto(tipo_seq)\n",
        "    tamanho=[]\n",
        "    for I,seq in enumerate(seqs):\n",
        "        tamanho.append(len(seq))\n",
        "        for pos,elem in enumerate(seq):\n",
        "            assert elem in alfa[1],f\"Na sequencia {seq}, o elemento {elem} na posição {pos+1} não se encontra no alfabeto do {alfa[0]}\"\n",
        "        assert tamanho[I]==tamanho[I-1],f\"A sequência {seq} não possui o mesmo tamanho que as restantes\"\n",
        "\n",
        "    elementos=list(zip(*seqs))\n",
        "\n",
        "    PSSM=[{b:math.log2(((elemento.count(b)+pseudo)/(len(seqs)+len(alfa[1])*pseudo))/(1/len(alfa[1]))) for b in alfa[1]}  for elemento in elementos]\n",
        "\n",
        "    return PSSM"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 101,
      "metadata": {},
      "outputs": [
        {
          "data": {
            "text/plain": [
              "[{'A': 0.5849625007211562, 'C': 0.0, 'G': -1.0, 'T': 0.0},\n",
              " {'A': 0.0, 'C': -1.0, 'G': 0.0, 'T': 0.5849625007211562},\n",
              " {'A': 0.0, 'C': 0.0, 'G': 0.5849625007211562, 'T': -1.0},\n",
              " {'A': -1.0, 'C': 0.0, 'G': -1.0, 'T': 1.0},\n",
              " {'A': -1.0, 'C': 0.0, 'G': 1.0, 'T': -1.0},\n",
              " {'A': 1.3219280948873624, 'C': -1.0, 'G': -1.0, 'T': -1.0}]"
            ]
          },
          "execution_count": 101,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "#Exemplo prático\n",
        "pssm([\"ATGCGA\", \"CAGTCA\", \"TTATGA\", \"AGCTGA\"], tipo_seq = \"DNA\", pseudo = 1)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 102,
      "metadata": {},
      "outputs": [
        {
          "data": {
            "text/plain": [
              "[{'A': 1.1926450779423958,\n",
              "  'C': -0.8073549220576043,\n",
              "  'G': -0.8073549220576043,\n",
              "  'T': -0.8073549220576043},\n",
              " {'A': -0.8073549220576043,\n",
              "  'C': -0.8073549220576043,\n",
              "  'G': 1.1926450779423958,\n",
              "  'T': -0.8073549220576043},\n",
              " {'A': 0.19264507794239583,\n",
              "  'C': 0.19264507794239583,\n",
              "  'G': -0.8073549220576043,\n",
              "  'T': 0.19264507794239583}]"
            ]
          },
          "execution_count": 102,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "#Exemplo prático1\n",
        "pssm((\"AGC\",\"AGA\",\"AGT\"),\"DNA\")"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "### Testes de unidade"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 103,
      "metadata": {},
      "outputs": [
        {
          "name": "stderr",
          "output_type": "stream",
          "text": [
            "test_alfabeto_caracter_errado_dna (__main__.TestMOTIFS.test_alfabeto_caracter_errado_dna) ... ok\n",
            "test_alfabeto_caracter_errado_protein (__main__.TestMOTIFS.test_alfabeto_caracter_errado_protein) ... ok\n",
            "test_alfabeto_caracter_errado_rna (__main__.TestMOTIFS.test_alfabeto_caracter_errado_rna) ... ok\n",
            "test_alfabeto_dna_valido (__main__.TestMOTIFS.test_alfabeto_dna_valido) ... ok\n",
            "test_alfabeto_protein_valido (__main__.TestMOTIFS.test_alfabeto_protein_valido) ... ok\n",
            "test_alfabeto_rna_valido (__main__.TestMOTIFS.test_alfabeto_rna_valido) ... ok\n",
            "test_prob_seq_caracter_errado (__main__.TestMOTIFS.test_prob_seq_caracter_errado) ... ok\n",
            "test_prob_seq_valido (__main__.TestMOTIFS.test_prob_seq_valido) ... ok\n",
            "test_pssm_caracter_invalido (__main__.TestMOTIFS.test_pssm_caracter_invalido) ... ok\n",
            "test_pssm_tamanhos_de_sequencia_diferentes (__main__.TestMOTIFS.test_pssm_tamanhos_de_sequencia_diferentes) ... ok\n",
            "test_pssm_valido (__main__.TestMOTIFS.test_pssm_valido) ... ok\n",
            "test_pwm_caracter_invalido_DNA (__main__.TestMOTIFS.test_pwm_caracter_invalido_DNA) ... ok\n",
            "test_pwm_caracter_invalido_RNA (__main__.TestMOTIFS.test_pwm_caracter_invalido_RNA) ... ok\n",
            "test_pwm_caracter_invalido_protein (__main__.TestMOTIFS.test_pwm_caracter_invalido_protein) ... ok\n",
            "test_pwm_tamanhos_diferentes (__main__.TestMOTIFS.test_pwm_tamanhos_diferentes) ... ok\n",
            "test_pwm_valid (__main__.TestMOTIFS.test_pwm_valid) ... ok\n",
            "test_seq_mais_provavel_max_prob (__main__.TestMOTIFS.test_seq_mais_provavel_max_prob) ... ok\n",
            "test_seq_mais_provavel_min_prob (__main__.TestMOTIFS.test_seq_mais_provavel_min_prob) ... ok\n",
            "\n",
            "----------------------------------------------------------------------\n",
            "Ran 18 tests in 0.060s\n",
            "\n",
            "OK\n"
          ]
        },
        {
          "data": {
            "text/plain": [
              "<unittest.runner.TextTestResult run=18 errors=0 failures=0>"
            ]
          },
          "execution_count": 103,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "import unittest\n",
        "\n",
        "class TestMOTIFS(unittest.TestCase):\n",
        "    \n",
        "    def test_alfabeto_caracter_errado_dna(self):\n",
        "        with self.assertRaises(ValueError):\n",
        "            alfabeto(\"DNA%\")\n",
        "\n",
        "    def test_alfabeto_caracter_errado_rna(self):\n",
        "        with self.assertRaises(ValueError):\n",
        "            alfabeto(\"RNA/\")\n",
        "\n",
        "    def test_alfabeto_caracter_errado_protein(self):\n",
        "        with self.assertRaises(ValueError):\n",
        "            alfabeto(\"protein@\")\n",
        "\n",
        "    def test_alfabeto_dna_valido(self):\n",
        "        self.assertEqual(alfabeto(\"DNA\"), [\"DNA\", \"ACGT\"])\n",
        "\n",
        "    def test_alfabeto_rna_valido(self):\n",
        "        self.assertEqual(alfabeto(\"RNA\"), [\"RNA\", \"ACGU\"])\n",
        "\n",
        "    def test_alfabeto_protein_valido(self):\n",
        "        self.assertEqual(alfabeto(\"protein\"), [\"Proteína\", \"ABCDEFGHIKLMNPQRSTVWYZ\"])\n",
        "\n",
        "    def test_pwm_caracter_invalido_DNA(self):\n",
        "        with self.assertRaises(AssertionError):\n",
        "            pwm((\"ACAT\", \"AGCP\", \"TGGT\"), \"DNA\")\n",
        "    \n",
        "    def test_pwm_caracter_invalido_RNA(self):\n",
        "        with self.assertRaises(AssertionError):\n",
        "            pwm((\"A&AU\", \"AGCU\", \"AUAU\"), \"RNA\")\n",
        "\n",
        "    def test_pwm_caracter_invalido_protein(self):\n",
        "        with self.assertRaises(AssertionError):\n",
        "            pwm((\"ACMN\", \"TGCC\", \"WYZ/\"), \"protein\")\n",
        "    \n",
        "    def test_pwm_tamanhos_diferentes(self):\n",
        "        with self.assertRaises(AssertionError):\n",
        "            pwm((\"ACGT\", \"TGCA\", \"ACG\"), \"DNA\")\n",
        "\n",
        "    def test_pwm_valid(self):\n",
        "        self.assertEqual(pwm((\"AGC\", \"AGA\", \"AGT\"), \"DNA\"), [\n",
        "        {'A': 1.0, 'C': 0.0, 'G': 0.0, 'T': 0.0},\n",
        "        {'A': 0.0, 'C': 0.0, 'G': 1.0, 'T': 0.0},\n",
        "        {'A': 0.3333333333333333, 'C': 0.3333333333333333, 'G': 0.0, 'T': 0.3333333333333333}])\n",
        "\n",
        "    def test_prob_seq_caracter_errado(self):\n",
        "        with self.assertRaises(AssertionError):\n",
        "            prob_seq(\"AGC/\",[{'A': 1.0, 'C': 0.0, 'G': 0.0, 'T': 0.0},\n",
        "            {'A': 0.0, 'C': 0.0, 'G': 1.0, 'T': 0.0},\n",
        "            {'A': 0.3333333333333333,\n",
        "            'C': 0.3333333333333333,\n",
        "            'G': 0.0,\n",
        "            'T': 0.3333333333333333}] )\n",
        "\n",
        "    def test_prob_seq_valido(self):\n",
        "        self.assertEqual(prob_seq(\"AGC\", [{'A': 1.0, 'C': 0.0, 'G': 0.0, 'T': 0.0},\n",
        "            {'A': 0.0, 'C': 0.0, 'G': 1.0, 'T': 0.0},\n",
        "            {'A': 0.3333333333333333,\n",
        "            'C': 0.3333333333333333,\n",
        "            'G': 0.0,\n",
        "            'T': 0.3333333333333333}]),0.3333333333333333 ) \n",
        "\n",
        "    def test_seq_mais_provavel_max_prob(self):  \n",
        "        self.assertEqual(seq_mais_provavel(\"AGC\", [\n",
        "        {'A': 1.0, 'C': 0.0, 'G': 0.0, 'T': 0.0},\n",
        "        {'A': 0.0, 'C': 0.0, 'G': 1.0, 'T': 0.0},\n",
        "        {'A': 0.3333333333333333, 'C': 0.3333333333333333, 'G': 0.0, 'T': 0.3333333333333333}\n",
        "        ], resultado=\"MAX\"),\"AGC\")\n",
        "     \n",
        "\n",
        "    def test_seq_mais_provavel_min_prob(self):\n",
        "        self.assertEqual(seq_mais_provavel(\"AGC\", [\n",
        "        {'A': 1.0, 'C': 0.0, 'G': 0.0, 'T': 0.0},\n",
        "        {'A': 0.0, 'C': 0.0, 'G': 1.0, 'T': 0.0},\n",
        "        {'A': 0.3333333333333333, 'C': 0.3333333333333333, 'G': 0.0, 'T': 0.3333333333333333}\n",
        "        ], resultado=\"MIN\"),\"AGC\")\n",
        "\n",
        "    def test_pssm_tamanhos_de_sequencia_diferentes(self):\n",
        "        with self.assertRaises(AssertionError):\n",
        "            pssm((\"ACT\", \"TGCA\", \"TCG\"), \"DNA\")\n",
        "\n",
        "    def test_pssm_caracter_invalido(self):\n",
        "        with self.assertRaises(AssertionError):\n",
        "            pssm((\"AC/\", \"UGC\", \"UCG\"), \"RNA\")\n",
        "   \n",
        "    def test_pssm_valido(self):\n",
        "        self.assertEqual(pssm([\"AGC\", \"AGA\", \"AGT\"], \"DNA\"), [\n",
        "        {'A': 1.1926450779423958, 'C': -0.8073549220576043, 'G': -0.8073549220576043, 'T': -0.8073549220576043},\n",
        "        {'A': -0.8073549220576043, 'C': -0.8073549220576043, 'G': 1.1926450779423958, 'T': -0.8073549220576043},\n",
        "        {'A': 0.19264507794239583, 'C': 0.19264507794239583, 'G': -0.8073549220576043, 'T': 0.19264507794239583}\n",
        "        ])\n",
        "\n",
        "suite = unittest.TestLoader().loadTestsFromTestCase(TestMOTIFS)\n",
        "unittest.TextTestRunner(verbosity=3).run(suite)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "<!-- LTeX: language=pt -->\n",
        "# Tarefa 8 - Análise filogenética\n",
        "\n",
        "<div align='justify'>\n",
        "\n",
        "Na tarefa 8, foi proposta a resolução do algoritmo da Análise filogenética. <br>\n",
        "A análise filogenética dedica-se ao estudo das relações evolutivas entre diferentes organismos. Essa abordagem é fundamental para compreender a evolução biológica e as interconexões entre as diversas formas de vida.<br>\n",
        "Existem várias técnicas e métodos para a construção de árvores filogenéticas, e a escolha dependerá do tipo de dados disponíveis e das perguntas a responder.<br>\n",
        "No algoritmo, começou-se por construir a função leitura_seqs, que lê sequências de um arquivo em formato FASTA. Cada sequência é associada a um nome precedido por '>'. Com a função matriz_distancias, calcula-se a matriz de distâncias entre as sequências fornecidas. A distância entre cada par de sequências é calculada pela função calculate_distance.<br>\n",
        "Prosseguiu-se para a construção da função find_min_distance, que percorre a matriz e encontra os índices correspondentes à menor distância numérica presente na matriz, seguindo-se a construção de agru_seq_sem, que recebe os índices de duas sequências semelhantes e utiliza esses índices para compor um novo nome resultante da combinação dos nomes originais dessas sequências presentes na matriz. De seguida, com a função cal_novas_dis, recebe-se uma matriz, os índices de duas sequências semelhantes e o nome resultante da combinação dessas sequências. Calcula as novas distâncias entre a sequência agregada e as demais sequências presentes na matriz armazenando o resultado em um dicionário aninhado. Por fim, define-se a função nova_matriz, que recebe uma matriz de distâncias, os índices de duas sequências semelhantes e o nome resultante da combinação dessas sequências. Ela gera uma nova matriz de distâncias após agregar as sequências semelhantes, adicionando a última linha à matriz original.\n",
        "\n",
        "</div>"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "import re\n",
        "\n",
        "def leitura_seqs(nome_file:str)->dict[str,str]:\n",
        "    \"\"\"\n",
        "    Lê sequências a partir de um arquivo em formato FASTA.\n",
        "\n",
        "    Parameters\n",
        "    ----------\n",
        "    nome_file : str\n",
        "      Nome do arquivo (sem a extensão .fa) contendo as sequências no formato FASTA.\n",
        "\n",
        "    Returns\n",
        "    -------\n",
        "    dict\n",
        "      Um dicionário onde as chaves são os nomes das sequências e os valores são as sequências correspondentes.\n",
        "    \"\"\"\n",
        "    with open(nome_file+'.fa','r') as file:\n",
        "        seqs={}\n",
        "        seq=''\n",
        "        nome=''\n",
        "        estado=False\n",
        "        for line in file:\n",
        "            if '>' in line:\n",
        "                if len(nome)!=0 and len(seq)!=0:\n",
        "                    seq=seq.replace('\\n','')\n",
        "                    seqs[nome]=seq\n",
        "                    seq=''\n",
        "                    estado=False\n",
        "\n",
        "                res=re.findall(r'[A-Z_\\d.]+',line)\n",
        "                nome=res[0]\n",
        "                estado=True\n",
        "                continue\n",
        "\n",
        "            if estado:\n",
        "                seq+=line\n",
        "\n",
        "    seq=seq.replace('\\n','')\n",
        "    seqs[nome]=seq\n",
        "    return seqs\n",
        "\n",
        "def calculate_distance(seq1:str, seq2:str,seq_type:str='protein')->int:\n",
        "    '''\n",
        "    Calcula a distância de duas sequências utiliznado o algortimo de Needleman Wunsch\n",
        "\n",
        "    Parameters\n",
        "    ----------\n",
        "    seq1 :str\n",
        "        Sequência que se pretende calcular a distância\n",
        "    \n",
        "    seq2: str\n",
        "        Sequência com a qual se vai alinhar a sequência 1\n",
        "    \n",
        "    seq_type: str\n",
        "        Corresponde ao tipo de sequência em análise. Por padrão é definido como protein\n",
        "\n",
        "    Returns\n",
        "    ---------\n",
        "    int\n",
        "        Corresponde ao resultado da distância que será o simétrico do score obtido no algoritmo de Needleman Wunsch\n",
        "    '''\n",
        "\n",
        "    return -needleman_wunsch(seq1, seq2, seq_tipo=seq_type,matrizes=False)[0]\n",
        "\n",
        "def matriz_distancias(seqs:dict[str,str],seq_type='protein')->list[list]:\n",
        "    \"\"\"\n",
        "    Calcula a matriz de distâncias entre as sequências fornecidas.\n",
        "\n",
        "    Parameters\n",
        "    ----------\n",
        "    seqs : dict\n",
        "      Um dicionário onde as chaves são os nomes das sequências e os valores são as próprias sequências.\n",
        "    \n",
        "    seq_type: str\n",
        "      Corresponde ao tipo de sequência em análise. Por padrão é definido como protein\n",
        "\n",
        "    Returns\n",
        "    -------\n",
        "    list of list\n",
        "      Uma matriz de distâncias entre as sequências.\n",
        "\n",
        "    Raises\n",
        "    ------\n",
        "    ValueError\n",
        "      Se o dicionário de sequências estiver vazio.\n",
        "    \"\"\"\n",
        "    assert seq_type.upper() in ['DNA','RNA','PROTEIN']\n",
        "    nlinhas= len(seqs)+ 1\n",
        "    ncolunas=len(seqs)+ 1\n",
        "    matriz=[[0]*ncolunas for linhas in range(nlinhas)] #inicializar a matriz\n",
        "    n_seqs=['-']\n",
        "\n",
        "    for seq in seqs: #nome das sequências em estudo\n",
        "        n_seqs.append(seq)\n",
        "    \n",
        "    matriz[0]=[seq for seq in n_seqs] #prencher a primeira linha com os nomes da sequências\n",
        "    for linha in range(1,nlinhas):\n",
        "        matriz[linha][0]=n_seqs[linha] #prencher a primeira coluna de cada linha com o nome da sequência\n",
        "\n",
        "    for linha in range(1,nlinhas):\n",
        "        for coluna in range(1,ncolunas):\n",
        "            if linha==coluna:\n",
        "                pass\n",
        "\n",
        "            else:\n",
        "                matriz[linha][coluna]=calculate_distance(seqs[n_seqs[linha]],seqs[n_seqs[coluna]],seq_type)\n",
        "\n",
        "    return matriz\n",
        "\n",
        "def find_min_distance(matrix:list[list])->tuple[int,int]:\n",
        "    \"\"\"\n",
        "    Encontra os índices correspondentes à menor distância numa matriz.\n",
        "\n",
        "    Parameters\n",
        "    ----------\n",
        "    matrix : list of list\n",
        "      Uma matriz contendo distâncias. A primeira linha corresponde ao nomes das sequências e para as restantes linhas\n",
        "      a primeira coluna corresponde ao nome da sequência\n",
        "\n",
        "    Returns\n",
        "    -------\n",
        "    tuple of int\n",
        "      Um tuplo de dois inteiros representando os índices correspondentes à menor distância.\n",
        "\n",
        "    Raises\n",
        "    ------\n",
        "    AssertionError\n",
        "      - Se a matriz estiver vazia\n",
        "      - Caso o elemento em análise não seja um inteiro ou um float.\n",
        "    \"\"\"\n",
        "    assert len(matrix)!=0\n",
        "\n",
        "    min_distance = float('inf')\n",
        "    min_indices = (0, 0)\n",
        "\n",
        "    for I in range(1,len(matrix)):\n",
        "        for J in range(1,len(matrix)):\n",
        "            assert type(matrix[I][J])==int or type(matrix[I][J])==float\n",
        "            if matrix[I][J]!=0:\n",
        "                if matrix[I][J]<min_distance:\n",
        "                    min_distance=matrix[I][J]\n",
        "                    min_indices=(I,J)\n",
        "\n",
        "    return min_indices\n",
        "\n",
        "def agru_seq_sem(seq_similar:tuple[int,int],matriz:list[list])->str:\n",
        "    \"\"\"\n",
        "    Agrupa duas sequências semelhantes com base nas informações fornecidas por uma matriz.\n",
        "\n",
        "    Parameters\n",
        "    ----------\n",
        "    seq_similar : tuple of int\n",
        "      Um tuplo que contem os índices das sequências semelhantes na matriz.\n",
        "\n",
        "    matriz : list of list\n",
        "      Uma matriz que contem informações sobre a semelhança das sequências.\n",
        "\n",
        "    Returns\n",
        "    -------\n",
        "    str\n",
        "      O nome resultante da combinação das sequências semelhantes.\n",
        "\n",
        "    Raises\n",
        "    -------\n",
        "    AssertionError\n",
        "        Quando o nome das duas sequências a agregar é igual\n",
        "    \"\"\"\n",
        "    linha=seq_similar[0]\n",
        "    coluna=seq_similar[1]\n",
        "    assert matriz[linha][0]!= matriz[0][coluna]\n",
        "    nome=matriz[linha][0]+' & '+ matriz[0][coluna]\n",
        "    return nome\n",
        "\n",
        "def calc_novas_dis(matriz:list[list],seq_similar:tuple[int,int],nome:str)->dict[str,dict[str,float]]:\n",
        "    \"\"\"\n",
        "    Calcula as novas distâncias após agregar duas sequências semelhantes numa matriz.\n",
        "\n",
        "    Parameters\n",
        "    ----------\n",
        "    matriz : list of list\n",
        "      Matriz que contem informações sobre as sequências.\n",
        "\n",
        "    seq_similar : tuple of int\n",
        "      Um tuplo que contem os índices das sequências semelhantes na matriz.\n",
        "\n",
        "    nome : str\n",
        "      O nome resultante da combinação das sequências semelhantes.\n",
        "\n",
        "    Returns\n",
        "    -------\n",
        "    dict of dict\n",
        "      Um dicionário que contem as novas distâncias calculadas após a agregação das sequências.\n",
        "    \"\"\"\n",
        "    seq1=matriz[seq_similar[0]][0] # nome da sequencia 1 a agregar\n",
        "    seq2=matriz[0][seq_similar[1]] # nome da sequencia 2 a agregar\n",
        "    pos_coluna=[] #colunas que correspondem as sequencias a agregar\n",
        "    calc={}\n",
        "    calc[nome]={}\n",
        "\n",
        "    for I in range(len(matriz)):\n",
        "        if I ==0:\n",
        "            for J,elem in enumerate(matriz[I]): #selecionar as colunas de interesse\n",
        "                if elem==seq1 or elem==seq2:\n",
        "                    pos_coluna.append(J)\n",
        "\n",
        "        else:\n",
        "            if matriz[I][0]==seq1 or matriz[I][0]==seq2: #saltar as sequências a agregar\n",
        "                pass\n",
        "            else:  # calcula da distância para as sequências agregadas e as restantes\n",
        "                dist=0\n",
        "                nome_seq=matriz[I][0]\n",
        "                for col in pos_coluna:\n",
        "                    dist+=matriz[I][col]\n",
        "                dist=dist/2\n",
        "                calc[nome][nome_seq]=dist\n",
        "    \n",
        "    return calc\n",
        "\n",
        "def nova_matriz(matriz:list[list],seq_similar:tuple[int,int],nome:str):\n",
        "    \"\"\"\n",
        "    Gera uma nova matriz de distâncias após agregar duas sequências semelhantes.\n",
        "\n",
        "    Parameters\n",
        "    ----------\n",
        "    matriz : list of list\n",
        "      Matriz original que contem informações sobre as distâncias entre as sequências.\n",
        "\n",
        "    seq_similar : tuple of int\n",
        "      Um tuplo que contem os índices das sequências semelhantes na matriz.\n",
        "\n",
        "    nome : str\n",
        "      O nome resultante da combinação das sequências semelhantes.\n",
        "\n",
        "    Returns\n",
        "    -------\n",
        "    list of list\n",
        "      Uma nova matriz de distâncias após a agregação das sequências.\n",
        "    \"\"\"\n",
        "    seq1=matriz[seq_similar[0]][0] # nome da sequencia a agregar\n",
        "    seq2=matriz[0][seq_similar[1]] # nome da sequencia a agregar\n",
        "    novas_dist=calc_novas_dis(matriz,seq_similar,nome)\n",
        "    nova_matriz=[] #iniciar a nova matriz\n",
        "    pos_col=[] #colunas das sequências a agregar\n",
        "\n",
        "    for I in range(len(matriz)): #copia da matriz de distâncias original\n",
        "        linha=[]\n",
        "        if I==0:\n",
        "            for J,elem in enumerate(matriz[I]):\n",
        "                if elem==seq1 or elem==seq2:\n",
        "                    pos_col.append(J)\n",
        "                    pass\n",
        "                else:\n",
        "                    linha.append(elem)\n",
        "            nova_matriz.append(linha)\n",
        "            continue\n",
        "        \n",
        "        else:\n",
        "            if matriz[I][0]==seq1 or matriz[I][0]==seq2: # as linhas que correspondem as seqs a agregar são ignoradas\n",
        "                continue\n",
        "\n",
        "            else: \n",
        "                for J,elem in enumerate(matriz[I]): #seleção das colunas de interesse para um certa linha\n",
        "                    if J not in pos_col: #as colunas que correspondem as seqs a agregar são ignoradas\n",
        "                        linha.append(elem)\n",
        "\n",
        "        nova_matriz.append(linha)\n",
        "\n",
        "    nova_matriz[0]=nova_matriz[0] + [nome] #adiconar na primeira linha as seqs agregadas\n",
        "\n",
        "    linhas=len(nova_matriz)\n",
        "    for I in range(1,linhas): #adicionar a partir da linha 1 o valor da nova distancia\n",
        "        for seq in novas_dist[nome]:\n",
        "            if seq== nova_matriz[I][0]:\n",
        "                nova_matriz[I].append(novas_dist[nome][seq])\n",
        "    \n",
        "    ult_linha=[] #construção da ultima linha\n",
        "    ult_linha.append(nome)\n",
        "    for I in range(1,linhas):\n",
        "        ult_linha.append(nova_matriz[I][-1])\n",
        "    ult_linha.append(0)\n",
        "\n",
        "    nova_matriz.append(ult_linha) #adicicao da ultima linha à matriz\n",
        "\n",
        "    return nova_matriz\n",
        "\n",
        "def arvore(nome_file:str,seq_type:str='protein')->list:\n",
        "    \"\"\"\n",
        "    Constrói uma árvore filogenética iterativa com base num arquivo de sequências.\n",
        "\n",
        "    Parameters\n",
        "    ----------\n",
        "    nome_file : str\n",
        "      O nome do arquivo que contem as sequências a serem processadas.\n",
        "    \n",
        "    seq_type: str\n",
        "      Corresponde ao tipo de sequência em análise. Por padrão é definido como protein\n",
        "\n",
        "    Returns\n",
        "    -------\n",
        "    list\n",
        "      Uma lista que representa a árvore filogenética iterativa.\n",
        "\n",
        "    Raises\n",
        "    ----------\n",
        "    AssertionError\n",
        "        - Se a matriz estiver vazia\n",
        "        - Caso o elemento em análise não seja um inteiro ou um float.\n",
        "        - Se uma das seqências não for do tipo string\n",
        "        - Se uma das sequências for uma string vazia\n",
        "        - Se seq_type não for 'DNA', 'RNA' ou 'PROTEIN'.\n",
        "        - Se uma das sequencias fornecidas não é um acido nucleico válido quando seq_type assume o valor DNA ou RNA.\n",
        "        - Se seq_type for 'PROTEIN' e uma das sequências não for uma proteína válida.\n",
        "\n",
        "    \"\"\"\n",
        "    res=[]\n",
        "    seqs=leitura_seqs(nome_file)\n",
        "    mat_dist=matriz_distancias(seqs,seq_type)\n",
        "    min_dist=find_min_distance(mat_dist)\n",
        "    nome=agru_seq_sem(min_dist,mat_dist)\n",
        "    print('Cluster 1: {}'.format(nome))\n",
        "    res.append(nome)\n",
        "    cont=1\n",
        "\n",
        "    while len(res)!=len(seqs)-1:\n",
        "        cont+=1\n",
        "        mat_dist=nova_matriz(mat_dist,min_dist,nome)\n",
        "        min_dist=find_min_distance(mat_dist)\n",
        "        nome=agru_seq_sem(min_dist,mat_dist)\n",
        "        res.append(nome)\n",
        "        print('Cluster {}: {}'.format(cont,nome))\n",
        "\n",
        "    return res"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "#exemplo da construção de uma arvore filogenética\n",
        "arvore('exemplo')"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "### Testes de unidade"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "import unittest\n",
        "\n",
        "class TestFilo(unittest.TestCase):\n",
        "    def test_leitura_seqs(self):\n",
        "        res={'NP_003733.2': 'MSDSVILRSIKKFGEENDGFESDKSYNNDKKSRLQDEKKGDGVRVGFFQLFRFSSSTDIWLMFVGSLCAFLHGIAQPGVLLIFGTMTDVFIDYDVELQELQIPGKACVNNTIVWTNSSLNQNMTNGTRCGLLNIESEMIK',\n",
        "             'B8K1W2.1': 'MSDAVILRSVKKFGEDNYGFESSTFYNNDKNSGLQDERKGDSSQVGFFQLFRFSSTTDIWLMFVGSLCAFLHGLSHPGVLLIFGTMTDVFIAYDTELQELKIPGKACVNNTIVWINSSLNQNVTNGTQCGLLDIESEMIK', \n",
        "             'NP_00000': 'MSVIRSVKFGEEFESDKSLQDEKKGKACVNSRLQDEKKGDGVRVGFFQLFRFSSSTDIWLMFVGSLCAFKLHGLSHPGVLLIFGTMTDVFIAYDTELQELKIPGKACVNNTIVWINSSLNQNVTNGTQCGLLDIESEMIK', \n",
        "             'Q9N0V3.1': 'MSDSVILRSVKKFGEENHGFESDGSYNNEKKSRLQDKKKSDSVRIGFFQLFRFSSWTDIWLMCMGSLCACIHGIAQPGVLLIFGTMTDVFIDYDTELQELKIPGKACVNNTIVWINSSLNQNVTNGTRCGLLDIESEMIR', \n",
        "             'O70127.1': 'MSDSVILRSVKKFGEENHAFESDGSHNNDKKSRLQDKMKEGDIRVGFFELFRFSSSKDIWLMLMGGVCALLHGMAQPGILIIFGIMTDIFIKYDIERQELEIPGKACVNNTIVWINSSFHQNMTNGTVCGLVDIESEMIK'}\n",
        "\n",
        "        self.assertEqual(leitura_seqs('seqs'),res)\n",
        "    \n",
        "    def test_calculate_distance(self):\n",
        "        seqs1=['MSDSVILRSIKKFGEENDGFESDKSYNNDKK','MSDAVILRSVKKFGEDNYGFESSTFYN']\n",
        "        seqs2=['MSVIRSVKFGEEFESDKSLQDEKKGKACVNSRLQ','MSDSVILRSVKKFGEENHGFESDGSYNNEKKSRLQDKKKSDSVR']\n",
        "        res=[-34,-40]\n",
        "        for x,y,z in zip(seqs1,seqs2,res):\n",
        "            self.assertEqual(calculate_distance(x,y),z)\n",
        "    \n",
        "    def test_matriz_distancias(self):\n",
        "        seqs={'seq1':'MSDSVILRSIKKFGEENDGFESDKSYNNDKK','seq2':'MSDAVILRSVKKFGEDNYGFESSTFYN',\n",
        "              'seq3':'MSVIRSVKFGEEFESDKSLQDEKKGKACVNSRLQ','seq4':'MSDSVILRSVKKFGEENHGFESDGSYNNEKKSRLQDKKKSDSVR'}\n",
        "        res=[['-','seq1','seq2','seq3','seq4'],['seq1',0,-87,-34,-92],\n",
        "             ['seq2',-87,0,-1,-40],['seq3',-34,-1,0,-56],['seq4',-92,-40,-56,0]]\n",
        "        self.assertEqual(matriz_distancias(seqs),res)\n",
        "\n",
        "    def test_find_min_distance(self):\n",
        "        matrix=[['-','seq1','seq2','seq3','seq4'],['seq1',0,-87,-34,-92],\n",
        "               ['seq2',-87,0,-1,-40],['seq3',-34,-1,0,-56],['seq4',-92,-40,-56,0]]\n",
        "        res=(1,4)\n",
        "\n",
        "        self.assertEqual(find_min_distance(matrix),res)\n",
        "    \n",
        "    def test_agru_seq_sem(self):\n",
        "        matrix=[['-','seq1','seq2','seq3','seq4'],['seq1',0,-87,-34,-92],\n",
        "               ['seq2',-87,0,-1,-40],['seq3',-34,-1,0,-56],['seq4',-92,-40,-56,0]]\n",
        "        min_distante=(1,4)\n",
        "        res='seq1 & seq4'\n",
        "\n",
        "        self.assertEqual(agru_seq_sem(min_distante,matrix),res)\n",
        "    \n",
        "    def test_calc_novas_dis(self):\n",
        "        matrix=[['-','seq1','seq2','seq3','seq4'],['seq1',0,-87,-34,-92],\n",
        "               ['seq2',-87,0,-1,-40],['seq3',-34,-1,0,-56],['seq4',-92,-40,-56,0]]\n",
        "        min_distante=(1,4)\n",
        "        nome='seq1 & seq4'\n",
        "        res={'seq1 & seq4':{'seq2':-63.5,'seq3':-45}}\n",
        "\n",
        "        self.assertEqual(calc_novas_dis(matrix,min_distante,nome),res)\n",
        "    \n",
        "    def test_nova_matriz(self):\n",
        "        matrix=[['-','seq1','seq2','seq3','seq4'],['seq1',0,-87,-34,-92],\n",
        "               ['seq2',-87,0,-1,-40],['seq3',-34,-1,0,-56],['seq4',-92,-40,-56,0]]\n",
        "        min_distante=(1,4)\n",
        "        nome='seq1 & seq4'\n",
        "        res=[['-','seq2','seq3','seq1 & seq4'],['seq2',0,-1,-63.5],['seq3',-1,0,-45],['seq1 & seq4',-63.5,-45,0]]\n",
        "        \n",
        "        self.assertEqual(nova_matriz(matrix,min_distante,nome),res)\n",
        "    \n",
        "    def test_arvore(self):\n",
        "        res=['NP_003733.2 & Q9N0V3.1','B8K1W2.1 & NP_003733.2 & Q9N0V3.1','O70127.1 & B8K1W2.1 & NP_003733.2 & Q9N0V3.1',\n",
        "             'NP_00000 & O70127.1 & B8K1W2.1 & NP_003733.2 & Q9N0V3.1']\n",
        "        self.assertEqual(arvore('seqs'),res)\n",
        "        \n",
        "suite = unittest.TestLoader().loadTestsFromTestCase(TestFilo)\n",
        "unittest.TextTestRunner(verbosity=3).run(suite)"
      ]
    }
  ],
  "metadata": {
    "colab": {
      "provenance": []
    },
    "kernelspec": {
      "display_name": "Python 3",
      "name": "python3"
    },
    "language_info": {
      "codemirror_mode": {
        "name": "ipython",
        "version": 3
      },
      "file_extension": ".py",
      "mimetype": "text/x-python",
      "name": "python",
      "nbconvert_exporter": "python",
      "pygments_lexer": "ipython3",
      "version": "3.11.5"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 0
}