Recent posts

Position-specific score matrices

7 minute read

Global and local alignment tools like BLAST are typically used to search for and align homologous sequences which are related by common descent. However we m...

Burrows–Wheeler transform

15 minute read

Hash tables are a very good general solution for providing quick access to values (e.g. k-mer positions) based on keys (e.g. k-mers). There is an even more e...

Arrays and addressing

1 minute read

To access elements in an array or matrix, programming languages typically implement one of two addressing schemes. One of the schemes uses one-based numberin...

Indexed MegaBLAST, BLAT, and SSAHA

3 minute read

BLAST and FASTA are based on building an index from the query sequences, and scanning the database sequences for k-mers which are present in the query index....

BLAST and FASTA

6 minute read

Pure Smith–Waterman is unpopular because of its poor scaling. Given two sequences of unequal lengths n and m, we have to compute nm intermediate values. We t...