Catalan Numbers and RNA Secondary Structures

CombinatoricsString AlgorithmsDynamic Programming

Descrizione

Un matching è "noncrossing" se nessuno dei suoi archi si incrocia (assumendo i nodi disposti su un cerchio). Un matching noncrossing degli archi di base-pairing nel grafo di bonding di una stringa di RNA corrisponde a una struttura secondaria priva di "pseudoknot". Il numero di matching perfetti noncrossing nel grafo completo K_2n sono i numeri di Catalano, con ricorrenza c_n = somma su k di c_(k-1) × c_(n-k).

Given

Una stringa di RNA s con lo stesso numero di occorrenze di 'A' e 'U' e lo stesso numero di occorrenze di 'C' e 'G'. Lunghezza massima 300 bp.

Return

Il numero totale di matching perfetti noncrossing 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_8886
CAGCUUGCAAUUCGAAUAAUGAUCCCGUAGUUAAUGCAUAUAUGCUGGCGCCAGUAGUGC
ACUACCGCGGCCUUCGUGCAUUAAUAUAUAUGCGCAAUUAUAGAUUACCGCGAUCUAGAA
UAAAUCUUUAAAGCGCGUCGGUACGCAUUCGGCAGUAUAGCCGAGCGCUCGCCUAGGAGC
GCUUACAUCGAAUUUAUAUAGUAUAGGCCCCGCGGGAUCUAGAGGUACCAUAUUACGUGC
CACGUG

Output · run_log.txt

Esegui nel browser · Pyodide

Mostra il codice sorgente (problem.py)

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

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 memoize(f):
    memo = {}
    def helper(x):
        if x not in memo:            
            memo[x] = f(x)
        return memo[x]
    return helper
    
@memoize
def catalan(n):
    if n == 0 or n == 1:
       return 1
    else:
       result = 0
       for k in range(1, n+1):
           result = result + catalan(k-1) * catalan(n-k)
       return result

opp = {"U": "A", "A": "U", "C": "G", "G": "C"}

def validate_base_sequence(base_sequence, RNAflag=True):
    #Return True if the string base_sequence contains only upper- or lowercase T (or U, if RNAflag), C, A, and G characters, otherwise False
    seq = base_sequence.upper()
    return len(seq) == (seq.count('U' if RNAflag else 'T') + seq.count('C') + seq.count('A') + seq.count('G'))

def validate_gc(base_seq):
    #assert validate_base_sequence(base_seq), "argument has invalid characters: '" + base_seq + "'"
    #seq = base_seq.upper()
    return base_seq.count('C') == base_seq.count('G')

def validate_ua(base_seq):
    #assert validate_base_sequence(base_seq), "argument has invalid characters: '" + base_seq + "'"
    #seq = base_seq.upper()
    return base_seq.count('U') == base_seq.count('A')

class Rna:
    def __init__(self, s):
        self.s = s
        self.l = len(s)
    #def countC(self, c):
    #    return sum(1 for x in self.s if x == c)
    def valida(self):
        return validate_gc(self.s) and validate_ua(self.s)
    def get_chunks(self):
        chunks = []
        c = opp[self.s[-1]]
        i = 0
        j = self.s.find(c, i, self.l-1) 
        while j != -1:
          if j%2 == 0:
             chunks.append((self.s[0:j], self.s[j+1:self.l-1])) 
          j = self.s.find(c, j+1, self.l-1) 
        return chunks
def calcola_chunks(chunks):
    tot = 0
    for chunk in chunks:
        r0 = Rna(chunk[0])
        if r0.valida(): 
           r1 = Rna(chunk[1])
           if r1.valida(): 
              result0 = calcola(chunk[0])
              if result0 > 0:
                 result1 = calcola(chunk[1])
                 tot1 = result0 * result1
                 tot = (tot + tot1) % 1000000
    return tot    

@memoize
def calcola(s):
    if len(s) == 0:
       result = 1
    elif len(s) == 2:
       if opp[s[0]] == s[1]:
          result = 1
       else:
          result = 0
    else:
       chunks = Rna(s).get_chunks()
       result = calcola_chunks(chunks)
    return result % 1000000

def main():
    data = lettura("dataset.txt")
    s = data[0] 
    chunks = Rna(s).get_chunks()
    tot = calcola_chunks(chunks)
    print(tot)
    

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

Soluzione JavaScript

Esegui ora, live

Mostra il codice sorgente

// Catalan Numbers and RNA Secondary Structures (Rosalind ID: CAT) -
// soluzione JavaScript indipendente, non una trascrizione di
// problem.py: stessa logica (conta le strutture secondarie non-crossing
// con accoppiamento Watson-Crick rigoroso A-U/G-C, ricorsivamente,
// spezzando la sequenza in coppia con l'ultimo carattere e tutto ciò
// che sta "dentro"/"fuori" a quella coppia), riscritta in modo
// idiomatico per JS.
//
// Nota: problem.py definisce anche una funzione catalan() memoizzata,
// ma non viene mai chiamata da main() - è codice morto nell'originale,
// quindi non è stata portata qui.
//
// Nota implementativa: problem.py enumera le posizioni del carattere
// complementare tramite ripetute chiamate a str.find(); qui, con lo
// stesso risultato, uso una singola scansione lineare da 0 a l-2 (dato
// che find() veniva comunque usato solo per elencare TUTTE le posizioni
// in ordine crescente, non per una ricerca "furba").
//
// Contratto: riceve il contenuto testuale di dataset.txt, restituisce
// l'output testuale (stessa forma dell'output Python).
const MODULO = 1000000;
const OPP = { U: "A", A: "U", C: "G", G: "C" };

function validateGC(s) {
  let c = 0;
  let g = 0;
  for (const ch of s) {
    if (ch === "C") c++;
    else if (ch === "G") g++;
  }
  return c === g;
}

function validateUA(s) {
  let u = 0;
  let a = 0;
  for (const ch of s) {
    if (ch === "U") u++;
    else if (ch === "A") a++;
  }
  return u === a;
}

function valida(s) {
  return validateGC(s) && validateUA(s);
}

// Per la sequenza s, elenca tutte le coppie (chunk0, chunk1) candidate:
// per ogni posizione j pari (0-indexed) dove compare il complemento
// dell'ultimo carattere, chunk0 = s[0..j), chunk1 = s[j+1..l-1).
function getChunks(s) {
  const l = s.length;
  const c = OPP[s[l - 1]];
  const chunks = [];
  for (let j = 0; j < l - 1; j++) {
    if (s[j] === c && j % 2 === 0) {
      chunks.push([s.slice(0, j), s.slice(j + 1, l - 1)]);
    }
  }
  return chunks;
}

const memo = new Map();

function calcola(s) {
  if (memo.has(s)) return memo.get(s);

  let result;
  if (s.length === 0) {
    result = 1;
  } else if (s.length === 2) {
    result = OPP[s[0]] === s[1] ? 1 : 0;
  } else {
    result = calcolaChunks(getChunks(s));
  }
  result = result % MODULO;

  memo.set(s, result);
  return result;
}

function calcolaChunks(chunks) {
  let tot = 0;
  for (const [chunk0, chunk1] of chunks) {
    if (valida(chunk0)) {
      if (valida(chunk1)) {
        const result0 = calcola(chunk0);
        if (result0 > 0) {
          const result1 = calcola(chunk1);
          const tot1 = result0 * result1;
          tot = (tot + tot1) % MODULO;
        }
      }
    }
  }
  return tot;
}

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;
}

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

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

  const tot = calcolaChunks(getChunks(s));
  return `${tot}\n`;
}