Motzkin Numbers and RNA Secondary Structures

CombinatoricsString AlgorithmsDynamic Programming

Descrizione

Estensione di "Catalan Numbers and RNA Secondary Structures" (CAT): qui, invece di richiedere un matching perfetto (ogni nucleotide accoppiato), si contano tutti i possibili matching noncrossing (anche parziali, incluso il matching vuoto) degli archi di base-pairing nel grafo di bonding di una stringa di RNA. Questi numeri sono i numeri di Motzkin. La ricorrenza: per una stringa s di lunghezza n, si considera il primo simbolo, che può non essere accoppiato (contributo M(s[1:])), oppure accoppiato con il simbolo in posizione k se sono complementari (contributo M(s[1:k]) × M(s[k+1:]) per ogni k valido), sommando tutti i contributi.

Given

Una stringa di RNA s di lunghezza massima 300 bp.

Return

Il numero totale di matching noncrossing (non necessariamente perfetti) degli archi di base-pairing nel grafo di bonding di s, modulo 1.000.000.

Sample Dataset

>Rosalind_57
AUAU

Sample Output

La mia esecuzione

08/24/2026 11:24:47

Input · dataset.txt

>Rosalind_3681
UUAGUCGGUAACUUGGCAUCACAGACAACGUUGGAGGGAUCGGAAGCGGGAGAAGUUACG
UCACCGGUCGGGGUUGCUUCCUUCACACGUAUGGUGGACACAGAUUUCACAUAUGCUAGG
CAGGUAUCCAUUUAUUAGACACCUUACACGGCCCUGCUAUAUUGAGUCUGUGCGGCGGUG
CUGUCGGGCUCUCUCUCCUUCUUUCGUACGCGUACGGGGACAAAGAGGGCAGAGGUUGGA
GGGCAUGUUUUUUCCAGCGAG

Output · run_log.txt

Esegui nel browser · Pyodide

Mostra il codice sorgente (problem.py)

#http://rosalind.info/problems/motz/

import sys

MODULO = 1000000
COMPLEMENTI = {"A": "U", "U": "A", "C": "G", "G": "C"}

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

def conta_matching(s, memo):
    n = len(s)
    if n in (0, 1):
        return 1
    if s in memo:
        return memo[s]
    totale = conta_matching(s[1:], memo)
    for k in range(1, n):
        if COMPLEMENTI.get(s[0]) == s[k]:
            totale += conta_matching(s[1:k], memo) * conta_matching(s[k + 1:], memo)
            totale %= MODULO
    memo[s] = totale
    return totale

def main():
    sys.setrecursionlimit(10000)
    s = lettura("dataset.txt")
    memo = {}
    print(conta_matching(s, memo))

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

Soluzione JavaScript

Esegui ora, live

Mostra il codice sorgente

// Motzkin Numbers and RNA Secondary Structures (Rosalind ID: MOTZ) -
// soluzione JavaScript indipendente, non una trascrizione di
// problem.py: stessa logica (ricorsione con memoizzazione sul numero di
// possibili strutture secondarie non-crossing, mod 1.000.000),
// riscritta in modo idiomatico per JS.
//
// Contratto: riceve il contenuto testuale di dataset.txt, restituisce
// l'output testuale (stessa forma dell'output Python).
const MODULO = 1000000;
const COMPLEMENTI = { A: "U", U: "A", C: "G", G: "C" };

function primaSequenzaFasta(testo) {
  const righe = testo.split("\n").map((r) => r.replace(/\r$/, ""));
  let record = "";
  let first = true;
  for (const riga of righe) {
    if (riga.startsWith(">")) {
      if (!first) return record;
      first = false;
    } else {
      record += riga;
    }
  }
  return record;
}

function contaMatching(s, memo) {
  const n = s.length;
  if (n === 0 || n === 1) return 1;
  if (memo.has(s)) return memo.get(s);

  let totale = contaMatching(s.slice(1), memo);
  for (let k = 1; k < n; k++) {
    if (COMPLEMENTI[s[0]] === s[k]) {
      totale += contaMatching(s.slice(1, k), memo) * contaMatching(s.slice(k + 1), memo);
      totale %= MODULO;
    }
  }
  memo.set(s, totale);
  return totale;
}

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

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

  const memo = new Map();
  return `${contaMatching(s, memo)}\n`;
}