nodalpoint.org - Sequence analysis - Comments

String-blasting

Bob Carpenter — Wed, 20 Jun 2007 13:01:43 -0400

It's useful to apply BLAST-like techniques for searching over strings. This has been used to find variations of the names of genes in text by several groups. First, Michael Krauthammer, when he was at Columbia, used base-pairs to encode arbitrary strings (they're usually encoding amino acids), then queries gene and protein names for matches in the text of journal articles.

BLAST is really just edit distance with some exclusion heuristics which don't work at all well on small strings. So it's more natural to implement this notion directly, as Tsuruoka and Tsujii did. There's a nice description of the algorithms in Dan Gusfield's string algorithm bible.

Our LingPipe software provides an implementation of approximate dictionary matching following Gusfield. Here's a link to the class Javadoc: com.aliasi.dict.ApproxDictionaryChunker. We provide Tsuruoka and Tsujii's distance metric as a constant, but the distances are plug-and-play.

The really critical issue here is not just finding approximate matches of names of biomedical entities, but also disambiguating them. The acronym "ACT" means a lot of different things in different contexts. Figuring out which sense of a word or phrase is intended is a widely studied problem usually going under the heading of word sense disambiguation for common nouns or database linkage for proper nouns. This can either be done via unsupervised clustering, or by supervised database linkage if there are example contexts. Luckily, databases such as Entrez and KEGG provide GeneRIFs which include pointers to articles about specific genes. And evaluations like Biocreative are evaluating abilities of systems to figure out which gene is being mentioned in an article.

Bob Carpenter

Alias-i, Inc.

Flawed, but useful analogy: Bloogle

Duncan — Mon, 18 Jun 2007 07:29:40 -0400

I think Google is still a useful analogy for explaining BLAST to wet bench biologists, even if it does have its flaws. As for "Google isn't statistical", I disagree. What about all that statistics, probability and machine learning they use to builld and improve search results? Google (and other search engines) have very well defined metrics for measuring search quality, it's not all subjective. So despite its problems, search is still a handy analogy for describing BLAST that many people will be familiar with.

Analogy

Jonathan_Badger — Mon, 18 Jun 2007 07:02:50 -0400

Or, BLAST is like a microwave oven, except for sequences and not frozen burritos.

But seriously, I think the Google analogy isn't very good because
1) You don't search using a subject in BLAST, but by using another sequence. If Google worked that way, you'd give it a web page and it would find web pages similar to it.
2) BLAST is statistical, Google isn't. The only measure of how good a Google search is is the (subjective) opinion of the searcher.

If you want an analogy, assuming the students know some bench biology, how about "BLAST is an electronic Southern Blot"?

Solexa

chris — Mon, 21 May 2007 15:38:45 -0400

Solexa's technology produces even shorter reads - approx 30bp or so. It seems to be rapidly gaining in currency and analysis effort, if the Cold Spring Harbor meeting I attended earlier this month is any indication. A number of the large sequencing centers are choosing which way to split, and rather predictably both Solexa and 454 are getting attention. It will be interesting to see whether one emerges as a winner, or as suggested below, the combination will prove more powerful.

It is certainly becoming clear that these technologies are only likely to be useful in resequencing and EST-like projects where reference genome scaffolds already exist for assembly. I'm sure someone will come up with a clever work-around eventually, though.

More like these to come

badboyz — Fri, 11 May 2007 04:40:11 -0400

I think more and more people will be getting into this strategy at the beginning because 454's method much to be desired. On the other hand I think we should look carefully at how ABI is going to handle this new and emerging market. Their new high-throughput sequencer, SOLID, is based on the Agencourt sytem.

What would be really cool is if we could get a machine that could interchange modes. Quite an instrumentation challenge because one technology is bead-based (454) - not sure about SOLID - and the other is clone based (Sanger).

Bead Events ???

badboyz — Fri, 11 May 2007 04:28:36 -0400

I work with this data every day and let me say that it's a bit of pain and pleasure. The data management issue is something most of us dont have a problem with, but the pain point comes with having to continually refine our analysis to handle data inconsistencies.

On the whole 454 are making a great effort to deliver clean datasets to their customers. The longer reads do help although I'm a bit wary of these homopolymers and phase errors. And then there are these "Bead Events" that I keep on hearing about from various people. Personally, I dont think that we should ever expect too much from a new technology that is trying to take massive strides too soon. I like the idea of combining data sources together e.g Sanger + 454, Solexa + Sanger + 454, etc...

Mostapha Ronaghi, the inventor of the first pyrosequencing system, gave quite an informative talk in Malaysia about technologies, the state of the art, cost issues, etc. It can be streamed online from
http://www.mgrc.com.my/eLectureRonaghi.shtml.

Back to the data issue. Does anybody have more insights in what kind of inconsistencies or other things that people may need to be wary of?

Upgrade to 250bp in the works?

lbbros — Thu, 01 Feb 2007 02:42:28 -0500

As far as I know, the 454 people promised an "upgrade" of their technology to extend the maximum reads to 250 bp, I believe. Of course, I want to see it before I believe it.
However, I will be able to confirm in a few months, as the people responsible for the 454 instrument here want to perform that upgrade.

shorts reads

maximilianh — Wed, 31 Jan 2007 05:35:43 -0500

short reads are less a problem if one has a close genome at hand that has already been sequenced... the more genomes are available the easier it is to simply assemble by alignment, which is similar to what ensembl is doing now with their 3x genomes (see their 2007 article in NAR).

but anyways, yes, I was rather thinking about re-sequencing than sequencing from scratch.

Short reads

Neil — Tue, 30 Jan 2007 20:19:32 -0500

I just came out of a group meeting where 454 was discussed. Something I hadn't realised is that the read length is very short - 100 bp or so. This makes 454 great for resequencing, mapping reads onto existing assemblies and finishing, not so great for assembly of a genome from scratch. I'm excited by the idea that any lab could do a genome one day, but it won't be for a while yet.

I vaguely recall a technology where single DNA strands are fed through nanopores and changes in electrical resistance used to read bases? If anyone has a better memory than mine, feel free to comment. That kind of technology strikes me as "the way forward" for truly high-throughput sequencing.

Hackathons

Neil — Tue, 30 Jan 2007 20:13:13 -0500

This sounds great. The BioPerl guys used to organise "hackathons", but I guess they were restricted more to developers. It would be useful to get developers and end-users together for brainstorming workshops.

We have one of those

lbbros — Tue, 30 Jan 2007 18:16:15 -0500

I can say that handling the data from that beast is quite a task, according to my co-workers that rebuild and analyze the instrument's reads to get clean and (possibly gap-free) sequences.

In my opinion pyrosequencing such as what the 454 system does will not be a viable option for many institutes until there is this large problem to tackle. At first we had just one person working on the data, but it became evident that it wasn't enough. Now we have three people dedicated to the data analysis, on different projects.

phylogeny programs

maximilianh — Wed, 11 Oct 2006 11:53:13 -0400

I should have added joe felsentein's list of phylogeny programs to that post. quote: "Here are 267 of the phylogeny packages, and 32 free servers, that I know about." I admit that my example motif discovery is nothing against old disciplines like that...

BLAT and PatternHunter

maximilianh — Wed, 11 Oct 2006 11:27:17 -0400

thanks for the reference to PatternHunter... I've heard about it before but forgot it here.

Yes, it seems they simply put the database into memory. But well, given today's RAM prices that's not such a bad idea. BLAT does the same, with less sensitivity. And buying RAM is cheaper than buying some strange special hardware.

Neil: a) PatternHunter is also commercial though free for academic use.
b) You don't want to use BLAT in many appplications as it is a lot less sensitive than BLAST. I would rely on a blat only if the sequence is from the same or a very, very close species (like chimp or mouse to human) but that might also depend on the gene... So BLAT is really no alternative. Besides, BLAT is only free for academic use.

How can we know?

Neil — Wed, 11 Oct 2006 00:34:51 -0400

10 000 x does seem like an outrageous claim. How are we to know? The website is high on "corporate speak" and low on technical information. "More options than all other products combined", " a new paradigm in biotechnology", "the ultimate genomics search solution" etc. The only way to test their claims is to obtain the product. And that my friends is why open source is superior.
Itatsumaki has already noted the huge RAM dependency - 4 GB is hardly standard even on a modern laptop. If you want a fast, in-memory BLAST alternative, why not try BLAT?

RAM Dependent

Itatsumaki — Wed, 11 Oct 2006 00:03:26 -0400

I looked at this, and it seems like they're just playing tricks. Check out the RAM dependency they quote, it's huge. They suggest your required RAM is 24 times the size of the database in letters, divided by the word-size. So, for example if you try this algorithm against a large database like nt (non-redundant nucleotides) you would need a minimum of: 24 x 928,057,554 / 12 = 1.7 GB. So it seems like they are making a speed/space trade-off somewhere. Interestingly, that factor of 10k they quote sounds suspiciously like the difference between HD & memory access.

It also seems likely that the played around with the seeding. I think it's wrong to say that "local alignments have been worked on for decades without a lot of speed improvement". I think PatternHunter's asymmetric seeds are pretty convincing at doing just that, although I've never benchmarked it myself. Check out:
Bioinformatics. 2002 Mar;18(3):440-5.
PatternHunter: faster and more sensitive homology search.
Ma B, Tromp J, Li M.