Sequence Searching – How is it done?

Pairwise sequence alignments are calculated by BLAST, FASTA, and SSEARCH which is used to view the evolutionary structure of a protein or domain family from a single perspective. Pairwise alignments produce very accurate statistical significance estimates and perfect homology are found. Searches with models of protein families, using either PSI-BLAST or Hidden Markov Model (HMM) based methods, can identify far more homologs in a single search at little additional computational cost. Moreover, the multiple sequence alignments that are used to construct the position-specific scoring matrices of PSI-BLAST or the Hidden Markov Models used by HMMER (software package for sequence analysis which is used to identify homologous protein or nucleotide sequences, and to perform sequence alignments) provide important information about the most conserved regions in the protein; locating conserved regions in protein and domain families can dramatically improve predictions of the functional consequences of mutation. Multiple sequence alignments thus provide much more structural, functional, and phylogenetic information than pairwise alignments.

While multiple sequence alignments are much more informative, they cannot be used to find out the homology of two sequences which is more important criteria in sequence mapping. The inclusion of a protein into a multiple sequence alignment requires independent evidence for homology; multiple sequence alignment programs do not provide statistical estimates and will readily align non-homologous sequences, particularly non-homologous sequences that are highly ranked by chance in a similarity search. The assumption of homology can be especially misleading with iterative methods like PSI-BLAST, because once a non-homologous domain has been included in the multiple sequence alignment used to produce the position-specific scoring matrix, the matrix can become re-purposed towards finding members of the non-homologous family. Ideally, each sequence included in a multiple sequence alignment will be evaluated both to ensure that it shares significant similarity with some of the other members of the family, and that the boundaries of the included sequence correspond with the boundaries of the domain homology.

Meticulously building a multiple sequence alignment is exponentially more computationally expensive than pairwise alignment. Exact pairwise alignment algorithms require time proportional to the product of two sequences, so increasing the sequence lengths 2-fold increased the time required 4-fold. Fortunately, protein sequences have a limited range of lengths, so rigorous searches (SSEARCH) are routine. In contrast, the rigorous multiple sequence alignment of 10 sequences of length 400 would take proportional to 40010, so rigorous multiple sequence alignment is impractical. During the 1980s, progressive alignment strategies, like ClustalW were developed that simplified the problem to O(n2l2), where n is the number of sequences, and l is their average length. These early progressive alignment strategies suffered from the problem that gaps placed early on in the alignment could not be re-adjusted to reflect information from sequences aligned later. More recent multiple sequence alignment methods, like MAFFT and MUSCLE use iterative approaches that allow gaps to be re-positioned.

There is a much greater diversity of multiple sequence alignment algorithms than pairwise sequence alignment algorithms, largely because optimal pairwise solutions are readily available, but multiple sequence alignment strategies use different heuristic approximations. While different multiple sequence alignment programs will often produce modestly different results, most programs produce very similar results for sequences at modest evolutionary distances (greater than 40% identity), and the differences are found near the boundaries of gaps. A more common problem is multiple sequence alignments with large gaps, which may reflect the presence or absence of domains in a subset of the sequence set. Alignment only makes biological sense when the residues included in the alignment are homologous. Large differences in sequence length, or attempts to multiply align sequences that are locally, but not globally, homologous can produce very different results because the programs are aligning non-homologous domains.