Locating Restriction Sites

String Algorithms

Descrizione

Una stringa di DNA è un "reverse palindrome" se è uguale al proprio reverse complement (es. GCATGC). Questi siti sono bersagli tipici degli enzimi di restrizione batterici.

Given

Una stringa di DNA di lunghezza massima 1 kbp, in formato FASTA.

Return

La posizione e la lunghezza di ogni reverse palindrome nella stringa avente lunghezza tra 4 e 12. Le coppie possono essere restituite in qualsiasi ordine.

Sample Dataset

>Rosalind_24
TCAATGCATGCGGGTCTATATGCAT

Sample Output

La mia esecuzione

08/24/2026 11:24:47

Input · dataset.txt

>Rosalind_5245
ATATAATGGGGTTTTAGGAGACCGATCATTTGCAATAGTCCGCGGGGTTTCTTGACGCTG
GCTATATATAGTGAATCGTAGGACGTGCCATCAGGATAGGGCGGAGATTCTGTACAGGAG
CAAAACTCATGAATCGGTAGGAATAGGAGAGCAGCGGCAGAGAGTAGGCATCCGGAGCGT
CAAGTGATGAAATACAATAGAAAGCGATCCAACTTACCCGCGTTAAGGCGGGGCGTACAT
GCGAGATCGATAAGTTTGAGGCTCGACGGATTGGATACACAGTGGACAATACTATGCTTG
GCGACCGCCCAGCGCGGTCTAGCTAGTTGATTTGGCCCTTGAACCGACCTGTGCTAGGTG
TGATCTACCAGGGCTCATCGACGTTGAAACGACTAGGGTGTGACCTATTAATAGGTTGAT
ATGGTGCCTTTATCTGGGGAGTATACCAAGCGTGGGAGAGATAATACGCTGCGATATTCC
TTAACGTTACATAGCAAGTTTCTGACGACGGTTACAGGGCATGTTAGGTTCAAGTATGGG
CCAACGACCACGCACCTAAGCCTTACATTCGTTCGTCTCCCCCTTGCAGATTGCCATGGC
GGTTGGAAAAAGTCTGAGTACCATGAGCACCCGACTATAGGTACTGAGGCCTCCAGGCTC
CACACTTTTCCCACGCGTTGCTGAACTGTTTCTTACTACCTTAAGGTAAACGTAGTACTC
CGTGATCGCGGACCTGGACAGGTTGGGTCCAAAATGCCACCCTACTACAGCACAGTCTCC
GTGTGGTTTTAAGGGAACTTGGGTATGCCACTGAGCGC

Output · run_log.txt

Esegui nel browser · Pyodide

Mostra il codice sorgente (problem.py)

def reverseDNA(dna):
    s = ""
    for i in range(len(dna)):
        key = dna[len(dna)-1-i]
        if key == 'G':
           key = 'C'
        elif key == 'C':
           key = 'G'
        elif key == 'T':
           key = 'A'
        elif key == 'A':
           key = 'T'
        s+=key
    return s

def lettura(filename):
    arr = []    
    with open(filename) as f:
        a = None
        b = ""
        for riga in f: 
            if riga[0] == ">":
               if b != "":
                  arr.append([a, b])
                  b = ""
               a = riga[1:-1]
            else:
               if b == "": 
                  b = riga.rstrip("\n") 
               else:
                  b += riga.rstrip("\n") 
        arr.append([a, b])       
    return arr[0][1]

def main():
    dna = lettura("dataset.txt")
    l1 = 4
    l2 = 12
    for i in range(len(dna)-l1+1):
        for j in range(l1, l2+1):
            x = dna[i:i+j] 
            if j > len(x):
                break
            y = reverseDNA(x)
            if x == y:
               print(i+1, j)	
             
if __name__ == "__main__":
    # execute only if run as a script
    main()

Soluzione JavaScript

Esegui ora, live

Mostra il codice sorgente

// Locating Restriction Sites (Rosalind ID: REVP) - soluzione JavaScript
// indipendente, non una trascrizione di problem.py: stessa logica
// (parsing FASTA, poi ricerca di tutte le sottostringhe di lunghezza
// 4..12 che sono palindromi inversi, cioè uguali al proprio complemento
// inverso), riscritta in modo idiomatico per JS.
//
// Contratto: riceve il contenuto testuale di dataset.txt, restituisce
// l'output testuale (stessa forma dell'output Python).
const COMPLEMENT = { A: "T", T: "A", C: "G", G: "C" };

function reverseComplement(dna) {
  let s = "";
  for (let i = dna.length - 1; i >= 0; i--) {
    s += COMPLEMENT[dna[i]] ?? dna[i];
  }
  return s;
}

// Estrae la sequenza del primo record FASTA (unico dataset atteso qui).
function primaSequenzaFasta(testo) {
  const righe = testo.split("\n").map((r) => r.replace(/\r$/, ""));
  let sequenza = "";
  let trovatoHeader = false;
  for (const riga of righe) {
    if (riga.startsWith(">")) {
      if (trovatoHeader) break; // secondo record: fermati, ci serve solo il primo
      trovatoHeader = true;
    } else if (trovatoHeader) {
      sequenza += riga;
    }
  }
  return sequenza;
}

export default function solve(datasetText) {
  const dna = primaSequenzaFasta(datasetText);

  if (!dna) {
    throw new Error("Input non valido: nessuna sequenza FASTA trovata");
  }

  const l1 = 4;
  const l2 = 12;
  const righeOutput = [];

  for (let i = 0; i <= dna.length - l1; i++) {
    for (let j = l1; j <= l2; j++) {
      const x = dna.slice(i, i + j);
      if (j > x.length) break;
      const y = reverseComplement(x);
      if (x === y) {
        righeOutput.push(`${i + 1} ${j}`);
      }
    }
  }

  return righeOutput.join("\n") + "\n";
}