Matching Random Motifs

Probability

Descrizione

Estensione di "Introduction to Random Strings" (PROB): data una stringa s e un GC-content x, si calcola prima la probabilità p_s che una singola stringa casuale costruita con GC-content x corrisponda esattamente a s (usando la stessa formula di PROB: probabilità x/2 per ciascun simbolo C/G, (1-x)/2 per ciascun simbolo A/T). Poi, generando N stringhe casuali indipendenti, la probabilità che almeno una di esse corrisponda a s è 1 - (1 - p_s)^N (complementare della probabilità che nessuna corrisponda).

Given

Un intero positivo N ≤ 100.000, un numero x tra 0 e 1, e una stringa di DNA s di lunghezza massima 10 bp.

Return

La probabilità che, costruendo N stringhe di DNA casuali della stessa lunghezza di s con GC-content x, almeno una di esse sia uguale a s (le stringhe casuali possono ripetersi).

Sample Dataset

90000 0.6
ATAGCCGA

Sample Output

0.689

La mia esecuzione

08/24/2026 11:24:47

Input · dataset.txt

98752 0.558945
GTTCGGATG

Output · run_log.txt

0.3284673261776563

Esegui nel browser · Pyodide

Mostra il codice sorgente (problem.py)

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

def lettura(filename):
    with open(filename) as f:
        n, x = f.readline().split()
        s = f.readline().strip()
    return int(n), float(x), s

def main():
    n, x, s = lettura("dataset.txt")
    gc = s.count("G") + s.count("C")
    at = s.count("A") + s.count("T")
    p_s = ((x / 2) ** gc) * (((1 - x) / 2) ** at)
    print(1 - (1 - p_s) ** n)

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

Soluzione JavaScript

Esegui ora, live

Mostra il codice sorgente

// Matching Random Motifs (Rosalind ID: RSTR) - soluzione JavaScript
// indipendente, non una trascrizione di problem.py: stessa formula
// (probabilità che almeno una di n stringhe casuali di GC-content x
// coincida con la stringa data s), riscritta in modo idiomatico per JS.
//
// Nota sulla formattazione del numero: sia Python (repr/print di un
// float) sia JS (Number.prototype.toString) usano un algoritmo "shortest
// round-trip", quindi per la maggior parte dei valori il testo prodotto
// coincide cifra per cifra. L'unico caso limite è la notazione
// esponenziale per numeri molto piccoli/grandi, dove i due linguaggi
// formattano l'esponente in modo leggermente diverso (es. "1e-07" in
// Python contro "1e-7" in JS) - improbabile con i vincoli tipici di
// questo problema, ma da tenere a mente in caso di dataset estremi.
//
// Contratto: riceve il contenuto testuale di dataset.txt, restituisce
// l'output testuale (stessa forma dell'output Python).
export default function solve(datasetText) {
  const righe = datasetText.split("\n");
  const prima = (righe[0] ?? "").trim().split(/\s+/);
  const s = (righe[1] ?? "").trim();

  if (prima.length !== 2 || !s) {
    throw new Error("Input non valido: attese due righe, \"n x\" e una stringa di DNA");
  }

  const n = Number(prima[0]);
  const x = Number(prima[1]);

  let gc = 0;
  let at = 0;
  for (const c of s) {
    if (c === "G" || c === "C") gc++;
    else if (c === "A" || c === "T") at++;
  }

  const p_s = (x / 2) ** gc * ((1 - x) / 2) ** at;
  const risultato = 1 - (1 - p_s) ** n;

  return `${risultato}\n`;
}