The O'Reilly Peer-to-Peer and Web Services Conference
oreilly.comO'Reilly Network
ConferencesInternationalSafari: Books Online

Arrow Home
Arrow Registration
Arrow Speakers
Arrow Keynotes
Arrow Tutorials
Arrow Sessions
Arrow BOFs
Arrow Community Meetings
Arrow Events
Arrow Exhibitors
Arrow Sponsors
Arrow Hotel/Travel
Arrow See & Do
Arrow Press
Arrow Mail List

Practical Tools For Innovation
O'Reilly Bioinformatics Technology Conference
January 28-31, 2002 -- Tucson, AZ
Chambered Nautilus


Speedup at What Cost? An Evaluation of Heuristic vs. Complete Homology Search Techniques

Christopher Dwan, Research Engineer, University of Minnesota

Track: Analysis
Date: Tuesday, January 29
Time: 4:15pm - 5:45pm
Location: Canyon IV

BLAST is the dominant survivor of a large crop of software products designed in response to the need for computationally efficient homology searches and sequence alignments. These heuristic algorithms give up the guarantee of absolutely correct answers in return for time and or space efficiency.

We used special purpose hardware (Field Programmable Gate Array boards implementing the Smith-Waterman algorithm) to calculate the optimal hits and alignments from a large set of DNA and amino acid data against a moderate sized (200,000 residue) query set. We evaluated these hits against several software implementations of heuristic algorithms (including BLAST) on two points: Accuracy of hit, and accuracy of alignment. Inaccurate or omitted hits can drive analysts in the wrong direction when annotating protein function. Inaccurate alignments can be used to generate incorrect numbers when calculating evolutionary distances and similar figures.

This presentation shows that with proper parameterization and knowledge of the limitations of the algorithms, heuristic techniques are acceptable substitutes for complete algorithms. We also show that simply using the defaults for these values can lead to misleading and incorrect results.

Read more about Speed at What Cost? by Chris Dwan in this article for The O'Reilly Network. Home | Conferences Home | Bioinformatics Conference Home
Registration | Speakers | Keynotes | Tutorials | Sessions | BOFs
Exhibitors | Sponsors | Hotel/Travel | Press | Mail List

© 2001, O'Reilly Media, Inc.