<p>From looking at this publication <a href="https://www.ncbi.nlm.nih.gov/pmc/articles/PMC2696921/" rel="nofollow noreferrer">"Database indexing for production MegaBLAST searches"</a> 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 <code>makembindex</code> 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 <code>makembindex</code> but only <code>makeblastdb</code> which I assume has superseded the older command: <a href="https://www.ncbi.nlm.nih.gov/IEB/ToolBox/CPP_DOC/doxyhtml/dir_30f669065d6b13796daf8e29b61b0d9a.html" rel="nofollow noreferrer">blastdb Directory Reference</a></p>

<p>Ulimtately the true details of the index generation lie in the C++ source code for <code>makeblastdb</code> can be found <a href="https://www.ncbi.nlm.nih.gov/IEB/ToolBox/CPP_DOC/doxyhtml/makeblastdb_8cpp_source.html" rel="nofollow noreferrer">here</a>.  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 <code>.cpp</code> file:</p>

<p><a href="https://www.ncbi.nlm.nih.gov/IEB/ToolBox/CPP_DOC/doxyhtml/blast_2seqdb__reader_2seqdb_8hpp_source.html" rel="nofollow noreferrer"><code>seqdb.hpp</code></a></p>

<p><a href="https://www.ncbi.nlm.nih.gov/IEB/ToolBox/CPP_DOC/doxyhtml/blast_2seqdb__writer_2build__db_8hpp_source.html" rel="nofollow noreferrer"><code>build_db.hpp</code></a></p>

<p><a href="https://www.ncbi.nlm.nih.gov/IEB/ToolBox/CPP_DOC/doxyhtml/blast_2seqdb__reader_2seqdbcommon_8hpp_source.html" rel="nofollow noreferrer"><code>seqdbcommon.hpp</code></a></p>

<p><a href="https://www.ncbi.nlm.nih.gov/IEB/ToolBox/CPP_DOC/doxyhtml/blast_2seqdb__writer_2writedb_8hpp_source.html" rel="nofollow noreferrer"><code>writedb.hpp</code></a></p>

<p>It would appear from <code>seqdb.hpp</code> that:</p>

<p>The index files have extension <code>.pin</code> or <code>.nin</code> and sequence files <code>.psq</code> or <code>.nsq</code>, </p>

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

CC BY-SA 4.0
2018-07-31T12:03:51.580Z
Thank you, i will read this! After a quick look, this datastructure is more or less a kmere list to position (hash/table), see 2.1.
Paul
CC BY-SA 4.0
2018-07-30T15:25:48.310Z
2018-08-07T07:50:39.673Z
2018-08-07T07:50:39.673Z
Matt Bashton
<blockquote>
  <p>What is the algorithm/concept behind‚<code>makeblastdb</code>?</p>
</blockquote>

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

<blockquote>
  <p>What is exactly stored in these files?</p>
</blockquote>

<p>Seems like <code>.phr</code> and <code>.pin</code> are storing some metadata (based on the size) and <code>.psq</code> 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)</p>

<p>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?</p>

<blast><makeblastdb>
The algorithm behind makeblastdb?
# The algorithm behind makeblastdb?

(Asked by: username_0 on 2018-07-30)

> 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?

**Tags:** blast, makeblastdb

---

## 1 answers

### Answer by username_1 on 2018-07-30. Score: 2 | Accepted answer

From looking at this publication ["Database indexing for production MegaBLAST searches"](https://www.ncbi.nlm.nih.gov/pmc/articles/PMC2696921/) 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](https://www.ncbi.nlm.nih.gov/IEB/ToolBox/CPP_DOC/doxyhtml/dir_30f669065d6b13796daf8e29b61b0d9a.html)

Ulimtately the true details of the index generation lie in the C++ source code for `makeblastdb` can be found [here](https://www.ncbi.nlm.nih.gov/IEB/ToolBox/CPP_DOC/doxyhtml/makeblastdb_8cpp_source.html). 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`](https://www.ncbi.nlm.nih.gov/IEB/ToolBox/CPP_DOC/doxyhtml/blast_2seqdb__reader_2seqdb_8hpp_source.html)

[`build_db.hpp`](https://www.ncbi.nlm.nih.gov/IEB/ToolBox/CPP_DOC/doxyhtml/blast_2seqdb__writer_2build__db_8hpp_source.html)

[`seqdbcommon.hpp`](https://www.ncbi.nlm.nih.gov/IEB/ToolBox/CPP_DOC/doxyhtml/blast_2seqdb__reader_2seqdbcommon_8hpp_source.html)

[`writedb.hpp`](https://www.ncbi.nlm.nih.gov/IEB/ToolBox/CPP_DOC/doxyhtml/blast_2seqdb__writer_2writedb_8hpp_source.html)

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!

> **Comments:**
> **username_0**: Thank you, i will read this! After a quick look, this datastructure is more or less a kmere list to position (hash/table), see 2.1.  

---

