From two sequences to a tree
The classical alignment-to-phylogeny stack, implemented from scratch: five programs that hand their output to the next.
dynamic programmingsequence alignmenthierarchical clusteringphylogenetic inferencePython
Pairwise global alignment
two sequences to one alignment
Dynamic programming over the full scoring matrix, with traceback.
Multiple sequence alignment
n sequences to an alignment block
Progressive extension of pairwise alignment to a set of sequences.
Supermatrix assembly
k alignments to one concatenated matrix
Joins per-gene alignments into a single matrix, tracking partitions.
Hierarchical clustering
a distance matrix to a clustering
Average-linkage clustering, merging the closest pair at each step.
Tree construction
a clustering to a tree
Builds and renders the tree implied by the clustering.
These are implementations, not libraries. Each one was written to understand the algorithm rather than to compete with an existing package, and each takes its input from the program above it.
Why build the whole chain
An alignment algorithm on its own is an exercise. The chain is the part worth showing: every stage makes an assumption that the next stage inherits, and those assumptions are only visible when the output of one program has to be the input of another.
What is not here
No substitution model beyond the scoring schemes each program defines, no bootstrap support on the trees, and no attempt at the performance of an optimised implementation.