\section{Introduction} \setcounter{footnote}{0} HMMER is used to search sequence databases for homologs of protein sequences, and to make protein sequence alignments. HMMER can be used to search sequence databases with single query sequences but it becomes particularly powerful when the query is an multiple sequence alignment of a sequence family. HMMER makes a \emph{profile} of the query that assigns a position-specific scoring system for substitutions, insertions, and deletions. HMMER profiles are probabilistic models called ``profile hidden Markov models'' (profile HMMs) \citep{Krogh94,Eddy98,Durbin98}. Compared to BLAST, FASTA, and other sequence alignment and database search tools based on older scoring methodology, HMMER aims to be significantly more accurate and more able to detect remote homologs, because of the strength of its underlying probability models. In the past, this strength came at a significant computational cost, with profile HMM implementations running about 100x slower than comparable BLAST searches. With HMMER3, HMMER is now essentially as fast as BLAST. \subsection{How to avoid reading this manual} I hate reading documentation. If you're like me, you're sitting here thinking, \pageref{manualend} pages of documentation, you must be joking! I just want to know that the software compiles, runs, and gives apparently useful results, before I read some \pageref{manualend} exhausting pages of someone's documentation. For cynics that have seen one too many software packages that don't work: \begin{itemize} \item Follow the quick installation instructions on page \pageref{section:installation}. An automated test suite is included, so you will know immediately if something went wrong.\footnote{Nothing should go wrong.} \item Go to the tutorial section on page \pageref{section:tutorial}, which walks you through some examples of using HMMER on real data. \end{itemize} Everything else, you can come back and read later. \subsection{How to avoid using this software (links to similar software)} Several implementations of profile HMM methods and related position-specific scoring matrix methods are available. \begin{center} \begin{tabular}{lp{5in}l} Software & URL \\ \hline HMMER & \url{http://hmmer.org/}\\ SAM & \url{http://www.cse.ucsc.edu/research/compbio/sam.html}\\ PSI-BLAST & \url{http://www.ncbi.nlm.nih.gov/Education/BLASTinfo/psi1.htm}\\ PFTOOLS & \url{http://www.isrec.isb-sib.ch/profile/profile.html}\\ \end{tabular} \end{center} The UC Santa Cruz SAM software is the closest relative of HMMER. \subsection{What profile HMMs are} Profile HMMs are statistical models of multiple sequence alignments, or even of single sequences. They capture position-specific information about how conserved each column of the alignment is, and which residues are likely. Anders Krogh, David Haussler, and co-workers at UC Santa Cruz introduced profile HMMs to computational biology \citep{Krogh94}, adopting HMM techniques which have been used for years in speech recognition. HMMs had been used in biology before the Krogh/Haussler work, notably by Gary Churchill \citep{Churchill89}, but the Krogh paper had a dramatic impact because HMM technology was so well-suited to the popular ``profile'' methods for searching databases using multiple sequence alignments instead of single query sequences. ``Profiles'' had been introduced by Gribskov and colleagues \citep{Gribskov87,Gribskov90}, and several other groups introduced similar approaches at about the same time, such as ``flexible patterns'' \citep{Barton90}, and ``templates''\citep{Bashford87,Taylor86}. The term ``profile'' has stuck.\footnote{There has been agitation in some quarters to call all such models ``position specific scoring matrices'', PSSMs, but certain small nocturnal North American marsupials have a prior claim on the name.} All profile methods (including PSI-BLAST \citep{Altschul97}) are more or less statistical descriptions of the consensus of a multiple sequence alignment. They use \emph{position-specific} scores for amino acids (or nucleotides) and position specific penalties for opening and extending an insertion or deletion. Traditional pairwise alignment (for example, BLAST \citep{Altschul90}, FASTA \citep{Pearson88}, or the Smith/Waterman algorithm \citep{Smith81}) uses position-{\em independent} scoring parameters. This property of profiles captures important information about the degree of conservation at various positions in the multiple alignment, and the varying degree to which gaps and insertions are permitted. The advantage of using HMMs is that HMMs have a formal probabilistic basis. We use probability theory to guide how all the scoring parameters should be set. Though this might sound like a purely academic issue, this probabilistic basis lets us do things that more heuristic methods cannot do easily. One of the most important is that HMMs have a consistent theory for setting position-specific gap and insertion scores. The methods are consistent and therefore highly automatable, allowing us to make libraries of hundreds of profile HMMs and apply them on a very large scale to whole genome analysis. One such database of protein domain models is Pfam \citep{Sonnhammer97,Finn10}, which is a significant part of the Interpro protein domain annotation system \citep{Mulder03}. The construction and use of Pfam is tightly tied to the HMMER software package. Profile HMMs do have important limitations. One is that HMMs do not capture any higher-order correlations. An HMM assumes that the identity of a particular position is independent of the identity of all other positions.\footnote{This is not strictly true. There is a subtle difference between an HMM's state path (a first order Markov chain) and the sequence described by an HMM (generated from the state path by independent emissions of symbols at each state).} Profile HMMs are often not good models of structural RNAs, for instance, because an HMM cannot describe base pairs. \subsection{Applications of profile HMMs} HMMER can be used to replace BLASTP and PSI-BLAST for searching databases with single query sequences. With HMMER3, we now include two programs for searching databases with single query sequences: \prog{phmmer} and \prog{jackhmmer}, where \prog{jackhmmer} is an iterative search akin to PSI-BLAST. Another application of HMMER is when you are working on a protein sequence family, and you have carefully constructed a multiple sequence alignment. Your family, like most protein families, has a number of strongly (but not absolutely) conserved key residues, separated by characteristic spacing. You wonder if there are more members of your family in the sequence databases, but the family is so evolutionarily diverse, a BLAST search with any individual sequence doesn't even find the rest of the sequences you already know about. You're sure there are some distantly related sequences in the noise. You spend many pleasant evenings scanning weak BLAST alignments by eye to find ones with the right key residues are in the right places, but you wish there was a computer program that did this a little better. Another application is the automated annotation of the domain structure of proteins. Large databases of curated alignments and HMMER models of known domains are available, including Pfam \citep{Finn10} and SMART \citep{Letunic06} in the Interpro database consortium \citep{Mulder03}. (Many ``top ten protein domains'' lists, a standard table in genome analysis papers, rely heavily on HMMER annotation.) Say you have a new sequence that, according to a BLAST analysis, shows a slew of hits to receptor tyrosine kinases. Before you decide to call your sequence an RTK homologue, you suspiciously recall that RTK's are, like many proteins, composed of multiple functional domains, and these domains are often found promiscuously in proteins with a wide variety of functions. Is your sequence really an RTK? Or is it a novel sequence that just happens to have a protein kinase catalytic domain or fibronectin type III domain? Another application is the automated construction and maintenance of large multiple alignment databases. It is useful to organize sequences into evolutionarily related families. But there are thousands of protein sequence families, some of which comprise tens of thousands of sequences -- and the primary sequence databases continue to double every year or two. This is a hopeless task for manual curation; but on the other hand, manual curation is still necessary for high-quality, biologically relevant multiple alignments. Databases like Pfam \citep{Finn10} are constructed by distinguishing between a stable curated ``seed'' alignment of a small number of representative sequences, and ``full'' alignments of all detectable homologs; HMMER is used to make a model of the seed, search the database for homologs, and automatically produce the full alignment by aligning every sequence to the seed consensus. You may find other applications as well. Using hidden Markov models to make a linear consensus model of a bunch of related strings is a pretty generic problem, and not just in biological sequence analysis. HMMER3 has already been used to model mouse song [Elena Rivas, personal communication] and in the past HMMER has reportedly been used to model music, speech, and even automobile engine telemetry. If you use it for something particularly strange, I'd be curious to hear about it -- but I never, ever want to see my error messages showing up on the console of my Saab. \subsection{Design goals of HMMER3} In the past, profile HMM methods were considered to be too computationally expensive, and BLAST has remained the main workhorse of sequence similarity searching. The main objective of the HMMER3 project (begun in 2004) is to combine the power of probabilistic inference with high computational speed. We aim to upgrade some of molecular biology's most important sequence analysis applications to use more powerful statistical inference engines, without sacrificing computational performance. Specifically, HMMER3 has three main design features that \emph{in combination} distinguish it from previous tools: \begin{description} \item[\textbf{Explicit representation of alignment uncertainty.}] Most sequence alignment analysis tools report only a single best-scoring alignment. However, sequence alignments are uncertain, and the more distantly related sequences are, the more uncertain alignments become. HMMER3 calculates complete posterior alignment ensembles rather than single optimal alignments. Posterior ensembles get used for a variety of useful inferences involving alignment uncertainty. For example, any HMMER3 sequence alignment is accompanied by posterior probability annotation, representing the degree of confidence in each individual aligned residue. \item[\textbf{Sequence scores, not alignment scores.}] Alignment uncertainty has an important impact on the power of sequence database searches. It's precisely the most remote homologs -- the most difficult to identify and potentially most interesting sequences -- where alignment uncertainty is greatest, and where the statistical approximation inherent in scoring just a single best alignment breaks down the most. To maximize power to discriminate true homologs from nonhomologs in a database search, statistical inference theory says you ought to be scoring sequences by integrating over alignment uncertainty, not just scoring the single best alignment. HMMER3's log-odds scores are sequence scores, not just optimal alignment scores; they are integrated over the posterior alignment ensemble. \item[\textbf{Speed.}] A major limitation of previous profile HMM implementations (including HMMER2) was their slow performance. HMMER3 implements a new heuristic acceleration algorithm. For most queries, it's about as fast as BLAST. \end{description} Individually, none of these points is new. As far as alignment ensembles and sequence scores go, pretty much the whole reason why hidden Markov models are so theoretically attractive for sequence analysis is that they are good probabilistic models for explicitly dealing with alignment uncertainty. The SAM profile HMM software from UC Santa Cruz has always used full probabilistic inference (the HMM Forward and Backward algorithms) as opposed to optimal alignment scores (the HMM Viterbi algorithm). HMMER2 had the full HMM inference algorithms available as command-line options, but used Viterbi alignment by default, in part for speed reasons. Calculating alignment ensembles is even more computationally intensive than calculating single optimal alignments. One reason why it's been hard to deploy sequence scores for practical large-scale use is that we haven't known how to accurately calculate the statistical significance of a log-odds score that's been integrated over alignment uncertainty. Accurate statistical significance estimates are essential when one is trying to discriminate homologs from millions of unrelated sequences in a large sequence database search. The statistical significance of optimal alignment scores can be calculated by Karlin/Altschul statistics \citep{Karlin90,KarlinAltschul93}. Karlin/Altschul statistics are one of the most important and fundamental advances introduced by BLAST. However, this theory doesn't apply to integrated log-odds sequence scores (HMM ``Forward scores''). The statistical significance (expectation values, or E-values) of HMMER3 sequence scores is determined by using recent theoretical conjectures about the statistical properties of integrated log-odds scores which have been supported by numerical simulation experiments \citep{Eddy08}. And as far as speed goes, there's really nothing new about HMMER3's speed either. Besides Karlin/Altschul statistics, the main reason BLAST has been so useful is that it's so fast. Our design goal in HMMER3 was to achieve rough speed parity between BLAST and more formal and powerful HMM-based methods. The acceleration algorithm in HMMER3 is a new heuristic. It seems likely to be more sensitive than BLAST's heuristics on theoretical grounds. It certainly benchmarks that way in practice, at least in our hands. Additionally, it's very well suited to modern hardware architectures. We expect to be able to take good advantage of GPUs and other parallel processing environments in the near future. \subsection{What's still missing in HMMER3} Even though this is a stable public release that we consider suitable for large-scale production work (genome annotation, Pfam analysis, whatever), at the same time, HMMER3 remains a work in progress. We think the codebase is a suitable foundation for development of a number of significantly improved approaches to classically important problems in sequence analysis. Some of the more important ``holes'' for us are: \paragraph{DNA sequence comparison.} HMMER3's search pipeline is somewhat specialized to protein/protein comparison. Specifically, the pipeline works by filtering individual sequences, winnowing down to a subset of the sequences in a database that need close attention from the full heavy artillery of Bayesian inference. This strategy doesn't work for long DNA sequences; it doesn't filter the human genome much to say ``there's a hit on chromosome 1''. The algorithms need to be adapted to identify high-scoring regions of a target sequence, rather than filtering by whole sequence scores. (You can chop a DNA sequence into overlapping windows and HMMER3 would work fine on such a chopped-up database, but that's a disgusting kludge and I don't want to know about it.) \paragraph{Translated comparisons.} We'd of course love to have the HMM equivalents of BLASTX, TBLASTN, and TBLASTX. They'll come. \paragraph{Profile/profile comparison.} A number of pioneering papers and software packages have demonstrated the power of profile/profile comparison for even more sensitive remote homology detection. We will aim to develop profile HMM methods in HMMER with improved detection power, and at HMMER3 speed. \vspace{2em} We also have some technical and usability issues we will be addressing Real Soon Now: \paragraph{More sequence input formats.} HMMER3 will work fine with FASTA files for unaligned sequences, and Stockholm and ``aligned FASTA'' files for multiple sequence alignments. It has parsers for a handful of other formats (GenBank, EMBL, and UniProt flatfiles; SELEX format alignments) that we've tested somewhat. It's particularly missing parsers for some widely used alignment formats such as Clustal format, so using HMMER3 on the MSAs produced by many popular multiple alignment programs (MUSCLE or MAFFT for example) is harder than it should be, because it may require a reformat to Stockholm or aligned FASTA format. \paragraph{More alignment modes.} HMMER3 \emph{only} does local alignment. HMMER2 also could do glocal alignment (align a complete model to a subsequence of the target) and global alignment (align a complete model to a complete target sequence). The E-value statistics of glocal and global alignment remain poorly understood. HMMER3 relies on accurate significance statistics, far more so than HMMER2 did, because HMMER3's acceleration pipeline works by filtering out sequences with poor P-values. \paragraph{More speed.} Even on x86 platforms, HMMER3's acceleration algorithms are still on a nicely sloping bit of their asymptotic optimization curve. I still think we can accelerate the code by another two-fold or so. Additionally, for a small number of HMMs ($<1$\% of Pfam models), the acceleration core is performing relatively poorly, for reasons we pretty much understand (having to do with biased composition; most of these pesky models are hydrophobic membrane proteins), but which are nontrivial to work around. This'll produce an annoying behavior that you may notice: if you look systematically, sometimes you'll see a model that runs at something more like HMMER2 speed, 100x or so slower than an average query. This, needless to say, Will Be Fixed. \paragraph{More processor support.} One of the attractive features of the HMMER3 ``MSV'' acceleration algorithm is that it is a very tight and efficient piece of code, which ought to be able to take advantage of recent advances in using massively parallel GPUs (graphics processing units), and other specialized processors such as the Cell processor, or FPGAs. We have prototype work going on in a variety of processors, but none of this is far along as yet. But this work (combined with the parallelization) is partly why we expect to wring significantly more speed out of HMMER in the future. \subsection{How to learn more about profile HMMs} \textbf{Cryptogenomicon} (\url{http://cryptogenomicon.org/}) is a blog where I'll be talking about issues as they arise in HMMER3, and where you can comment or follow the discussion. Reviews of the profile HMM literature have been written by myself \citep{Eddy96,Eddy98} and by Anders Krogh \citep{Krogh98}. For details on how profile HMMs and probabilistic models are used in computational biology, see the pioneering 1994 paper from Krogh et al. \citep{Krogh94} or our book \emph{Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids} \citep{Durbin98}. To learn more about HMMs from the perspective of the speech recognition community, an excellent tutorial introduction has been written by Rabiner \citep{Rabiner89}. \begin{srefaq}{How do I cite HMMER?} There is still no ``real'' paper on HMMER. If you're writing for an enlightened (url-friendly) journal, the best reference is \url{http://hmmer.org/}. If you must use a paper reference, the best one to use is my 1998 profile HMM review \citep{Eddy98}. \end{srefaq}