Last time I was active in DB, I created a script to get phylogenetic trees from saved sims (
see this thread). Eric, I believe you should reuse my algorithm, it needs in the average case only O(m*n log(n)) direct comparisons of mutations.
Basically, each node in the phylogenetic tree corresponds to a genome. The node stores the mutation history from its parent to itself and the number of living bots having the corresponding genome. To add a new bot, you compare recursively its mutation history with that of the nodes, starting from the root. When there's a full match with a node, you try to match the bot with the node's children. If there is no match (or no children), you create a new child. In the case where there's only a partial match (I'm not sure it can happen in your setting), you need to create a new node for the common ancestor of the bot and the node being matched. When a bot dies, you decrement the counter and prune nodes if it falls to zero.