Creating a Distance Matrix

PhylogenyAlignment

Descrizione

Per due stringhe della stessa lunghezza, la p-distance è la loro distanza di Hamming (HAMM) divisa per la lunghezza della stringa — cioè la proporzione di posizioni in cui differiscono. Il problema chiede la matrice n×n delle p-distance tra ogni coppia di stringhe date.

Given

Una collezione di n (n ≤ 10) stringhe di DNA di uguale lunghezza (al massimo 1 kbp), in formato FASTA.

Return

La matrice D corrispondente alla p-distance dp calcolata su tutte le coppie delle stringhe date.

Sample Dataset

>Rosalind_9499
TTTCCATTTA
>Rosalind_0942
GATTCATTTC
>Rosalind_6568
TTTCCATTTT
>Rosalind_1833
GTTCCATTTA

Sample Output

0.00000 0.40000 0.10000 0.10000
0.40000 0.00000 0.40000 0.30000
0.10000 0.40000 0.00000 0.20000
0.10000 0.30000 0.20000 0.00000

La mia esecuzione

08/24/2026 11:24:47

Input · dataset.txt

>Rosalind_0603
CCTCAAGGGTCAGTGTTATCCACATATGTTGTGTTGTTAGACTCTGTCACGTACTGGTAG
TCTCGCCTCCCGGCGATCTATTCTCTGTCCAGTTGAGTCTACTCGTGTAATTGCTGGTTC
CACTAATGCATAGACACGGCTCTTTTTTATAAAACCGATTCCTATCCGTTCCGAAGTTCG
TTGGGTAATTGCATCAGTCACGGGGATCCTCGTTGGAAACCACGAAGTACCGAGAGGAGC
ACCGAAAGACCCAATCACCAAAGGGGTGGCAGTCCACTAAAACGGTCCTTACGAATTAGA
TGTGCCATCTAAGGATAAATGTCGTGAGTTCTTATCACGCCGTATTCCTGAGTTCTCTCG
CGTCCCCAGGATGCCATGTGCCAAGAGCCCCTATCAACACCCATAGATTGCTATAATCAT
TCTTTTTGTCTCACTAACCCGGGTATAAGAAACGAAATTCTCAGAAACTCGATTTGGTAG
ACCCTAGTACCTTTGCACCGAAAACTAAAGAAACATTTGTCTACGCTTCCGATTCTTCTT
GTACCTTGTGTCGGGGAATTCTGTCGCCGCTAGCAAAAATGATATTTTGGGTGAACTAGC
GGTCGGCTATTTATGGCTACCAAAGGGGTAGACTACAGATTCAAAAGCCTGCTATCGGAC
TAGCTGAATATCTGGCAGAAGTTTGTTCCCGCAGTTTTCGCTTCGCGAGCGAAGCTAATG
ACTCCTTAGTTGGTAGAGGGCTCTTATGAGAAGACAGGCCTCTCCAGGACCCCGATCAAG
GATAAATGCTCATAGAGGCTCCAGACCTCGGGCGACTTAGTGCTGTATGTCCATAAATTA
GCAGCTTATCGTGTGACTCACAGGGGGGCGTCATGATATACCTCATTTCTGTTTTCGCGA
ATTTGGTCGCTCATCCGATGTCAGCAGAGGTCTACAGTGAATTAACGTCAGTGAGTGACA
GT
>Rosalind_2076
CTGCATGAATAAGCGCTAGCCCTATATGATATATTCTTGAGTACAGTTATATGCTACAGG
TCTAGCGTTCCGGCGATTTATCGGTCACTCACTTCAATCTATCCGGGTGTATGTTGATTT
CACCCACAGAAAGAAGGGGTCCTCGTCCGCGAGACCGGCTCCTGACCACCGTGACGTCCG
CCAAGTAAATACGTCACCCGGTGGAACATTCATTAGGAGCCCCGGAGTACTATGAGAACC
ATTCAAGAATCGCTTCACCGGAACGGTAACGGCTCCGCATGACGGCGTGTGCTAACCAGA
GGCACCGTCGGGGGATACGTCCCGCGTGTTCTCATTACACTGCATCTTCGAGTTGTCCAA
AGTCGTCTTGGTCCCCCGGCTTGGAGAACACTCTTACTAGCTAGGGCCTACTCAGATTAG
ATCCCATACCTCACTAGCACGACGGTTGGTGGTAGAGTCCTCACAGATAGAGCGCGGTGA
ATGGTGATACATCCTCGGTAGAAGACACAGAGAAAGGTACTTATGCATTCAATCTTCATT
ATACTGCATGTCAAGGAACACCGTGAACCTTGGCCCATATGATATCGTGTATAGACCAGC
GATTTGCTACCTATCGCGACAACCGGCGGCAACAGTGGATTCGGAGGCTTGCTGATAGGC
GACTTGATTGCATGGTGGAACCTGGCACTTACAGCATCCGCCTCACTGTTGGAGGTGATG
GCCCCGCTTTAGAGAGGGAGCTCCAGTGGCGGAAGAGGCTTCCTTAGAATTTCTACCGAA
GCTTAATCCTCGCGAAGGCACTAAGATTCGCGTAGTCTGTGATTGCGTACTCATAATCCA
ATAGTTAAGCGCGCAGGGCGTAGGGAGGTGATAGCGAATATCTTGCATGTGACTTCGCAG
ATCGAATGCTTCGTTTGATGTAAGTAGAGATCTCCAAGGGACTGTTGTCAGCAAGCTGCA
AT
>Rosalind_7397
CCACACGAACCAGCGCTAGCCACGTATGATATATCCCTAGGCTCAGTCACGTGCTGCCGG
TCTAGCATCCCGGCGATCTATTTCATGTTCAGTTGAATCTACCCGTGTGTTTGTTAATTT
CACTCACGGATAAAGACGATCCTCGTTTATAAAACCAGCTCCTATCCACCGCGTGGTTCG
CTGGGTGAATGCATTAGTCCGCGGGATACTCATAAAGAGCCCCGAAGTATTATGAGAAGC
ATTCAAGGATCGAATCACCGGAGCGGCAGCGGCTCGCCGTGACGGCCTTCGCGAACTAGA
TGCACCGTCGAGGAGTACATACCGCGGGTTCTTATGATGCCGCATCTCCGAGTTCTCTAA
TGCCCTCCTGGTCCCGCGTGTTAAAAGCCACTATCACTACCCACAGCTTACTAGAGTGAG
ATTTCATGTCTCGCCAGTCCGATGGCAGGTAACAGAATTCTCAGAGGCAGGACTTAGTGG
ACGCTAGTACTTTTGCGCCGGAAGCTAGAGGAATAGTTACTTATGCATTCCATTTTTATT
ATACCCCATGTCAAGGAACTCCGTGGACTTTAGCACAAATGATATTTTGGATGAACTAGC
GACTGGTTGCTTATCGTTACCAAAGGGGTAAACAGCGGATTCGAAGGTCTGCTAGCGGAC
CACCTGATTGTTTGGCGGAGCTTGGCGCCTACAACATTCGTCTCACTGACGGAGCTGATG
GCCCCCCTTTGGGTAGAGGGTTCTCGTGGGGAAAGAGGCCTCCTTAGAACCTCTATCAAG
GCCAAATGCTCGTAAGGGCCCTAAAACTCGGGCGTTTTACCATTGCATGCCCATAGGTTA
ACAGTCAAGCGTGCAACGCGTAGGGAGGTGGCAGAGTACACCTCGCTTCTGTTTTCGCGA
ATTGGGTGGTTCGCTCGATGTGAGCAGAGATCTCCAGGGGATTATCATCAATGAGTTATA
AT
>Rosalind_4669
CTTTAAAGATCAGAGTCGTCTACACATGTTGTGTTACGAGTCTCCGCTACGTAACCGTGG
TTTGGCCTATCGACGGTTCATTCCCCGTCCGCCGGAGTCCACTCGTGCCATCGCCGATTC
CGTTAATCAACAGGCGCGGTTCCTTTCCATAAAACCGCTTCATATCCGTTCTGAAGTTTG
TTCAGCAATTGTATCAGTAACATAGACTCTCGCTCGAAACCACGAGGGACCGAGAGGAGC
ACCTAAAGACCCAAACACCAAGGGGTTCGGGGACCACAAGAACAGCCCTCCCAGACCAGG
TAGGCCATCTGACGTCCAATGGCGTAGGTTCTTGTCTTGACGTATTCCTTAGCTGCCTCC
CGCCCTCAGGTACTCACGAGTCCAGTGCCCCTTTCGACACCCATAGATTACTATAATCGT
CCCTTTGGTTTAATTAACACGGGAATAGGGGACAGAATCCTCAGAAGATTAGCTCGGTAC
ACTTTCGTGCCTTGGCGCTCGAGACTCAGGAAGCATTCGAACACACCCACAAATTCTCTC
GCTCCTTATGTTGTGAAACATAGTTCCCGTTAGCAAGAGTGATGTCTTGGGCGAGTGAGT
GGCCGGCTATTTATGGCCATCAAAGAGATAAACTACGGATTCAAAAGCCTGTTTTCGGAC
TAGCTGAACTTCCGGCAAACCCCTATTCTTGAAGTATTCATCCCCCGGGCAGATCTAATC
ACGCTTTAGTTGGCGGAGGTTTCTTATAGGAGCTTCGGCCTCTCCAAGGCCCCGGTAAAG
GACGAATGCTCATAGGAGTTTCAGACTTTAGACGACCTTGTGCGGTCTGGCCAAAAATTA
ATAGCTTATCATATGACTCAGTGGGGCGCTTGATGATATACTTTACTTCCGCCGTCGAGA
ACCAGATCGCAGCCCCGATGTCAGAGTAGGCCAGTAGTGAATCAGCGCCAGTGGGTGACA
GT
>Rosalind_8162
CCTTTTAAATCTGAGTTGGCTGCACGTATCAGGCTACGAGCCTCCGTTACGTGAACGCCG
ATCGGCTTATCGAATATCCATTCTCCGTCTGCCAGGTTTGCCTCGCCCCGTTGACAGTCC
CGTGACTTAGTGGATGCGGTTCGTTTCCATAAGACCGCTCCACATCTGATCTGGGGTTTA
TTCAGTCATTTTGTTGGTAGCTTGGACTATCGCTCAACGCCCTGAGGGATCGCAAAGAGC
ACCCATAGTTCCAAACGTCAGGGTATTCGGGTAGCTCCCGGACAAACTTCCGGGGCGAGC
TGGGGTGCAGGACGTCGCATGGCGTAGGTCCTCGTCTCGCCGTGTTCCTCAGTCGTCTCC
AGCCCCTGGGTACTCCTGATGCCGGTGCCCGCTTCGACACGCACCTGAAGCTATAATCGT
CCTCCTAGTTAAGTCAATACTGGCACAGGGGACAGAATCGTCAGTGGATCGACAAGGCAG
ATTATAGTGTCTTGGGGTCCCAGACTCTGGAAGCACTCGCACACACCCACAAATTCTCCC
GCTCCCCGTGCTATGGAACACAGTTTCCGTTAGCAAAAGCGGTGCCTTGGCCGAGTGAAG
GGCAAGTCACTAATCGTCACCAAGCAGCTAAACTTAGGATCCGGAGGTCTGCTTTTGAAC
TAATTGCACTTCCAGTGAGCACGTGTTCTTGAAGTAGTTTTCCTCGGGAGGGATATAGTT
ATGCTTTAATTAGCGGAGGTCTACTGTAGAAACCTGGGTCTCCTCAAGCCTCTGGAAAAA
TACGAATGCTCTTAGGGGTTTCGTACTGTAGACGACCTCGTGGGGATCGGCCCAAAATTA
ATAGTTTACCACATGGTCAATTAGGGTTCCTGATGGTATGCTTTCCTGCCACCGCCGAAC
AGCGGACTTTTGCCCCACAGTTACAATAGATCAATAATGACTTAGCACTAGCGAGTGGTA
GC
>Rosalind_6198
CTATGCCGGTCGACGCTACTCAGCGCCAGTTTTTCCCACCCTTTACGTACTTACGTTCGA
ACCAAGACCTTGATTATTTATTTTTTGATCAGCTGTATTTTCTCGAGTGACTGTCACCCT
TAGATCGCATAAAAGATAATCCCCATTTATAGAATCATCTGGCATCTTCCATTCAGCCCC
TTGTGTTAACGCATTAGTAAACGGGGTAACGTTGGGGGGCTTCGAAATTTCGTGTAGAAC
AATGAACAGCCGAACAATGAAGATGAAGACTTTTCGGCAACCCGGCTTACGCGGACTTGC
CCTACCATTGGGGATGGTCTGCTGTGAGTCCTTACGATGGCGCATTTTAGGGTTCTCCGG
AGCGCTCTTGGGCGTGAGTTACAATGGACATTGTTACTGTCCGAGGCCCATCAGAGAATA
ACTACATATCTTACAAGTTCGATGGGACCCGACAGCTGCTCTAGATTCGTATTCCAATGG
ACGCGTATACGAGTGCAATGGAGGGCTAGGGGACAGCTACGTTCGTATCCCGGTTTGTGT
ACACCCAGTGTCTAGAAATCCTGCGATGCCAAGTAGGGCGGAGATTTCGATTGGGTTAGC
GGCGATCCGCATGTCACTAATAACGGCGTAAAAGGCGTTTTGAGCAGACTCGTAGTGAGT
CGGTTAGCGAATTGATGAGGCTTCGCGCCTGACACATTCGTTTTACCGACGGAGAGTATG
GCAGGCCTTTCACTTGTGGACGCCTGCGGAGAAGGATGGTCTGTCGAGTACTCGACTGGA
GCTGTAAACTCGTAGGGACTTCCAAGCTCCGAGGTTCTAGCAACGCACGTCTGCGAGTTG
GCCGTCAAACTAGCCATTTGTCGAAAGATCGCTGAGGACGTTTGGTTTTGGTTGTCGCAC
CCCGGACCGGGCGCTCGAAAGACTTGGGCATCTACGGCTAGTTGTAATTGGTGAGCTACA
AT
>Rosalind_6049
CCATGCCGCTGAATTCACACCATTTGCAGTTTGTCCCCCCGTTCGCCTGGTAACATCAGG
GCTAGTATTTTGAATGTTTATCTCCTAGTCATCGAGATTTTCTAACGTACATGTTGTTTT
TACATAAGGGCAAAGACAGCCCTCAACTATAAAATCATCCAATACCCTCAACGCGGTCCA
TTGACTGCATGAACTAGTTGGCGGGATAGTTGTGGGCGGCTTCGAAGCCCTTCGCGGCGC
GATAATATGATTAGTGACGGAGATGGTGGCTTCTCAGTGTTCGAGCCTTCGCGTGCTTGC
CCCGCCGTCAGGGAACGTCCACCGCGCGTTCTTAAGAGGTCGTATTTAAAAATTCCCTGT
AACACTCTGAAGCTTGCATGCTGGAGAACACTGTGATTGCCTGGAGCTTAACGGAGACAG
GCCACATGTTCTGCTAGTCCACCGGCTGGCTATAAATCAATTTGGGACAAAACCTAATGC
AAGCCCCGACTTGTGTAGTGGGGGAACAGGGGACTGCTAGGTGTATAGCCTGATTCTTTT
ATACCGCGTACCCAAAAATTCTGTTGATTCTAAGATCACAACTATTTTAAGTGGGATAGC
GACGATCTGCCTATCACCAGTAACGGAGTAAAGAGCTATTTCAGCAGTCTGTTACCGGGA
GGGTAACCAAGCTAGTGAGGCTCCACGTTTACAACATCGGCCTCATTGACGGACCTCATA
GTTCACCCTTAGCCGGAGGAGTCATGTGAACAGAGAGAGCTTTGAGGGTGCGAGACCGGA
GTTAAACACCCATGGGGACTTCCAAACTCCGGGGCCCCAGCACCGAATATTCACGCACTG
AGAGTCGATTTAGTTATTTGTCGGTATGTCGATGAGAACCTTTCGCTTCTGTTGTCGTGC
TCCGCGTGACTCGCTCGAGATACTTGGGGGGCGCTGAGTGATCACGCTTACAGTGTCGCA
AT
>Rosalind_1320
CTATGCCGATCAACGCTAACCATCTACAATTTGTCCCTCCGTTCACCTACTTACTTCCGG
GCCAGTATCTTGATTGTTTATTTCTTGATCAGCTAAATCTTCTTGCGTACTTGTCACCCT
CACATAAGGACAAAGACAATCCTCATTTATAAAATCGTCTAATATCCTCCACGCGGCCCG
CTGAGTGAGTGCATTAGTAGGCGGGATAATTATGGGGAGCTCTGAAATTTCGTGCAGAAC
GATGAAAGGTTGAATTACGAAGACGGAGACTTCTCGGTGCGCCGGCTTTCGCGGACTTGC
CCTACCGTTAAGGAACGCCTGCCGCGAGTCTTTACGATGTCGCATCTCAGGGTTCCCTGG
AGCACTCCTGAGCTTGCATGCCAGAAGACACTGTTACTGTCCGGAGCTTATCAGAGGGTG
ACTACATATCTTGCCAGTTCGGTGGCATGCGACAAATTCCTTAGGGCCGTGACCCAATGG
ACGCGTTTACTTGTGCATTAGAGGACTGAGAGACAGCTATGTCTGCATCCCGATTCTTTT
ACACCCCATGTCCAGAAATTCTGTTATCTCTAGTGTGATGGATATTTTGAATGAGCTGAC
GACGGTTTGCCTATTGCTAGTAACGGAGTGAAAAGCGGGTTCAGCAGTCCATTAGCGAAG
CGGTTAGCGAACTGGTGAGGCTCCGCGTCTACAACATTAGTCTTACTGACGGACAGTATG
GTCTGTCTTTGGCTAGAGGACTCTTGTGGAGAAAGAGGATTTTTCAGGTGCTCGACCGGA
GTTGAACACTCGTAAGGACCTTCAAGCTCCGAGGCTCTAGCATCGCACATTCACGGGCTG
GCAGTCAATCTAGCAACTTGTCGGGAGGTCGCTGAGAACGTCTCGCTTTTGTTGTCACGC
TCTGGGTGGTTCGCTCGATATACTTGGGGATCTCCGGGTGGTTATAATTAGGGGGCCACA
AT
>Rosalind_5630
CTTTGAGGATCGGGATCGCCTACACTCGCGGTTCTACGAGTCTCCGCTGTGCAACTGTTG
TCTGGCCTACCGCTGACTCACACTTTCTCCGCTGGAACCCACCCATGCAACGGCCAGTTG
CGTTAATCACCAATAACAGTCCTCTCCTCGACTACCGTCGCATACTTGTTCTGAAGCGTG
TTTAGCAATTGTAACGATAACAGAGACTCTCGCTCGAAACAATGAGGGGCTGACAAGAGC
ACCTAACGACCCAAATACCAAGGGGACTGGAGAGCACAAGTACAGACATCTCGGGCAGAG
TAGGCGCTCTGTTATCCAGCGGCGTAGGCTCCAGCCTCAAGGTGTTCCTTAGCTGCCCCC
CAACGCTAAGTATCCACAAGTCCGGTGCCCCCTTTTACACCCATAGGTCATTATTATTGA
TATTCCGGTCAAATTAACACGGGAATAGGGGACAGGGTCTTCGGAAGATTGATATGGTAC
AATCTCGTGCCTTGGCACTTCAAACTCAAGGAACGTTCGCACACCCCCACAAGCTCTTCC
CATCTCTATGTCATGAAGCACGTATCTCATCACCACACGCGGTATCCGGGACAAGTGATT
GGTCGGCTATTTATGGTCATCAAGGAGATGGCCTACGGAATGAAAGGGCCATTTTCGGGC
TAGTCGATCATCCGCCAAACTCTTGCTTGCGGAGTATTCATCCTCCGAACGGACCTAGCC
GCGCTTAATTTGGAAGTAGTTCCTTACATGTGCTTTGTCGGACTCAGGGCCCAAGTAAAG
GGCGAGGGGCAATAGAAGCTTCAGACTTTAGACGACATTGCCCGATCTGGCTTGATTTTA
ATAGGGTATCATATGGCCCAGTGGTTAGCTAGATCACATACCTTGCCTTCGCAATCAAAG
ACCAAGTCGCAGCTCCGATGTCGAGGTAGACCAGCGGCAGGTTACCATGAGTAAAGGATA
AC

Output · run_log.txt

0.00000 0.49480 0.32328 0.30457 0.48960 0.57380 0.56653 0.50416 0.46466
0.49480 0.00000 0.31497 0.58212 0.63721 0.57380 0.55925 0.49168 0.64033
0.32328 0.31497 0.00000 0.48337 0.55301 0.47713 0.48129 0.34927 0.57484
0.30457 0.58212 0.48337 0.00000 0.31913 0.64137 0.61435 0.58420 0.30977
0.48960 0.63721 0.55301 0.31913 0.00000 0.66112 0.66840 0.62994 0.46985
0.57380 0.57380 0.47713 0.64137 0.66112 0.00000 0.44179 0.27755 0.67672
0.56653 0.55925 0.48129 0.61435 0.66840 0.44179 0.00000 0.31081 0.68503
0.50416 0.49168 0.34927 0.58420 0.62994 0.27755 0.31081 0.00000 0.64449
0.46466 0.64033 0.57484 0.30977 0.46985 0.67672 0.68503 0.64449 0.00000

Esegui nel browser · Pyodide

Mostra il codice sorgente (problem.py)

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

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 p_distance(s1, s2):
    diff = sum(1 for a, b in zip(s1, s2) if a != b)
    return diff / len(s1)

def main():
    seqs = lettura("dataset.txt")
    n = len(seqs)
    for i in range(n):
        riga = [p_distance(seqs[i], seqs[j]) for j in range(n)]
        print(" ".join(f"{v:.5f}" for v in riga))

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

Soluzione JavaScript

Esegui ora, live

Mostra il codice sorgente

// Creating a Distance Matrix (Rosalind ID: PDST) - soluzione JavaScript
// indipendente, non una trascrizione di problem.py: stessa logica
// (parsing FASTA multi-record, poi matrice n x n delle p-distanze tra
// ogni coppia di sequenze, ciascuna formattata a 5 decimali), 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;
}

function pDistance(s1, s2) {
  let diff = 0;
  const n = Math.min(s1.length, s2.length);
  for (let i = 0; i < n; i++) {
    if (s1[i] !== s2[i]) diff++;
  }
  return diff / s1.length;
}

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

  if (seqs.length === 0) {
    throw new Error("Input non valido: nessun record FASTA trovato");
  }

  const n = seqs.length;
  const righeOutput = [];
  for (let i = 0; i < n; i++) {
    const riga = [];
    for (let j = 0; j < n; j++) {
      riga.push(pDistance(seqs[i], seqs[j]).toFixed(5));
    }
    righeOutput.push(riga.join(" "));
  }

  return righeOutput.join("\n") + "\n";
}