What Exactly Does Formatdb Do?

Question

[Griffan]

As far as I know, the blast searches for homology in the way that indexing query(word list), scan database(automaton), extension and so on. Then why should we pre-process the database with formatdb.

I know there is another way that firstly indexing k-mer or word in database, and then looking for occurrences in database for each query like blat did and lastz did. And I was told by articles that is why blat is faster than blast, the former is O(1), and the latter is O(G) for time complexity given the database of size G when determining each query's location.

If you can show me a link or give a brief list, that'll be helpful.Thanks.

[Neilfws]

You might ask "what does makeblastdb do?" since formatdb has been superseded by it.

Answer 1

[Hamish]

The place to start would be the NCBI C++ Toolkit:

• http://www.ncbi.nlm.nih.gov/toolkit
• http://www.ncbi.nlm.nih.gov/IEB/ToolBox/CPP_DOC/
• ftp://ftp.ncbi.nlm.nih.gov/toolbox/ncbi_tools++/

Which includes developer documentation and source code for various NCBI tools, including NCBI BLAST+. This includes details of the internal data structures used in BLAST and details of the BLAST database formats.

For the legacy NCBI BLAST, the equivalent information can be found in the NCBI Software Development Toolkit:

• http://www.ncbi.nlm.nih.gov/IEB/ToolBox/MainPage/index.html
• ftp://ftp.ncbi.nlm.nih.gov/toolbox/ncbi_tools/

Information about the NCBI BLAST database format can also be found in various other places, for example:

• http://selab.janelia.org/people/farrarm/blastdbfmtv4/blastdbfmt.html

And in third-party programs which read BLAST databases, for example:

• FASTA: http://fasta.bioch.virginia.edu
• EMBOSS: http://emboss.open-bio.org/

Note that other implementations of BLAST use alternative formats for their databases, for example WU-BLAST/AB-BLAST uses the XDF format.