nodalpoint.org - blast - 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"?

mpiBLAST in EC2

cariaso — Sat, 21 Apr 2007 14:15:31 -0400

I've got mpiBLAST working well inside EC2. If you'd like to try it out, you will find this document helpful.
http://mpiblast.pbwiki.com/AmazonEC2

I will be at BioIT World at the end of April, and happy to discuss this topic with others.

Mike Cariaso * Bioinformatics Software * http://www.cariaso.com

EC2 MPI quickstart

Pete — Wed, 11 Apr 2007 21:53:55 -0400

Check out the second part of the tutorial I just posted on Data Wrangling, it is a bit less lengthy and should let you get a cluster running in a few minutes using the Amazon EC2 public image published based on the first post.

There are some Python scripts available on my blog to configure the MPI cluster on EC2, and it looks like you can hack them a bit to configure an EC2 BLAST cluster based on my tutorial:

MPI Cluster with Python and Amazon EC2 (part 2 of 3)

For message intensive code I expect performance will be a bit worse than people with research clusters are used to considering the effective 250 Mb/s interconnect. I'll be doing some benchmarking in coming weeks. The advantage of EC2 will be for startups and people who otherwise can't get access to or afford to build a permanent cluster. As EC2 moves out of Beta, I would guess that there may be some high performance options if Amazon finds enough demand for it.

-Pete

Re: new blast interface

dalloliogm — Tue, 03 Apr 2007 10:35:12 -0400

Finally!!
I've never liked the actual interface ;)
In particular, I hated the pop-up window to show the results and I think the interface of the actual blast is not too clear.
The new feature to keep track of the recent results sounds cool.
Thanks ;)

---

WHO AM I?
Your name is , seeker.

http://genome.imim.es/~giovanni

That tutorial is quite

Greg — Mon, 19 Mar 2007 10:26:38 -0400

That tutorial is quite full-on, a bit too much for me at the moment. I thought I remember someone offering to transfer their beta EC2 account to you in the comments of your post ?

Collaboration

pansapiens — Sun, 18 Mar 2007 15:33:13 -0400

I still don't have a EC2 account, but it looks like all the heavy lifting will have been done by the time I get a chance to play with EC2 ... check out Peter Skomoroch's extensive tutorial "On-Demand MPI Cluster with Python and EC2 (part 1 of 3)", if you haven't caught it already.

Andrew Perry -- http://pansapiens.blogspot.com/

mpiblast and EC2

cariaso — Mon, 05 Mar 2007 16:07:14 -0500

I'm an mpiBLAST developer and a heavy mpiBLAST user. I'm also moderately active with EC2. Despite a lot of interest in merging these two interests together, I haven't yet found an opportunity. If anyone reading this is considering such a project I'd be interested in comparing notes or collaborating.

As for MPI on EC2, like most parallel apps its a matter of the right topology for the right application. Communication between nodes is going to have fairly high latency compared to the more traditional dedicated clusters, but for some apps thats perfectly acceptable. The benefits of free transfers into and out of S3 is potentially a big win.

I would like to imagine that we could someday host a shared version of the major blastable DBs in S3, to alleviate the maintenance and transfer costs. For the moment, its probably inappropriate since its more designed for total replacement than the incremental growth.

--
Mike Cariaso * Bioinformatics Software * http://www.cariaso.com

EC2

mndoci — Mon, 05 Mar 2007 13:09:52 -0500

I've heard the Amazon folk talk about EC2 a bit and also attended a workshop during Mindcamp. From what I can gather, S3 would be perfect for a small startup biotech. Scales well, cheap etc etc. EC2 might work for a company that does computation in bursts, especially using apps like BLAST, but for a company that is constantly crunching data, I am not yet convinced EC2 is the right solution over something like Sun's on-demand offering, which is more suited for number crunching apps (as noted in the article, I would not run MPI apps on EC2 based on current knowledge).

My Blog: http://mndoci.com