Time And Space Complexity Of Motifviz Suite And Ucsc Genome And Table Browsers

Question

[Devst]

Hi,

I was searching for an esteem of the time and space complexity of some bioinformatic tools such as the Motifviz suite (clover, rover, motifish and possum) and the UCSC Browsers (Genome Browser and Table Browser).

I found very little information regarding the complexity of those algorithms, so I ask you if someone has any clue of what this complexity would be.

Regarding the UCSC Browsers, it seems that the Genome and the Table Browsers are actually two web user interfaces for the underlying UCSC databases. If I am not wrong, can I assume that the browsers time complexity are trivial compared to the database access time (done by, for example, MySQL)?

[brentp]

Re: UCSC, what are you trying to do? Depending on the query: is it on the database? if so, does it have joins? if so, how many? or are you BLAT'ing?

[Devst]

Well, I don't directly use the mysql database, but I send queries from the web user interface. To be more specific: I will use the Genome and Table Browsers in order to search for a sequence and extract parts of a sequence, respectively.

Answer 1

[Pierre Lindenbaum]

Regarding the UCSC Genome browser: People of the UCSC use mysql and AFAIK, the software handling the http requests is a C program: for quickly accessing the genomic data, they use a binning algorithm see:

The 'Bin' Column Used By Sam, Ucsc...

A detail of their old architecture was discussed here:

Ngs Data Centers: Storage, Backup, Hardware Etc..

[Devst]

That gives me a hint on understanding the structure of the UCSC database. I really appreciate it, but for now I cannot afford an investigation on UCSC complexity based on its database indexing system.