Finding a Spliced Motif

String Algorithms

Descrizione

Una sottosequenza (a differenza di una sottostringa) non richiede che i simboli siano contigui: basta che compaiano nello stesso ordine, anche con altri simboli intermezzati. Il problema chiede di trovare una collezione di posizioni in s tali che i simboli di t vi compaiano come sottosequenza.

Given

Due stringhe di DNA s e t (ciascuna di lunghezza massima 1 kbp), in formato FASTA.

Return

Una collezione di indici (1-based) di s in cui i simboli di t compaiono come sottosequenza di s. Se esistono più soluzioni, se ne può restituire una qualsiasi.

Sample Dataset

>Rosalind_14
ACGTACGTGACG
>Rosalind_18
GTA

Sample Output

3 4 5

La mia esecuzione

08/24/2026 11:24:47

Input · dataset.txt

>Rosalind_9517
TGGTTGCCCCACTGAAATAAAACATAAGGTTTACATAATCTAGGCAAATTGTGCACGACC
TGCACACTACGCATGGTTCGTTGTTTACAGCACGACACTAGCTGAACGTCCAACACTCCC
GTGTCTCCACCAGAGCCTCCCTGGTAGGTATGGGAGCTCCTCCGACCTTACGTAAGACAG
TCAAATGGACTAGGTAGGAAGGCCTGTAGCAAGTGCGGAAGCGTCATTCATCTCGTTCCA
GTTTCCCCCACCCTAATGGCAAAGTTCAAACTCTTGAATATGCCGTCGCACACGCCCCGT
TGGGTGATACTGTGAGTGGTGTAACTACACGTCAGTATATTCCAAGTGGACCACTCAACT
TAATTGATAAGACTGCCCGGGAGCGCAGGCATCGACAAGGGGGCTTGTTTGATGCTAAAC
CCGACAATGCCCGCGAATGCGCGGTGCGCCAGAGCTCTCCATCCGCTCACGGTATGGAAT
GGGATTTTATCAAGAAGATAAATTTGTGGCAGGGTAAGTTCATCCCCGCGTCCCCACGGT
CCTCTGTGCCAGCCGGGGGATATGGTAACCATCGGAGGAAATTAGGTAAATGCCGAAATT
CGTCACACCATAACTTGTAGACTTATACGGACAGAGCCCTACGTTGAGTCACAATCTTTA
GCCGCTACGTTCTCGAGCATTGTCACAGTACGAAGCGAATACCTGGATTTTTCTCTTGCT
AGTACATTAACTACTGAATATCACCACGGGCTGCGAATGGGGCGCTGACAACCACAAGCG
TTCAAAATTCAGCGAGTCTAGTTGCGGTGATGGCCAAGGTCACCACCTATAAGAGCCTCG
ATTGGACTGTCTGGCAACTATTTCGTAAGCATTTGAAACAGGGACTGTCGTGTAAGCGGA
CGAGGGAAACATAACCAGATACGCACGTTCGGACCCAGGGTACCGTGCTCGCTATTTCAA
AGATGGGTCCACAC
>Rosalind_4688
ATTCGTTCCGCTTCAAGACTGTTATTTCATG

Output · run_log.txt

11 13 18 23 28 30 31 34 40 43 45 49 50 54 55 58 62 64 65 68 71 74 77 87 99 103 109 110 112 117 121

Esegui nel browser · Pyodide

Mostra il codice sorgente (problem.py)

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

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 main():
    seqs = lettura("dataset.txt")
    s, t = seqs[0], seqs[1]
    posizioni = []
    j = 0
    for i in range(len(s)):
        if j < len(t) and s[i] == t[j]:
            posizioni.append(i + 1)
            j += 1
    print(" ".join(str(p) for p in posizioni))

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

Soluzione JavaScript

Esegui ora, live

Mostra il codice sorgente

// Finding a Spliced Motif (Rosalind ID: SSEQ) - soluzione JavaScript
// indipendente, non una trascrizione di problem.py: stessa logica
// (parsing FASTA multi-record, poi ricerca greedy delle posizioni in s
// dove t compare come sottosequenza), riscritta in modo idiomatico per
// JS.
//
// 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;
}

export default function solve(datasetText) {
  const seqs = parseFasta(datasetText);
  const [s, t] = seqs;

  if (!s || !t) {
    throw new Error("Input non valido: attesi almeno due record FASTA");
  }

  const posizioni = [];
  let j = 0;
  for (let i = 0; i < s.length && j < t.length; i++) {
    if (s[i] === t[j]) {
      posizioni.push(i + 1);
      j++;
    }
  }

  return `${posizioni.join(" ")}\n`;
}