Answers.Body: <p>Turns out that I was dumb: I misread.</p>
  <p>The Clustal Omega paper (in the supplementary materials) chose <span class="math-container">$t = \log N$</span>, which I think originates from this claim from this part of the Linial et al. paper:</p>
  <blockquote>
  <p>In random polynomial time <span class="math-container">$X$</span> may be embedded in <span class="math-container">$l_{2}^{O(\log n)}$</span> with distortion <span class="math-container">$\leq(1+\epsilon) \cdot c_{2}(X)$</span> (for any <span class="math-container">$\epsilon&gt;0)$</span></p>
  </blockquote>
  <p>Several questions still remain though:</p>
  <ol>
  <li>The newest implementation of Clustal Omega (that I downloaded) has source code that instead chooses <span class="math-container">$t = (\log N)^2$</span>, why changed?</li>
  <li>The original mBED paper chooses <span class="math-container">$t = (\log N)^2$</span>, but it was not justified on how they chose this number instead of <span class="math-container">$\log N$</span></li>
  </ol>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-07-25T07:35:38.823Z
Answers.LastActivityDate: 2020-07-25T08:22:30.147Z
Answers.LastEditDate: 2020-07-25T08:22:30.147Z
Answers.UserDisplayName: runeblaze
Body: <p>In the <a href="https://www.embopress.org/doi/full/10.1038/Msb.2011.75" rel="nofollow noreferrer">Clustal Omega paper</a>, it says the following about mBED (<span class="math-container">$N$</span> is the number of input sequences, I assume):</p>
  <blockquote>
  <p>we use a modified version of mBed (Blackshields et al , 2010), which has complexity of <span class="math-container">$O(N \log N)$</span></p>
  </blockquote>
  <p>But in the <a href="https://link.springer.com/article/10.1186/1748-7188-5-21" rel="nofollow noreferrer">mBED paper</a> it says the following (section 2):</p>
  <blockquote>
  <p>A number of <span class="math-container">$t$</span> sequences are initially sampled from the input dataset <span class="math-container">$X .$</span> Following the LLR
  algorithm, this value is set by default to <span class="math-container">$t=\left(\log _{2} N\right)^{2} .$</span></p>
  </blockquote>
  <blockquote>
  <p>After the seed sequences in <span class="math-container">$R$</span> have been chosen, all sequences in the input data are associated with a <span class="math-container">$t$</span>-dimensional vector. This is done simply by computing the distances from all sequences to each of the <span class="math-container">$t$</span> seeds.</p>
  </blockquote>
  <p>Then my conclusion is that this would lead to a complexity of <span class="math-container">$O(N (\log N)^2)$</span> because for each  sequence (in total <span class="math-container">$N$</span> of them), distances to <span class="math-container">$t = (\log N)^2$</span> sequences must be calculated. Where did I do wrong?</p>
  
Tags: <phylogenetics>
Title: mBED has time complexity $O(n \lg n)$, claimed by Clustal Omega paper, why?
ThreadText: # mBED has time complexity $O(n \lg n)$, claimed by Clustal Omega paper, why?
  
  (Asked by: username_0 on 2020-07-23)
  
  In the [Clustal Omega paper](https://www.embopress.org/doi/full/10.1038/Msb.2011.75), it says the following about mBED ($N$ is the number of input sequences, I assume):
  
  > we use a modified version of mBed (Blackshields et al , 2010), which has complexity of $O(N \log N)$
  
  But in the [mBED paper](https://link.springer.com/article/10.1186/1748-7188-5-21) it says the following (section 2):
  
  > A number of $t$ sequences are initially sampled from the input dataset $X .$ Following the LLR
  > algorithm, this value is set by default to $t=\left(\log \_{2} N\right)^{2} .$
  
  > After the seed sequences in $R$ have been chosen, all sequences in the input data are associated with a $t$-dimensional vector. This is done simply by computing the distances from all sequences to each of the $t$ seeds.
  
  Then my conclusion is that this would lead to a complexity of $O(N (\log N)^2)$ because for each sequence (in total $N$ of them), distances to $t = (\log N)^2$ sequences must be calculated. Where did I do wrong?
  
  **Tags:** phylogenetics
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_0 on 2020-07-25. Score: 1
  
  Turns out that I was dumb: I misread.
  
  The Clustal Omega paper (in the supplementary materials) chose $t = \log N$, which I think originates from this claim from this part of the Linial et al. paper:
  
  > In random polynomial time $X$ may be embedded in $l\_{2}^{O(\log n)}$ with distortion $\leq(1+\epsilon) \cdot c\_{2}(X)$ (for any $\epsilon>0)$
  
  Several questions still remain though:
  
  1. The newest implementation of Clustal Omega (that I downloaded) has source code that instead chooses $t = (\log N)^2$, why changed?
  2. The original mBED paper chooses $t = (\log N)^2$, but it was not justified on how they chose this number instead of $\log N$
  
  
  ---
  
  