[Bioclusters] URGENT: Time Complexity for Blast, HMMsearch etc.

[Joe Landman]

Hi Intikhab:

  I haven't looked recently, but (old memory) I seem to remember that the 
time complexity for NCBI BLAST was on the order of O(N_query_seq * 
N_library_seq * f(Length_query_seq) )  where 

	N_query_seq is the number of query sequences
	N_library_seq is the number of library sequences
	f(Length_query_seq) is a function of the length of the query 
sequences.

As I remember, people (used to) talk in terms of the number of cells.  A 
cell being the number of base pairs in the library multiplied by the 
number of base pairs in the query.  We used to quote (for SGI 
GenomeCluster) some number of cells/second for our search rates.

  I think this provided some estimates on computational complexity, but I 
haven't seen a real analysis of this.

Joe

On Sun, 9 Jan 2005, Intikhab Alam wrote:

> 
> Hi,
> 
> We urgently need some information regarding the time/computational
> complexity of HMMsearch, PSI-Blast, PHI-Blast and Mast. Are there any
> results available? If not, what is the difficulty in estimating the time
> complexity of these methods?
> 
> Best Wishes &
> Happy new year.
> 
> Intikhab Alam/ Georg Fuellen
> 
> PS. We apologize if any one of you received this message twice.
> 
> ---
> Intikhab Alam
> PhD Scholar
> 
> International NRW Graduate School in Bioinformatics and Genome Research
> Center for Biotechnology (CeBiTec), University of Bielefeld
> Universitaetsstr. 25, D-33615 Bielefeld, Germany
> 
> P: +49 (0) 521 106-4915 , F: +49 (0) 521 106-6490
> E: intikhab at cebitec.uni-bielefeld.de
> w: http://www.cebitec.uni-bielefeld.de/~intikhab
>     ~-_-_~GS_BiG~_-_-~
> 
> ----- Original Message ----- 
> From: "Dan Bolser" <dmb at mrc-dunn.cam.ac.uk>
> To: "Intikhab Alam" <intikhab at cebitec.uni-bielefeld.de>
> Cc: <ssml-general at bioinformatics.org>; <bundschuh at mps.ohio-state.edu>
> Sent: Sunday, January 09, 2005 6:19 PM
> Subject: Re: [ssml] URGENT: Time Complexity for Blast, HMMsearch etc.
> 
> 
> > 
> > Try asking this question here...
> > 
> > bioclusters at bioinformatics.org
> > 
> > Many of the people on that list are experts in implementation strategies
> > for biological sequence analysis, and should be able to answer your
> > question.
> > 
> > Please post a summary of the results back if you get them :)
> > 
> > All the best,
> > Dan.
> 
> _______________________________________________
> Bioclusters maillist  -  Bioclusters at bioinformatics.org
> https://bioinformatics.org/mailman/listinfo/bioclusters
>