Checking the Alignment

Courtesy of European Bioinformatics Institute KNOWLEDGE GAPS? Sequence alignments offer clues to both the function and evolution of novel genes. But a bewildering array of algorithms and parameters leaves many researchers unable to use these programs to their fullest potential. In the beginning, there was Needleman-Wunsch, which begat Smith-Waterman, which begat FASTA, which begat BLAST, and so on. Peel away the information technology jargon surrounding these alignment algorithms, and a powerful dynasty becomes evident. And this dynasty is anything but stagnant. Old stalwarts among the more familiar algorithms go through subtle changes. Newer, more specialized versions create handy choices that unsophisticated users overlook. Upstarts claim to be better, faster, and smarter at taking on the huge and growing piles of data in public and private repositories. The result is computational evolution, and even as formidable an expert as Lincoln Stein, at Cold Spring Harbor Laboratory in New York, finds he cannot keep up. "It would be a full-time job just to update a Web page of bioinformatics tools," he says. "I can only come to grips with a small piece of the field." Indeed, the European Bioinformatics Institute (EBI) in Hinxton, UK, offers 11 choices under "homology and similarity" in the toolbox on its Web site, and links to 12 options at its European Molecular Biology Laboratory (EMBL). Why so many? "This is a fallacy to think there is any one algorithm that solves all the problems," says UK-based bioinformatics programmer Ewan Birney of EMBL. "Different problems require different algorithms by necessity." NOT AN EXACT SCIENCE Sequence alignment is not an exact science, experts agree, but rather a tradeoff between speed and accuracy. The process matches segments of nucleic acid and protein to find sequences that are identical or similar to each other. Sometimes only portions of sequences match, but in ways that suggest they have a common ancestor and are, therefore, homologous. "The basic problem is [that] computer science is good at finding exact matches very quickly," explains Stephen Altschul, a key figure in the development of BLAST at the National Center for Biotechnology Information (NCBI). "Computer science doesn't have a good way of finding similarities short of doing an exhaustive search of every possibility." The earliest algorithm, Needleman-Wunsch (1970), aligns the full length of two known segments, performing what is called a global alignment. Smith-Waterman, published in 1981, does local alignment, searching for pieces that correspond to sequences in the query segment. Still in use, both algorithms are precise and time-consuming. "They are terrific, but they are extremely slow and are only useable for searching small databases," says Stein. Consequently, similarity searches often start with one of two heuristic algorithms that were published later: FASTA (pronounced "fast-A") in 1988 and BLAST in 1990. Each sacrifices exactitude for speed, searching databases in stages. First they break the data into chunks, scanning regions of nucleotide or protein to find those likely to hold a sequence similar to the query. Then they go back to the candidate regions and test their choices. BLAST is faster, scanning chunks that are 11 base pairs long in phase one. FASTA is more sensitive but slower, as it starts with smaller chunks and therefore must scan more segments before validating its selections. The drawback is each can miss small alignments. Nonetheless, BLAST and FASTA perform well enough to be used extensively and to inspire BLAT, a faster, cruder BLAST-like tool for large-scale alignment problems. Stein suggests scientists also familiarize themselves with the following variations and newer algorithms that can be accessed free on the Internet: BLASTN, to compare DNA to DNA BLASTP or FASTP, to find related proteins BLASTZ, to compare large nucleotide sequences PSI-BLAST, to do iterative protein searches GENEWISE, to align a protein to genomic DNA EXONERATE, to align a cDNA or expressed sequence tag to a genome PSI-BLAST is especially useful for finding distant proteins that are not obviously related to the original query, according to Stein. It repeats the search on the first proteins it hits, and keeps searching on new hits until the user tells it to stop. As a result, the search can turn up proteins distantly evolved from the original gene. "It may be [that] the function of the gene is known in a prokaryote or Archaea, which is a billion years away, and it is not known in human or mouse," Stein explains. Another useful tool, he adds, is a free program called RepeatMasker, which hides repetitive elements that will be picked up as noise in nucleotide searches. He also recommends the use of scoring matrices such as BLOSUM that take into account differences in how amino acids evolve. FREEWARE OR COMMERCIAL? To Stein's thinking, with so many free algorithms available in the public domain, scientists need not pay for sequence-alignment software. Many laboratories do pay, however, accessing open-source algorithms along with proprietary algorithms via commercial products. Even when they link to the BLAST and FASTA search engines on public databases, graphical interfaces can make tools such as Vector NTI from InforMax (recently acquired by Invitrogen, Carlsbad, Calif.) and LaserGene from DNAStar, of Madison, Wis., easier to use than going to the sites directly. That's a big attraction for scientists daunted by the explanatory material on the NCBI and EBI web sites. Options for storing and integrating data and privacy features can also be attractive. While he sees many advantages in using commercial software, Stuart M. Brown, director of the Research Computing Resource at New York University Medical Center, says these products do not always provide the latest versions of algorithms. Companies often provide older, more stable, best-of-breed tools rather than cutting-edge releases that have yet to prove themselves. "The return on investment is going to be in time saved. It's not going to be in better computing," he cautions. From the industry perspective, quality control is worth the wait. "We try to take the best of the best and make sure they have been validated broadly," says Scott Kahn, chief scientific officer at Accelrys of San Diego, maker of DS Gene, MacVector, and LabShare. Support also is better in the commercial sector, according to DNAStar marketing manager Jeff Briganti. "If you're using a state-of-the-art algorithm and it doesn't work, there's nobody to fix it," he says of some free sites. (Other commercial packages offering sequence alignment include Genamics Expression from Genamics of Hamilton, New Zealand; DNASIS MAX from MiraiBio of Alameda, Calif.; and Visual Cloning from Redasoft of Toronto.) But some sequence-alignment products are specialized. Sequencher from Ann Arbor, Mich.-based Gene Codes is built around a proprietary version of Smith-Waterman optimized for in-depth contig building. And Bioinformatics Solutions of Waterloo, Ontario, claims its proprietary PatternHunter technology is a hundred times faster than BLAST for homology searching. Some vendors complement their algorithms with specialized hardware to accelerate searches. The leaders are BlastMachine from Paracel of Pasadena, Calif.; DeCypher Accelerated Bioinformatics Solution from TimeLogic of Crystal Bay, Nev.; and the Bioccelerator product line, which Compugen of Tel Aviv recently transferred to Biocceleration. INEFFICIENCY REMAINS Whatever algorithm or product they use, many scientists do not make optimal use of them, according to bioinformatics experts. "The single most prominent mistake is probably something that 50 or 60% of bench biologists do," says Stein. "They use a nucleotide search when they could be using a protein search. Just switching to protein will immensely increase the number of satisfactory responses." Protein sequences evolve a lot more slowly than nucleotide sequences, and therefore are more likely to produce alignments, he explains. Another common mistake is not resetting default parameters before starting a search, according to Georges G. Grinstein, director of the Center for Biomolecular and Medical Informatics at the University of Massachusetts, Lowell. "Most people say, 'Find those that are close.' And close is what the problem is," he says. There are varying degrees of closeness, he says. "If you are a phylogenist, you want ancestral closeness. If you are a protein chemist, you are looking for protein closeness. You may be looking for other kinds of closeness." BLAST and FASTA parameters are chosen conservatively, so that a broad range of scientists will not miss things of interest, according to Altschul. To his thinking, the scoring systems for evaluating the similarities found are more important than the heuristics. "If you change the scoring system, the whole order of output changes, and you find different things than before," he says. Accordingly, Altschul recommends that scientists master the underlying statistics--in particular, the significance of an e-value. Similar to a p-value, the e-value estimates the likelihood of coming across a similar sequence through a random search of the database. The lower the e-value the more significant the result, but raising the e-value threshold before starting a search can bring in distantly related proteins, which may be desirable. Increasing the size of a database increases the likelihood of finding a similar sequence by chance; that is, it raises the e-value. Though these values are sometimes published, experts say they are often misunderstood and really only valid on the day a database is searched. PLAYING THE LOTTERY Scientists who do not appreciate basic concepts make silly mistakes, according to Darren Platt, director of computational biology and informatics at Exelixis, a biotechnology company in San Francisco. He offers the following example. Platt's group was using BLAST to assemble an entire genome, crunching the data overnight and delivering a new version each morning. One day the researcher who requested the search came to Platt with a complaint. Her previous results had come with a BLAST score of 10-270. Now her score was zero, and she wanted to know what had happened to her big hit. "She didn't realize that 10-270 was the closest number to zero the computer could represent. This computer was basically saying there is zero probability that this hit occurred by chance," says Platt. In the game of sequence searching, she had hit the jackpot. Indeed, Altschul compares BLAST searching to playing the lottery. A number of hits will usually pop up at random. The scientist looking for a protein similar to the one being studied has to figure out which hit, if any, is the one needed. "One in ten million--is that something to get excited about? No. Someone was going to win [the lottery]," Altschul says. "You only get excited if it's you." How do you know that you've won, that your results can advance your research? The answer is in the biology. Even before they follow up with wet lab experimentation, Brown urges scientists to scroll down on the Web page and examine the actual alignment critically. "It's a skill that needs to be built like reading an X-ray," he advises." Says Grinstein, "The really great researchers are the ones who can take the results and hone in right away and say, 'This is correct, this is not correct,' or 'I've asked the wrong question. This is not what I'm asking for; I need to change.' And you begin to have a relationship with the software, so you basically interact, communicate with that software in a way that solves the problem at hand." Jane Salodof MacNeil (macneiljs@earthlink.net) is a freelance writer in Groveland, Mass. THE TWO HOUSES OF BLAST Courtesy of Dennis Wheeler, NCBI Graphical overview of an NCBI BLAST alignment Many people are familiar with BLAST, the NCBI's ubiquitous Basic Local Alignment Search Tool. But do they know WU-BLAST, the brainchild of Warren Gish, Washington University (WU) in St. Louis? Gish developed WU-BLAST after leaving the NCBI in 1994. "I began simply by fixing bugs in the latest version I'd released at the NCBI, but at the same time I was working on a version of BLAST that produced gapped alignments," he says. Gish succeeded in both goals, releasing WU-BLAST (free to academic and nonprofit researchers) in 1996. A year later the NCBI introduced gapped alignment capability into its software, and ever since, Gish has played David to NCBI's Goliath. Operating as a free public service, NCBI has a broad clientele making high-volume demands. This fall, researchers will have access to a new queuing system, capable of handling large searches that use as many as 10 to 20 CPUs simultaneously. One of those users is Darren Platt, who uses the best of both BLAST and WU-BLAST as director of computational biology and informatics at Exelixis in San Francisco. Platt praises WU-BLAST for its speed and sensitivity, and commends Gish for the support he provides to users. "In terms of features, they arrive more quickly in WU-BLAST than they have traditionally in the NCBI version," he says. Lincoln Stein at Cold Spring Harbor Laboratory is critical, however. "The major effect of having two versions of BLAST has been to make it hard for people to exchange BLAST output files, because the output files are subtly different. It's made it difficult to compare results. It's made it difficult to share BLAST databases." Gish counters that WU-BLAST is more compatible with BLAST files produced a dozen years ago, and that it is NCBI's BLAST that has changed more dramatically. The two versions have become less alike, agrees Stephen Altschul, an author of the original BLAST who remains at the NCBI. Though he questions whether the differences are significant, he suggests that having two versions of BLAST is more boon than bane. "I think in any field, there is this tension between standardization and competition, and the competition is always useful," Altschul says. "If one program is doing something well, it puts pressure on developers of other programs to do as well." function sendData() { document.frm.pathName.value = location.pathname; result = false if (document.frm.score[0].checked) result = true; if (document.frm.score[1].checked) result = true; if (document.frm.score[2].checked) result = true; if (document.frm.score[3].checked) result = true; if (document.frm.score[4].checked) result = true; if (!result) alert("Please select") return result; } .myradio{background-color : #94bee5} Please indicate on a 1 - 5 scale how strongly you would recommend this article to your colleagues? Not recommended 1 2 3 4 5 Highly recommended Please register your vote

Checking the Alignment

Interested in reading more?

Become a Member of