Bioinformatics Asked by runeblaze on August 27, 2021

In the Clustal Omega paper, 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 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} Nright)^{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?

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:

- The newest implementation of Clustal Omega (that I downloaded) has source code that instead chooses $t = (log N)^2$, why changed?
- The original mBED paper chooses $t = (log N)^2$, but it was not justified on how they chose this number instead of $log N$

Answered by runeblaze on August 27, 2021

1 Asked on June 25, 2021 by suvar

5 Asked on June 25, 2021

differential expression featurecounts gene expression normalization rna seq

2 Asked on June 24, 2021 by pawan-verma

1 Asked on June 24, 2021 by curioustree

2 Asked on June 23, 2021 by equinox

0 Asked on June 22, 2021

2 Asked on June 21, 2021

1 Asked on June 20, 2021 by scamander

1 Asked on June 17, 2021 by beerzy

1 Asked on June 16, 2021 by mereven

1 Asked on June 13, 2021 by sujaypatil

1 Asked on June 12, 2021 by gypti

2 Asked on June 10, 2021 by plantgeek519

0 Asked on June 9, 2021

1 Asked on June 8, 2021 by nereus

Get help from others!

Recent Questions

- How Do I Get The Ifruit App Off Of Gta 5 / Grand Theft Auto 5
- Iv’e designed a space elevator using a series of lasers. do you know anybody i could submit the designs too that could manufacture the concept and put it to use
- Need help finding a book. Female OP protagonist, magic
- Why is the WWF pending games (“Your turn”) area replaced w/ a column of “Bonus & Reward”gift boxes?
- Does Google Analytics track 404 page responses as valid page views?

Recent Answers

- haakon.io on Why fry rice before boiling?
- Lex on Does Google Analytics track 404 page responses as valid page views?
- Peter Machado on Why fry rice before boiling?
- Joshua Engel on Why fry rice before boiling?
- Jon Church on Why fry rice before boiling?

© 2023 AnswerBun.com. All rights reserved. Sites we Love: PCI Database, MenuIva, UKBizDB, Menu Kuliner, Sharing RPP, SolveDir