Finding a Shared Motif

String Algorithms

Descrizione

Una sottostringa comune di una collezione di stringhe è una sottostringa presente in ogni membro della collezione. Si cerca la sottostringa comune più lunga (longest common substring) tra tutte quelle presenti; la soluzione non è necessariamente unica.

Given

Una collezione di k (k ≤ 100) stringhe di DNA di lunghezza massima 1 kbp ciascuna, in formato FASTA.

Return

Una sottostringa comune più lunga della collezione (se esistono più soluzioni, se ne può restituire una qualsiasi).

Sample Dataset

>Rosalind_1
GATTACA
>Rosalind_2
TAGACCA
>Rosalind_3
ATACA

Sample Output

AC

La mia esecuzione

08/24/2026 11:24:47

Input · dataset.txt

>Rosalind_9024
TCCGATTCGGTACCCCCAGTGGGCTCTGGGTATATCCTACTGACATCCCCAATACGTTAT
ATGCTAATGTCTTACTTGTTTACCTTGGTTTTAGTAGCCGCCCACATCGAGGAAGGCAAG
GTCATCGATAATGCCTCTTCCCGGAAGCTGTCGTCCAAAAACTAAAATGTTGGGGTTTAC
GGGCGGAGATTATTTTGAACATCGTCGATAAATGGTACGATCTGCATGGGCCCGTTTCTT
ATTATGAAATAGTAGGACCTATAGGTCGGGCACCTTAACCTCCTTCCGTCCTGAACTTGC
GTATACCTTCCGGGTTAATGCATTCCGGCATTGGTTCCGAGGCTGACGTAACGTTTGGCA
GTTGGTGTTTGACTCAGTCATGATTGCTTCATTCGGTTCCAGACAAGGTATCGGCGGTAT
CGATTGCGTTCCTAGAGCTATTTTGCTTTACGCCAGAACCCGTGCGGATGTGTCTCCACG
TAACTATGCAGTAATTGATACACATAGCAGCGCTACAAATTTACCTTTCTGGTTGCCGGT
TGGTTTAGCGTCTGAGCTCACCAACTCCACGGCGACGAGACTCTTTGTGTACCTGCATGG
CATCTCAACCCCGATTCTACACTGTGAGGATTGCTCGACTTATAGCAAGTACGCTTCCTC
AGCTGATTGTAGAGCTCCCAGTTCGCCAAACGTCAATGCGAGCATTCTGAAGCAAAGCCC
GGACAAGAAGTCTGAGCCAAGACCTTCCCCGACCCTGCAGTTAACCAAGAATTTTATGTA
GGGTGGGCGGGAAGAGTACGAGCGTAAGCGGAGTCGAACTCGTCTGGATGGGACTCCTGC
GCGGGACCCAGACGGGCATTAAATCCCAGGATTTTCCCTATTTTTCTAGCCCTGCTGTCC
TGTGACCTCTGTGATCGGATGTGGACAGAGAGCCCCCAGCCTGAAACATAATCAAGTGGC
CTCAGAATTTTTTTCCATTTTTGGGATTAGTTCTCCAGTT
>Rosalind_6338
GAGAATCGGGGGATTATCTAAGGCAGACCTCCCCTCAGAGATAGGGGATGCAAATTGGAG
TAAGCAAATTCGCCTGGCAGCGCTGGAAGTTAATTTCCGAGAGTCGGAACTGGAGAACAC
CCCTACGACCGATCGAGCCGCTATCGAGGACAAAACACGCCCCCAGGTTTCCTCTGATAA
TCGGAATATATTCCCGTTCCTGCGCACTGCACTCTTCCAGTTCGTTGCACCCAAATTTAT
TCTTGGTGTCCGGCCCCGGCGCGTCGCTCAATGTAGTTTCAACTTTGGCTCTACCAGGAT
AGTATAAGTCCGAGGGAGCGTCAGGGAATCTAGCTTTTTCAGACGGTCGGGATCCTAACC
CTGTACATAGAGGAACAACGGCATTCCGGCATTTTCCAGATACATCTGTAACAGTGGTCA
TGTCGCAGTCTGTAGAGCTATTTTGCTTTACGCCAGAACCCGTGCGGATGTGTCTCCACG
TAACTATGCAGTAATTGATACACATAGCAGCGCTACAAATTTACCTTTCTGGTTGCCGGT
TGGTTTAGCGTCTGAGCTCACCACAGTCGCAGACGGGTCTCATTAGCTCTCCCAATACGA
GCCCACTGTCCATGCAGTCGAGCTTACCGCGGTAGATGTAGAGCAACCTGCATCAGGGAG
GAACCGACCGCACTTCTTCTAGTTCCTAGAACAGGGTCCCCATGATGAGACTCCGGTGTC
ACGCCGGCTCTGCGGTTGAGGACGTGCGGATACAACGGTGAAGCATGTGTTCGTAGAGTG
GGGGACGCATACTATTAAAGCAGTCAATATATGCGACGTGGTCCGAGACCGTTTGGGCTC
GTTTATCCGGTCGGACAGATAAGGGCAAATCGCGGGCGTCAAGTTGTTGGCTCGGAATTA
CTTATCTTCATAGCTTCAATGTAAAAACGAAGCTGGGCCCCGAATCCCCGAGAATAGAAC
GGCGTGTCATGGGACGCCTATGTCCCAACCGTTATGGAGG
>Rosalind_1938
GACAGCAGTAAGGAGTGTCAAACCACTTAGCCCAACTTTGCGTACTCCACGAGGCAGGGG
CTTATCAAGACGTCAAGTGAACGGAGTGAATCGACAGAGCTCTGACGTTTAATGACAACT
GGAACTACGTATATCATAATGTAACGCTGTCTCATCCAGTAGGAACCACCAATCCTATTC
CCGAAACGCGTGCGTTATATGCGTACCAATACCATCGCGCTCTCAATGTGAGCTTTGAAA
CGTTATACGGTATAGACATCAGAGAAGTTACTCGCGTACGATGTTCGGTACGTTCGTGCT
TGATACTGATAGAGTATACCGAATACTGTCCTTAGTCCGGATTATTTACGCGTGAACGCG
TAGCCGCACGCAACTCCTCAGAGCTATTTTGCTTTACGCCAGAACCCGTGCGGATGTGTC
TCCACGTAACTATGCAGTAATTGATACACATAGCAGCGCTACAAATTTACCTTTCTGGTT
GCCGGTTGGTTTAGCGTCTGAGCTCACCACACTATGCCGCACCTCCGAACACCCCAGGGA
TTTCTACTTCCCCCAGACACCGTAAGTACCCAGCTGCGGGGTCCCACTGACCGCTATCGC
GCCGTCTACAGTTTATTACAGCGGGAACGGGTTACCTACGGCAATCGCCTCTATTTCATC
ACTACCTCGCTAAACTGTCGCTGCGCACTATACCGCTAAGTATTCTGATGAACACGGACA
TCAAGTGTCCCGGAAGTGAATCCCAGTCTTAGCATTTATACGGCCATATTATTATCGTCC
AAGAAGAACGGCGCTCATAGCGCCAATGAATCGATGGTGCTGAGGACAAGACACCGTACT
CAACCATGTACCCGCGGGATAGGCCTCATGGCAGCCGGCTGGCGGGATATAGCCGCCGAT
ACCTCTAGATAACCTACAACCGGTCTAGCGCATGATTATTTGGGGCCTCAGTCTCAAGGA
AGAGAGGGCGGAAAGCTCGTGCGCTGGACCTGGTTAGCAC
>Rosalind_6991
CGTTTGGGTTCCCCGAAGACACACGGATTCCTTTTTGAGTAGGATCAGCTTTCGCGCTCT
GAGGATAGAACATACATACCGCCCTATATCCAGTAAAAGTGATCGCATATTGCATAACTC
GTAGTGGTGCAATTTACCAGGTGCGACACGAAACCTGAATACACTCTCGGTTATGTATCC
TTAAGGAGGGCACGTCATGTTCAAGAGGGCCCCTGAAACTATGACATGTCGGGTTGAGTA
ATAATGGATTGGAGGTGCACCAGAAATCGATTTAAATCCTTTCGGGGCTTGTGGCACGAG
TATGGACGAAATAATGCATGCAAAGAGATCGTACGTTACTTACTATAGTGAGAAGACGCA
CGGAAACCATGGGAGAGTTGACCACAGTGTACTAACTACTGAATACGCGCTGAGAAGAGC
TATTTTGCTTTACGCCAGAACCCGTGCGGATGTGTCTCCACGTAACTATGCAGTAATTGA
TACACATAGCAGCGCTACAAATTTACCTTTCTGGTTGCCGGTTGGTTTAGCGTCTGAGCT
CACCAAGACTTAATGATTTTTTAACGTTAAGGGATGAATGGGCTAGGTTGTCCAACTAGA
CATACCGCTCCGGTATGGAAATATTTGAGCGTATAAGCCGGCCTGCCGATTTTCATGCGG
CAGGCATTGGTGTACGCTTCCTCGTGTCCGTAGTGACTCACCGTATCGTGGAGCTATGCG
ACAATTTTACGGCTAAAAAGGACCTGCACGGATTGATAGCCATGATCGTGAAGGCAGAAT
GGATAAAATGCTTAGACCTAGTCATGCGATTCAGATCTAACTGAGAACTTACATTTGATC
CGGTAAAGTTGTCCGGGCTACGGGCCTGGTTCGATACAGTGTGCGTATGGTTATATTTCC
GTCGAAGCTTCCCCTGGTAGATTATCGAAAAACGCCGGGCAAGACTTATGGCGGTGTTAG
TCGGCTGATAAGCCCGGGTACCATTAACTTTTCGGCATGT
>Rosalind_3366
GTAGGTCACGGGCGTAGGACGGAATGAGTATGAGCTTGCTACGGCTGATCGGACGTGATA
GCACCCTGGAGTAGACTGATTGCAGACAGCGTTGAAGCACTTGGAATGCCGCCTCTAGGG
GGTTGTGGAGATCTATTGAAGTCCGGGTTGATTAGAACGCCCAAGCTGTCTGCGGTGACC
GCCTGTTGAAATCGCCTATTGGCACCTATGTAGGTTTGAAAGAAGTACCTCGTGGCTATC
TCAACTGCTCGCGTACACTGCTTTGCCCCCGTCGCACACTGATTCCCAGCGTCAACTTTA
AGGCGTCTCGAGCCACTTTAGAAGCGTTGGGCGCCTGGCCTCAGACCGCGCTGGCGAAAG
GGGCCAACGTGTCGAGTGAGAGACTTCGAGCACTCAGTCCAGACCTTCCTATCGGCTGGT
CACTAGTGACTAATCAAACTGAGCAAGGAGGGTTTACAATCACATAAGAAGTCATTGGGG
TGGATACGCTAGAATGAGCGCGGATAGGAGGTTACTTGCCAATGAAGACCTGAGTACCGC
ACAGAACGTAGAGTTAAGATAGCGTGCATTTATGTACTCAAAAACTAGCCGTTCTTGTCA
TCAAGAAAAAATAAAATCGCCTATTATTTGGGACGCGGACCAGCGTCCGAGATCGTCACC
TAGGCGGGACCGTTTAAGAGCTATTTTGCTTTACGCCAGAACCCGTGCGGATGTGTCTCC
ACGTAACTATGCAGTAATTGATACACATAGCAGCGCTACAAATTTACCTTTCTGGTTGCC
GGTTGGTTTAGCGTCTGAGCTCACCAGTGCATTGACTTGAACATGTGCCCGCCTCGTAAC
CGGCGCCGTCAGTATGTCCTGACCAGGGCGCTGGCGCCCACTGTTGTGGGTCGGCTCGAC
TGTAGAAACTTTTGAATTGGGGGATGGCCAACATCACGCCGCTGTGGAATGACAGGTTAC
ACGTGGTCGTAATGGTGCAAGATTTTGTCAACTTCTTCCA
>Rosalind_6291
CTCTATCGTAACTCGGAACGCACTCTTGTTTAAGCCTGCCCTGTCACGCATGCAGCCTGG
TGACGGCCGCCGGATAATTCTCTTCCACGCCGTGTTGTATTGAGTCGATTCAGGCCTTCT
GAAAGTTCGGACCAATGCTAAGGAGAGATGTGTAGACTTTCGCAACAAGACGACAATGTA
ACAGCGGAGGTATTTTTAGTCAGGCACAGATGGCAGCGACGTGTAAGTAGACTCACTTGC
ATATTAGTATCATGTACAAATTAAGTTCCACAATTACTCACGGGCTTGGTCAAAAGAACA
CACTCGTCACGTTTGCAGGCAATCTTTTCGAAATGAGACATGTTACCTAAACTCTGGCAA
GTGTACTGTACGTCCAATTGACAATCACGCGCCGATGAGCCCCGCTTTTCGCCCGGCCGC
ACTCCTCTTGTGCGCTAAGGTCTACTGCAACTTAGATGCTTACGTTGGCAGAGCTATTTT
GCTTTACGCCAGAACCCGTGCGGATGTGTCTCCACGTAACTATGCAGTAATTGATACACA
TAGCAGCGCTACAAATTTACCTTTCTGGTTGCCGGTTGGTTTAGCGTCTGAGCTCACCAA
TAAATTACGTGAGGCTCCGGACGCTGCATAAGTTAGGTCAGCACGCAATCGCCGAAACAT
TATCCGAAACTATCGCCGCCAAAACTGACTTCCGTTCGATATTTTGTTAGAGGGACCAGG
TAGCCACGTAGAGTTAACCTAAATGTGAATGTGCCATGGGCGGTCTTCTACCAATTGCAA
TTCAAGTAGGTTAGATTCACGGGAAAATTATGAGACATCTTCCCATATGCGGGCGTTCCT
CTAATCCAGGGAGCGAGACACCATCGTGGCATACACCCGGCCTAATACGTTTCCCGTTCG
TGCGGTGTTCCATAATAAACGATTTGCAAAGTCCTAGTGAAGGGTCGCAGTACTTCATAC
TGAGTCCATCTCGAGCTCGCTCTCGGACTACCTTACACCC
>Rosalind_7610
TTATTCGATACTGCGAACGGCAAGGGGCGGTCGTCGCGCGCCCGCCCACAACTGTGTCGT
CCTCTGAAGAGCTATTTTGCTTTACGCCAGAACCCGTGCGGATGTGTCTCCACGTAACTA
TGCAGTAATTGATACACATAGCAGCGCTACAAATTTACCTTTCTGGTTGCCGGTTGGTTT
AGCGTCTGAGCTCACCAAATAAGCTTTCCGATAAACCCTTAAACAGGATATTTTCTGCCC
GGCCCATGGCAACGTAGATAAATTGGACGTTTCGACATTGATCAGCACCAGCACGGACAC
GGTACAGTTCCAAAGTGCAGTATCACACAAGATACGTTGACGGATTGTGCCGTTTCTCTA
GCCTGTATTCTGCCCTCGGTAGCAATCGGGCCCAACTTAAAACCCTTTTTCAAGATCTTG
TTAGGCTTGCCACTTCAGTACTATAACTGACGCTATCTCCCAGCTGTACTTAGGGTGAGA
GTAAGTAACAGCGGCGAGGGATTTGTGGCAGCGATTAGAGCGGACAAACCTAATACTCTT
GCTGGCGCTTAAATGAGAACACCAAAGCAGGTACACTGCGCTGAACGAAGCGTTAGCTCG
ACCGGCCAGCCTAGACTGAAGGGGGTGAAAGCGAACCGGTTAATTGTTAACGGGTACTAT
GATTCTCGATAAAGCCCAGTAGCAGTAGAGAATTGGTCGTGTCATTCGCTGATGTATCGT
CTCCATCTACGAGGTGTCCCCGGTTGGATAATAGTGGTCTTCGCAGGGGATGGTGCCCGA
TACTTAATGAAATGGGTTGGAGGATCGACTCCTATTACGTTATGTGCGGGGGAAAACCGA
CGCTGAAGTCGTCTAGAACCTGTCCCCTGGAAATAGATATTACGATTCTCCCGTAAAGCT
CCGTCCAATGCTGAATAATTAGATGGTTCCTATGACCTGTTAGTTCGCCACGGGCGTTTA
GACCAACAAGGTTATGATCACGAGCTCTACAGATGTGGCT
>Rosalind_3500
GAATAACTATAGACGCGTAACCACGCACTACAAATCCGCTCCACGCGAGAAGTAAATAGA
CGACCTTTCGTCCACATGGGAGAGTACTGAGACGAAGATTTTATGATATGATGTTACCGC
CGAGTTGTACTAACAAGATAACACCCTCAGGCGCTGATGGCTCTATACTCCCTACTACCA
TCGTGCAGAGGAGTTCAGACGATTGTTCAACGGCCCAGCCGAACGAGTCGTTGATAACCT
CAGGTCATCATCAAGTCTAGCTGGACTTTGGCCCCGAATGTTACTCAGGTAAAATAGCTT
CTCTTCCTGTCATTCTACCAACCTCGAGTCTAGATACCACGGGCTGATAGAAGTTTTAGT
GCCTCGCTCAATGTCGTTTGGAACCGGATCGAAGCTGTCTCTACTTTTCATCTTTCGCTA
AACAAACGCTTTTAATCGGAGAAGGAAGTCGAGCCTCGGTGGTTAGGGGCTCTCCACCGA
CATAGCCCTACTATAGTAGCAACGCAGCCGTTACCCACATAAACGTAAATAACAAATAAC
ATGAATACCGTTACTAATAACGGCACGGGCCTATTCTGACTAACCCCCGCGGAGTAATGA
GTGCGTCGCTCGCCAGTGGTGATCACCTCCATGACTGTACAAGCCGGGCAAAACGAAGAC
GTGATAGGGGAAAGTGGAGAAGTAAGCTCGCTAAGGGGAGGTCACCTAACTCCCGCACAA
CCGGAGTAACCAGCGGGGACCGCCGCTATCGTTCGTGCTTAAGACGGCACGCACGCGCGG
ATTTTCGACGAAGTGTCATAGGGGAAAAGGTGTGTCGGGTCGCACTAGAGCTATTTTGCT
TTACGCCAGAACCCGTGCGGATGTGTCTCCACGTAACTATGCAGTAATTGATACACATAG
CAGCGCTACAAATTTACCTTTCTGGTTGCCGGTTGGTTTAGCGTCTGAGCTCACCAGAAC
CGCCTGAACCCATAAAAGCCGAATGCTCTGTGATTTTAGC
>Rosalind_9160
CAAACGGGAAGGGAGGGTGCTGAGGGCACGCAGTAGCCCGGGCGAAACCGCAGTCTCGAG
GCCAATGAGGCTGGCACGGGCGGAGCGGTAGATTCTCAATTATTGGACTACTTGTCGGCA
GGATGGACCAGAGGCTACACTCCGAAGCGGAAAATGAGCGACGGTGTCGGAGGTAAAAGG
TTTCATTAGACCACTCCCCGGGAAATACCTGACCCGCCGAACGGACACTTTGTTAAGATA
ACAACACACGCATTAAGATAGGGGTTGATAAGGGTTCAATTATTCTACTGACCGGTACTC
CGGTGCGGTCCATTAGCCTGTTCGGATAACAGTTTGAGTTAGGTGGGGGCGCTGATGTTG
TCAGACGTATGAAACGGACCACTAACGAAACCAACGTGGCGTGGCTTTCATCGAGTTCGT
TATCAGAGCGTCGGGGTTCTATATCTCTCCACTAGTGGGCCTCAAGAGAGCTATTTTGCT
TTACGCCAGAACCCGTGCGGATGTGTCTCCACGTAACTATGCAGTAATTGATACACATAG
CAGCGCTACAAATTTACCTTTCTGGTTGCCGGTTGGTTTAGCGTCTGAGCTCACCATTCG
GTTGACTTGTTTGACAATCTATAGCTCGTTTATAGTGCGCAGTGAAAATTCTACCCAAGT
CACATCTCTCCATCCTGAGTTCTTTCTCCAGTATCAACAGGCAGTGCGGGCCCGATGTAC
TCTTCACGATTGTATCGCGGTAGGCGGAGTGTACGAGTCTACGACAGGACCCTGATGCAG
GGCTTCTCACTTTCTTTCTACTCAGTTATTAGTCCTGGTGTTTAGCGACCGAAGGAATTA
AGATTTGAAGGATGACGCACTCCTGCTCTTCTGGTACGTCCGCGTACCCCACCTCGGTAG
CTGCGTATGGTCCGGCAACGTATCTCGGTCGCACAAAGTTAGCGAGACCGGAACTAGAAC
GTGCGGAGCATTTGTAGTACGAAGGACCCAAATACACCGG
>Rosalind_5984
GTAGCCAAGCTAGCTAGGTAATTAAGACACTTCCTCGGGTCGTGTTTAGTCTGGCTTCCA
ATCCGGTATCTTTCAGATCTACAGAACCATGTGTGACATAACTCCGAGAATTCCGACGGT
GGGACACATCGGCTGTCACAAATCTAATTATCTAGCCCAGCTGCTCGCACTTATATTAAG
GAACCATGTAGGTCCATCGGCGCCATACCGGTCCCCCAATATCCATAGGCTTATATCTGC
ACATCCTCCCCTCGGCTGTTATTGAGGCGTCTATAACTCCCGGACAATTCCTAGCCAGTC
TTAGTTTAGCCGCACGCTATAGCCGACCACCTGTAGCCACCGTGCCAGGGCTCTTCTTGA
ATTGACTCGCCCCCCTAAAGGCGTAACTAGACTGTAATGTATGGTCGCCCTTTGGTCTCT
ATTACGTGTGTCAGTGAGTGAAGTGTAAGTACTCTATCGGCTTATATGGCCAAAGGCCTA
TCATAGAATTCGTCGCTGCGAGCTCCTTGGAGACGTGAACAAACTATAAACGTATGCGGG
CCATGGCGCCTTTCCAAAGGCTCTGTGTGAGACGTCTGCGACATGAACCCAAACGACTTG
GTTGGAAGAACTACGTGAACAGAGACGCAGTAGTATAAACCGGAAGTTTAGTCAAGAGAA
TGCCTAATATTGATGCGAACCCACCGGCCATTCCGAGCTACTTTTACAACGCCTTGCAGG
GTAAGAAAAAGGGAATGGACTACTGTGGGCATAAGCGATAAACACTGCATGACAGCATTC
GCTCGGCATGGTGGCCATTTTAGTGGACCTAGTGCGGTCAGTTCCGCAAGTCTTCGCCCG
ACGGATCTTGTGTAACTAATAGAGCTATTTTGCTTTACGCCAGAACCCGTGCGGATGTGT
CTCCACGTAACTATGCAGTAATTGATACACATAGCAGCGCTACAAATTTACCTTTCTGGT
TGCCGGTTGGTTTAGCGTCTGAGCTCACCAAGACACCTCC
>Rosalind_6145
ACGCGTGATGCCAAACGATCGATGACATCAAGCCCGTGCGCGAATCTTTTTCACATACAA
TGACGTAACTAGTTGAATCCCCTCCCGCGCGACGTCTACGTCGCAGGAATGACTGTCTAT
GTTTGTGCATCACCTTTTGCAGAAGTATATCCTCGTGTCCCACCGATGGTCGATTACACT
TCAACCACATTTCAAAATTACGCTTAAGTAAGCCACAATACTATGCGCAAAGGAAGATCG
TCGGTGCAATAGCCGTACCCCGAATAAATTGGGTTATATTTAGCCACCACCTCTCTATCC
AGAGCTATTTTGCTTTACGCCAGAACCCGTGCGGATGTGTCTCCACGTAACTATGCAGTA
ATTGATACACATAGCAGCGCTACAAATTTACCTTTCTGGTTGCCGGTTGGTTTAGCGTCT
GAGCTCACCAGCATCAGCATGCACATCCCTGCCCCTATATCCACACGCCAAACCTGGGTA
GGACACACTTACTTTCCACTATAGAAGGACCAGCAGCTCCGAAGCTGTTTATCATACACA
GAATTCTCAAATCTCTTTCCGACTGAACCTGAAGGGATCCGGAAGATGTCCATAGGCAAC
TTTAGAGCGTCGTACGAGGCCTGATAAATGCCCAAGATTGACGGACCAGAATTCATCTAC
CATTGCAGCTAGTCTGTAAGGGTCTCTCCTTCAATCTAGCTTACACGGGGACCGCGTACC
GCTTTTAGAAGGAGAGCAAAAAACCTGCGCCGCCAAGGGCTGTACGTGGCCTCGACGATT
ACCACGATTTTGGCGGGAGTAATAGATAGTCATAAGCGTATGCTACTCTGCGAGGTAGAG
CATTGGATCGCTTGACACCATTCCAAAAAACCTCACGGTGTGCTCCTATAGCAGCTAGAA
CGTCAAATTAAACGGACATAGCACTTGAAATTCGTGATAAGTACAAGGGACTCGCAATAG
GGCCACCACAAATAATATTCAATTGCATCGCTCCGTGTGT
>Rosalind_5035
AAGAAGGTCCAAAAATTAAAACTCATCCAAGCCGTTGTTTACGCTAATCATGTGCTACCT
CGGTTTCTGTCATCTTGAGGCAGGGTCATCGCACCGAAGGGTTCAATACCCAGTCTCGTC
TAAGCGGTGCCAGGGAACGTTTCCGTAGACCTACTTTAGAAGTACGCGCGGGCCAAGTTC
AGCAGTAGAAGGAGAATGACTCACTGCAGAATCTCTTCGGGCCCAGTGTCTACCGACTCT
AACCGCCTGTCTTTTAGACCGGTTCGCACTTTCAGTACATTTCAACTTAGGAGCAGGTGT
GTGACCCCTGGCACAGTGGCTCCAACGTCAATTTACCCCTGCAGTACTACCGACCGGGCA
TGTATGCTCTCGAATAGGTGTGAATGGGTCCTGGAATTGCCTTTTAAGAGCTTTAACATT
CGGGACTAACAGGATCCGAGTACCTGATGCGGACACCGTCAGTAGGAGAGAGCTGTTTAG
ACAAACCCGCAACGAAATGCCTGAAGACTTTCTCCCGTCTGAGTAGTTAAATTTCTCAAT
CGTACGCAAGACGATTCCTGTCTTAATTCATAGTATTAGACATAGCAAATGAGGACCCAG
ATAGACTAGAGTGTAGCCGTTTT

… troncato (103.200 caratteri totali)

Output · run_log.txt

AGAGCTATTTTGCTTTACGCCAGAACCCGTGCGGATGTGTCTCCACGTAACTATGCAGTAATTGATACACATAGCAGCGCTACAAATTTACCTTTCTGGTTGCCGGTTGGTTTAGCGTCTGAGCTCACCA

Esegui nel browser · Pyodide

Mostra il codice sorgente (problem.py)

def lettura(filename):
    arr = []    
    with open(filename) as f:
        a, b = "", ""
        for riga in f: 
            if riga[0] == ">":
               if b != "":
                  arr.append([a, b])
                  b = ""
               a = riga[1:-1]
            else:
               if b == "": 
                  b = riga.rstrip("\n") 
               else:
                  b += riga.rstrip("\n") 
        arr.append([a, b])       
    return arr

def valid(s, records):
    result = True
    for record in records:
        if record[1].find(s) == -1:
           result = False
           break
    return result

def purge(stack, records):
    stack1 = []
    for s in stack:
        if valid(s, records): 
           stack1.append(s)  
    return stack1

def iteration(stack, records):
    stack1 = purge(stack, records)
    if len(stack1) == 0:
       print(stack[0][0:-1])
       return
    stack2 = []
    length = len(stack1) 
    for i in range(length):
        for l in ["A","C","G","T"]:
            stack2.append(stack1[i]+l)
    return stack2
   
def main():
    records = lettura("dataset.txt")
    #for record in records:
    #	   print(record[1])
    
    stack0 = [""]
    while True:
        stack1 = iteration(stack0, records)
        if stack1 is None:
           break
        stack0 = stack1
            
if __name__ == "__main__":
    # execute only if run as a script
    main()

Soluzione JavaScript

Esegui ora, live

Mostra il codice sorgente

// Finding a Shared Motif (Rosalind ID: LCSM) - soluzione JavaScript
// indipendente, non una trascrizione di problem.py: stesso algoritmo
// (ricerca in ampiezza: parte dalla stringa vuota, ad ogni round tiene
// solo le stringhe correnti che sono effettivamente sottostringa di
// TUTTI i record, poi le estende di 1 carattere in tutti i 4 modi
// possibili; si ferma al primo round in cui nessuna estensione
// sopravvive, e la risposta è la prima estensione di quel round privata
// dell'ultimo carattere), riscritta in modo idiomatico per JS.
//
// ATTENZIONE - stesso limite computazionale dell'originale: l'insieme
// dei candidati cresce come 4^L (L = lunghezza del motivo condiviso più
// lungo), quindi su dataset dove il motivo comune è lungo questo
// approccio può diventare molto lento o esaurire la memoria - non è un
// bug della conversione, è una caratteristica (poco efficiente) fedele
// dell'algoritmo originale.
//
// 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 bodies = [];
  let corpo = "";
  let first = true;
  for (const riga of righe) {
    if (riga.startsWith(">")) {
      if (!first) bodies.push(corpo);
      corpo = "";
      first = false;
    } else {
      corpo += riga;
    }
  }
  bodies.push(corpo);
  return bodies;
}

function valid(s, bodies) {
  return bodies.every((body) => body.includes(s));
}

function purge(stack, bodies) {
  return stack.filter((s) => valid(s, bodies));
}

export default function solve(datasetText) {
  const bodies = parseFasta(datasetText);

  if (bodies.length === 0 || bodies.some((b) => !b)) {
    throw new Error("Input non valido: attesi almeno due record FASTA non vuoti");
  }

  let stack = [""];
  while (true) {
    const stack1 = purge(stack, bodies);
    if (stack1.length === 0) {
      return `${stack[0].slice(0, -1)}\n`;
    }
    const stack2 = [];
    for (const s of stack1) {
      for (const l of ["A", "C", "G", "T"]) {
        stack2.push(s + l);
      }
    }
    stack = stack2;
  }
}