Pairwise p-Distance Matrix

Advanced Bioinformatics Distance Matrix Phylogenetics FASTA Formatting
Significance:

Almost every phylogenetic method begins by converting a set of aligned sequences into
a matrix of pairwise distances. The p-distance — the fraction of positions at which two sequences
differ — is the simplest such measure, and while more sophisticated models correct it for multiple
substitutions, every one of them starts here. Producing a correctly formatted symmetric distance matrix
is the required input format for tools like neighbor in PHYLIP and FastTree.

Statement

You are given several DNA sequences of equal length in multi-FASTA format.

For every ordered pair of sequences, compute the p-distance: the number of positions at which they
differ, divided by the sequence length.

Print an n x n matrix where entry (i, j) is the p-distance between the i-th and j-th sequences
in input order. Format every value to exactly five decimal places, separate values on a row with
single spaces, and print one row per line.

Input — read from standard input
Variable Type Description
fasta
line 1..n
 str Multi-FASTA input, all sequences of equal length
2 <= records <= 20, 1 <= sequence length <= 1000

These variables are already read for you in the starter code on the right.

Output

str n rows of n space-separated p-distances, each formatted to five decimal places

Sample Cases
Sample 1
Input
>a
TTTCCATTTA
>b
GATTCATTTC
>c
TTTCCATTTT
>d
GTTCCATTTA
Expected 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
Four ten-base sequences produce a symmetric four-by-four matrix with a zero diagonal.
Sample 2
Input
>x
ACGT
>y
ACGT
Expected Output
0.00000 0.00000
0.00000 0.00000
Two identical sequences, so every distance is zero.

Submit also runs your code against 3 hidden test cases. Hidden inputs are never shown — if one fails you'll get its number and a description of the mismatch, not the data.

Constraints
  • 2 <= number of sequences <= 20
  • All sequences have identical length
  • Sequence lines may be wrapped across multiple lines
  • The diagonal is always 0.00000 and the matrix is symmetric
Further Reading
  • Reuse your multi-FASTA parser — this problem assumes you already have one.
  • sum(1 for a, b in zip(x, y) if a != b) counts mismatches in one expression.
  • Format with f"{d:.5f}" so 0 prints as 0.00000 rather than 0.0.
My Notes
Log in to save personal notes.
Console output will appear here when you click Run Code or Submit...
Expected: fasta — the whole input (Multi-FASTA input, all sequences of equal length)
Next Problem
Mendelian Inheritance Probability