mBED has time complexity $O(n lg n)$, claimed by Clustal Omega paper, why?

Question

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?

runeblaze · Answer

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$

mBED has time complexity $O(n lg n)$, claimed by Clustal Omega paper, why?

One Answer

Add your own answers!

Related Questions

install bowtie2 from sources cannot find -ltbb

Normalize RNA seq data from multiple runs for expression analysis

Tool for rna/lna melting temperature prediction

Getting Unique Identifier List for GEO Datasets NCBI

MSA (protein) with biopython or something else?

Problem with merge data while trying to convert gene names in R

How to deal with the mismatches between gene names obtained from different sources?

Is there any value in scaffolding the output contigs of MEGAHIT assembler given a metagenomic dataset?

How to tell if our ligand-protein docking is good from AutoDock Vina’s result

Survival analysis using CoxPH – Effect of covariates

Parsing .vcf file for this information

Is there an efficient way to extract CIGAR strings for read pairs from bam files with python?

Filtering genes from cuffdiff results

Low Fraction of usable antibody reads in CiteSeq

RNA_Seq Analysis in R, propmapped function issue

Selecting part of an extracted ligand

Proper use of BWA MEM on multiplexed GBS sample

co-occurrence analysis and visualization for amplicon microbial data

How do I create a VCF file of all known pathogenic mutations in a gene of interest?

How do I write tests for a snakemake pipeline?

Ask a Question