How to compare/cluster millions of strings?
The length of each string is at least 200, and you only consider two strings similar if their edit distance is less than 20.  So if $S,T$ are similar, then there must exist $U$ such that (1) $U$ is a substring of $S$, (2) $U$ is a substring of $T$, and (3) the length of $U$ is at least 10.

This suggests that one heuristic is to find all length-10 substrings and look for collisions.  In other words, build a hashmap whose keys are substrings and values are the containing strings; for each string $S$, compute all length-10 substrings $U$, and add a mapping from key $U$ to string $S$ into a hashmap.  This can be done in linear time; a rolling hash may improve efficiency.

Now iterate through the hashmap and find all pairs of strings $S,T$ that share a common length-10 substring.  For each pair $S,T$, compute the edit distance and check whether the edit distance is &lt; 20.  I suggest using the optimized edit distance computation with "early out": if the edit distance is $\ge 20$ you don't care what its actual value is.  This computation can be done in $O(20 \cdot (n+m)) = O(n+m)$ time per pair, where $m,n$ are the lengths of $S,T$.  Length 10 is large enough that probably won't be too many pairs $S,T$ that contain a common length-10 substring but whose edit distance is $\ge 20$, so you probably won't waste too much time computing the edit distance on pairs you aren't interested in.

There are other approaches, based on metric trees, BK trees, and other methods.  See, e.g., Efficient map data structure supporting approximate lookup.  You might also look into the computational biology literature, which deals with a similar problem when clustering DNA sequences.  There the alphabet has 4 characters, rather than 5 characters, and strings can be much longer, but they also want to find similar pairs from a large database, and they have developed practical and efficient algorithms.