Perfect Matchings and RNA Secondary Structures

CombinatoricsString AlgorithmsDynamic Programming

Descrizione

In una stringa di RNA, adenina si accoppia con uracile e citosina con guanina. Un "matching perfetto" nel grafo di bonding (dove ogni simbolo è un nodo) rappresenta una possibile struttura secondaria dell'RNA in cui ogni nucleotide è accoppiato. Se K_n è il grafo completo su 2n nodi, il numero di matching perfetti p_n soddisfa la ricorrenza p_n = (2n-1) × p_(n-1), con soluzione chiusa p_n = (2n-1)(2n-3)...(3)(1).

Given

Una stringa di RNA di lunghezza massima 80 bp, con lo stesso numero di occorrenze di 'A' e 'U' e lo stesso numero di occorrenze di 'C' e 'G'.

Return

Il numero totale di possibili matching perfetti degli archi di base-pairing nel grafo di bonding della stringa.

Sample Dataset

>Rosalind_23
AGCUAGUCAU

Sample Output

La mia esecuzione

08/24/2026 11:24:47

Input · dataset.txt

>Rosalind_3209
GCUGCGCGGCAAUCGAGUUAAAGAUUUCUACAAGACUUGUACGUCCCGUUCGAUAGCUUU
CGGCAAGACA

Output · run_log.txt

2277243837099849063333888000000

Esegui nel browser · Pyodide

Mostra il codice sorgente (problem.py)

def lettura(filename):
    data = []
    with open(filename) as f:
        record = ""
        first = True
        for riga in f:
               riga = riga.rstrip("\n")
               if riga[0] == ">":
                  if not first:
                     data.append(record)
                  record = ""
                  first = False
               else:
                  record += riga
    data.append(record)
    return data
    
def fact(x):
    if x == 1:
        return 1
    else:
        return x * fact(x-1)

def main():
    data = lettura("dataset.txt")
    s = data[0] 
    numA = 0
    numU = 0
    numC = 0
    numG = 0

    for l in s:
        if l == 'A':  
         numA += 1
        elif l == 'U':  
         numU += 1 
        elif l == 'C':  
         numC += 1 
        elif l == 'G':  
         numG += 1 

    print(fact(numA) * fact(numC))

if __name__ == "__main__":
    # execute only if run as a script
    main()

Soluzione JavaScript

Esegui ora, live

Mostra il codice sorgente

// Perfect Matchings and RNA Secondary Structures (Rosalind ID: PMCH) -
// soluzione JavaScript indipendente, non una trascrizione di
// problem.py: stessa logica (il numero di perfect matching è
// numA! * numC!, dato che ogni A deve accoppiarsi con una U e ogni C
// con una G), riscritta in modo idiomatico per JS.
//
// Due correzioni rispetto all'originale:
// 1. fact(0): problem.py definisce fact(x) con caso base solo x==1,
//    quindi fact(0) andrebbe in ricorsione infinita (bug latente, mai
//    innescato sui dataset reali perché un matching perfetto richiede
//    numA==numU e numC==numG entrambi positivi, ma comunque non lo
//    riproduco: qui fact(0) = 1, matematicamente corretto).
// 2. BigInt: con sequenze fino a qualche centinaio di basi, numA! può
//    superare abbondantemente Number.MAX_SAFE_INTEGER.
//
// Contratto: riceve il contenuto testuale di dataset.txt, restituisce
// l'output testuale (stessa forma dell'output Python).
function parseFasta(testo) {
  const righe = testo.split("\n").map((r) => r.replace(/\r$/, ""));
  const data = [];
  let record = "";
  let first = true;
  for (const riga of righe) {
    if (riga.startsWith(">")) {
      if (!first) data.push(record);
      record = "";
      first = false;
    } else {
      record += riga;
    }
  }
  data.push(record);
  return data;
}

function fact(n) {
  let tot = 1n;
  for (let i = 2n; i <= BigInt(n); i++) tot *= i;
  return tot;
}

export default function solve(datasetText) {
  const data = parseFasta(datasetText);
  const s = data[0] ?? "";

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

  let numA = 0;
  let numC = 0;
  for (const l of s) {
    if (l === "A") numA++;
    else if (l === "C") numC++;
  }

  return `${fact(numA) * fact(numC)}\n`;
}