The algorithm behind makeblastdb?

Question

What is the algorithm/concept behind‚makeblastdb?

I know makeblastdb produces a .phr, .pin, and a .psq file, that represents an index or a data structure that is better optimised for searching a given query.

What is exactly stored in these files?

Seems like .phr and .pin are storing some metadata (based on the size) and .psq the actual index. It can't be the table of all k-mers since the command doesn't take a value of k? (or maybe it is fixed to 3)

I could not find any direct discussion of the algorithm since google is flooded with people asking how to build such a database... Maybe someone can give me a link or hint?

Answer 1

From looking at this publication "Database indexing for production MegaBLAST searches" which although deals with MegaBLAST and it's indexing method, it would appear that this was rolled into the NCBI C++ toolkit as the command makembindex so I'm inclined to think the current implementation must have been derived from this strategy. Looking at the relevant part of the current NCBI C++ toolkit I find no reference to makembindex but only makeblastdb which I assume has superseded the older command: blastdb Directory Reference

Ulimtately the true details of the index generation lie in the C++ source code for makeblastdb can be found here. However following on from that I think the further details of the index generation may be in one of the following files which are includes for the main .cpp file:

seqdb.hpp

build_db.hpp

seqdbcommon.hpp

writedb.hpp

It would appear from seqdb.hpp that:

The index files have extension .pin or .nin and sequence files .psq or .nsq,

However it's not at all clear how the current implementation differs to the 2007 reference or where the .phr file is generated from! Some degree of reverse engineering the C++ source code will be needed!