Answers.Body: <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>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-07-31T12:03:51.580Z
Answers.Text: 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.
Answers.UserDisplayName: Paul
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-07-30T15:25:48.310Z
Answers.LastActivityDate: 2018-08-07T07:50:39.673Z
Answers.LastEditDate: 2018-08-07T07:50:39.673Z
Answers.UserDisplayName: Matt Bashton
Body: <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>
  
Tags: <blast><makeblastdb>
Title: The algorithm behind makeblastdb?
ThreadText: # 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.  
  
  ---
  
  