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

CC BY-SA 4.0
2020-07-25T07:35:38.823Z
2020-07-25T08:22:30.147Z
2020-07-25T08:22:30.147Z
runeblaze
<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>

<phylogenetics>
mBED has time complexity $O(n \lg n)$, claimed by Clustal Omega paper, why?
# 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$


---

