Misplaced Pages

#629370

54-473: HMMER is the core utility that protein family databases such as Pfam and InterPro are based upon. Some other bioinformatics tools such as UGENE also use HMMER. HMMER3 also makes extensive use of vector instructions to increase computational speed. This work is based upon an earlier publication showing a significant acceleration of the Smith-Waterman algorithm for aligning two sequences. A profile HMM

108-419: A log-likelihood model that requires no calibration for estimating E-values , and allows the more accurate forward scores to be used for computing the significance of a homologous sequence. HMMER still lags behind BLAST in speed of DNA-based searches; however, DNA-based searches can be tuned such that an improvement in speed comes at the expense of accuracy. The major advance in speed was made possible by

162-435: A search space . This is achieved by trading optimality, completeness, accuracy, or precision for speed. In a way, it can be considered a shortcut. A heuristic function , also simply called a heuristic , is a function that ranks alternatives in search algorithms at each branching step based on available information to decide which branch to follow. For example, it may approximate the exact solution. The objective of

216-562: A clan. This portion has grown to around three-fourths by 2019 (version 32.0). To identify possible clan relationships, Pfam curators use the Simple Comparison Of Outputs Program (SCOOP) as well as information from the ECOD database. ECOD is a semi-automated hierarchical database of protein families with known structures, with families that map readily to Pfam entries and homology levels that usually map to Pfam clans. Pfam

270-444: A curated gathering threshold are classified as members of the protein family. The resulting collection of members is then aligned to the profile HMM to generate a full alignment. For each family, a manually curated gathering threshold is assigned that maximises the number of true matches to the family while excluding any false positive matches. False positives are estimated by observing overlaps between Pfam family hits that are not from

324-406: A deletion. Capturing this information gives them a better ability to detect true homologs than traditional BLAST -based approaches, which penalise substitutions, insertions and deletions equally, regardless of where in an alignment they occur. Profile HMMs center around a linear set of match (M) states, with one state corresponding to each consensus column in a sequence alignment. Each M state emits

378-574: A domain or extended structure. Motifs are usually shorter sequence units found outside of globular domains. The descriptions of Pfam families are managed by the general public using Misplaced Pages (see #Community curation ). As of release 29.0, 76.1% of protein sequences in UniprotKB matched to at least one Pfam domain. New families come from a range of sources, primarily the PDB and analysis of complete proteomes to find genes with no Pfam hit. For each family,

432-413: A file or executing process is found to contain matching code patterns and/or to be performing that set of activities, then the scanner infers that the file is infected. The most advanced part of behavior-based heuristic scanning is that it can work against highly randomized self-modifying/mutating ( polymorphic ) viruses that cannot be easily detected by simpler string scanning methods. Heuristic scanning has

486-505: A glimpse of theory. The latter are exposed to a larger number of pitfalls. When a heuristic is reused in various contexts because it has been seen to "work" in one context, without having been mathematically proven to meet a given set of requirements, it is possible that the current data set does not necessarily represent future data sets (see: overfitting ) and that purported "solutions" turn out to be akin to noise. Statistical analysis can be conducted when employing heuristics to estimate

540-462: A heuristic is not admissible, it may never find the goal, either by ending up in a dead end of graph G {\displaystyle G} or by skipping back and forth between two nodes v i {\displaystyle v_{i}} and v j {\displaystyle v_{j}} where i , j ≠ g {\displaystyle {i,j}\neq g} . The word "heuristic" came into usage in

594-599: A heuristic is to produce a solution in a reasonable time frame that is good enough for solving the problem at hand. This solution may not be the best of all the solutions to this problem, or it may simply approximate the exact solution. But it is still valuable because finding it does not require a prohibitively long time. Heuristics may produce results by themselves, or they may be used in conjunction with optimization algorithms to improve their efficiency (e.g., they may be used to generate good seed values). Results about NP-hardness in theoretical computer science make heuristics

SECTION 10

#1732885043630

648-438: A heuristic selects branches more likely to produce outcomes than other branches. It is selective at each decision point, picking branches that are more likely to produce solutions. Antivirus software often uses heuristic rules for detecting viruses and other forms of malware. Heuristic scanning looks for code and/or behavioral patterns common to a class or family of viruses, with different sets of rules for different viruses. If

702-438: A new system that allowed registered users anywhere in the world to add or modify Pfam families. Heuristic algorithm In mathematical optimization and computer science , heuristic (from Greek εὑρίσκω "I find, discover" ) is a technique designed for problem solving more quickly when classic methods are too slow for finding an exact or approximate solution, or when classic methods fail to find any exact solution in

756-603: A report on the taxonomic breakdown, and the domain organisation of the hits. Search results can then be filtered according to either parameter. The web service is currently run out of the European Bioinformatics Institute (EBI) in the United Kingdom, while development of the algorithm is still performed by Sean Eddy's team in the United States. Major reasons for relocating the web service were to leverage

810-410: A representative subset of sequences are aligned into a high-quality seed alignment. Sequences for the seed alignment are taken primarily from pfamseq (a non-redundant database of reference proteomes) with some supplementation from UniprotKB . This seed alignment is then used to build a profile hidden Markov model using HMMER . This HMM is then searched against sequence databases, and all hits that reach

864-410: A single residue (amino acid or nucleotide). The probability of emitting a particular residue is determined largely by the frequency at which that residue has been observed in that column of the alignment, but also incorporates prior information on patterns of residues that tend to co-occur in the same columns of sequence alignments. This string of match states emitting amino acids at particular frequencies

918-453: A subsequence of the target) and global alignment (align a complete model to a complete target sequence), HMMER3 only performs local alignment. This restriction is due to the difficulty in calculating the significance of hits when performing local/global alignments using the new algorithm. Several implementations of profile HMM methods and related position-specific scoring matrix methods are available. Some are listed below: Pfam Pfam

972-407: A substantial reorganisation to further reduce manual effort involved in curation and allow for more frequent updates. Circa 2022, Pfam was integrated into InterPro at the European Bioinformatics Institute . Curation of such a large database presented issues in terms of keeping up with the volume of new families and updated information that needed to be added. To speed up releases of the database,

1026-525: Is a database of protein families that includes their annotations and multiple sequence alignments generated using hidden Markov models . The latest version of Pfam, 37.0, was released in June 2024 and contains 21,979 families. It is currently provided through InterPro website. The general purpose of the Pfam database is to provide a complete and accurate classification of protein families and domains. Originally,

1080-466: Is a variant of an HMM relating specifically to biological sequences. Profile HMMs turn a multiple sequence alignment into a position-specific scoring system, which can be used to align sequences and search databases for remotely homologous sequences. They capitalise on the fact that certain positions in a sequence alignment tend to have biases in which residues are most likely to occur, and are likely to differ in their probability of containing an insertion or

1134-494: Is analogous to position specific score matrices or weight matrices. A profile HMM takes this modelling of sequence alignments further by modelling insertions and deletions, using I and D states, respectively. D states do not emit a residue, while I state do emit a residue. Multiple I state can occur consecutively, corresponding to multiple residues between consensus columns in an alignment. M, I and D states are connected by state transition probabilities, which also vary by position in

SECTION 20

#1732885043630

1188-544: Is available in the form of a web server. The service facilitates searches across a range of databases, including sequence databases such as UniProt , SwissProt , and the Protein Data Bank , and HMM databases such as Pfam , TIGRFAMs and SUPERFAMILY . The four search types phmmer, hmmsearch, hmmscan and jackhmmer are supported (see Programs ). The search function accepts single sequences as well as sequence alignments or profile HMMs. The search results are accompanied by

1242-456: Is best. HMMER sequence alignments are accompanied by posterior probability annotations, indicating which portions of the alignment have been assigned high confidence and which are more uncertain. A major improvement in HMMER3 was the inclusion of DNA/DNA comparison tools. HMMER2 only had functionality to compare protein sequences. While HMMER2 could perform local alignment (align a complete model to

1296-410: Is currently the best next step regardless of whether that prevents (or even makes impossible) good steps later. It is a heuristic in the sense that practice indicates it is a good enough solution, while theory indicates that there are better solutions (and even indicates how much better, in some cases). Another example of heuristic making an algorithm faster occurs in certain search problems. Initially,

1350-553: Is expected that DUFs will eventually outnumber families of known function. Over time both sequence and residue coverage have increased, and as families have grown, more evolutionary relationships have been discovered, allowing the grouping of families into clans. Clans were first introduced to the Pfam database in 2005. They are groupings of related families that share a single evolutionary origin, as confirmed by structural, functional, sequence and HMM comparisons. As of release 29.0, approximately one third of protein families belonged to

1404-519: Is named in order of addition. Names of these entries are updated as their functions are identified. Normally when the function of at least one protein belonging to a DUF has been determined, the function of the entire DUF is updated and the family is renamed. Some named families are still domains of unknown function, that are named after a representative protein, e.g. YbbR. Numbers of DUFs are expected to continue increasing as conserved sequences of unknown function continue to be identified in sequence data. It

1458-496: Is reviewed by curators before it is displayed on the Pfam website. Almost all cases of vandalism have been corrected by the community before they reach curators, however. Pfam is run by an international consortium of three groups. In the earlier releases of Pfam, family entries could only be modified at the Cambridge, UK site, limiting the ability of consortium members to contribute to site curation. In release 26.0, developers moved to

1512-495: The Zinc finger article. An automated procedure for generating articles based on InterPro and Pfam data has also been implemented, which populates a page with information and links to databases as well as available images, then once an article has been reviewed by a curator it is moved from the Sandbox to Misplaced Pages proper. In order to guard against vandalism of articles, each Misplaced Pages revision

1566-429: The travelling salesman problem (TSP): so as to select the order to draw using a pen plotter . TSP is known to be NP-hard so an optimal solution for even a moderate size problem is difficult to solve. Instead, the greedy algorithm can be used to give a good but not optimal solution (it is an approximation to the optimal answer) in a reasonably short amount of time. The greedy algorithm heuristic says to pick whatever

1620-454: The community were invited to create one and inform the curators, in order for it to be linked in. It is anticipated that while community involvement will greatly improve the level of annotation of these families, some will remain insufficiently notable for inclusion in Misplaced Pages, in which case they will retain their original Pfam description. Some Misplaced Pages articles cover multiple families, such as

1674-454: The computing infrastructure at the EBI, and to cross-link HMMER searches with relevant databases that are also maintained by the EBI. The latest stable release of HMMER is version 3.0. HMMER3 is complete rewrite of the earlier HMMER2 package, with the aim of improving the speed of profile-HMM searches. Major changes are outlined below: A major aim of the HMMER3 project, started in 2004 was to improve

HMMER - Misplaced Pages Continue

1728-638: The creation of other resources such as iPfam, which catalogs domain-domain interactions within and between proteins, based on information in structure databases and mapping of Pfam domains onto these structures. For each family in Pfam one can: Entries can be of several types: family, domain, repeat or motif. Family is the default class, which simply indicates that members are related. Domains are defined as an autonomous structural unit or reusable sequence unit that can be found in multiple protein contexts. Repeats are not usually stable in isolation, but rather are usually required to form tandem repeats in order to form

1782-399: The developers started a number of initiatives to allow greater community involvement in managing the database. A critical step in improving the pace of updating and improving entries was to open up the functional annotation of Pfam domains to the Misplaced Pages community in release 26.0. For entries that already had a Misplaced Pages entry, this was linked into the Pfam page, and for those that did not,

1836-444: The development of an approach for calculating the significance of results integrated over a range of possible alignments. In discovering remote homologs, alignments between query and hit proteins are often very uncertain. While most sequence alignment tools calculate match scores using only the best scoring alignment, HMMER3 calculates match scores by integrating across all possible alignments, to account for uncertainty in which alignment

1890-434: The following: In some cases, it may be difficult to decide whether the solution found by the heuristic is good enough because the theory underlying heuristics is not very elaborate. One way of achieving the computational performance gain expected of a heuristic consists of solving a simpler problem whose solution is also a solution to the initial problem. An example of approximation is described by Jon Bentley for solving

1944-411: The goal node v g {\displaystyle v_{g}} in a directed graph G {\displaystyle G} containing n {\displaystyle n} total nodes or vertices labeled v 0 , v 1 , ⋯ , v n {\displaystyle v_{0},v_{1},\cdots ,v_{n}} , "admissible" means roughly that

1998-428: The heuristic improves the algorithm's convergence while maintaining its correctness as long as the heuristic is admissible . In their Turing Award acceptance speech, Allen Newell and Herbert A. Simon discuss the heuristic search hypothesis: a physical symbol system will repeatedly generate and modify known symbol structures until the created structure matches the solution structure. Each following step depends upon

2052-423: The heuristic tries every possibility at each step, like the full-space search algorithm. But it can stop the search at any time if the current possibility is already worse than the best solution already found. In such search problems, a heuristic can be used to try good choices first so that bad paths can be eliminated early (see alpha–beta pruning ). In the case of best-first search algorithms, such as A* search ,

2106-567: The heuristic underestimates the cost to the goal or formally that h ( v i , v g ) ≤ d ⋆ ( v i , v g ) {\displaystyle h(v_{i},v_{g})\leq d^{\star }(v_{i},v_{g})} for all ( v i , v g ) {\displaystyle (v_{i},v_{g})} where i , g ∈ [ 0 , 1 , . . . , n ] {\displaystyle {i,g}\in [0,1,...,n]} . If

2160-416: The majority of proteins fell into just 1000 of these. Counter to this assertion, the Pfam database currently contains 16,306 entries corresponding to unique protein domains and families. However, many of these families contain structural and functional similarities indicating a shared evolutionary origin (see Clans ). A major point of difference between Pfam and other databases at the time of its inception

2214-472: The model, e.g. whether a sequence can have multiple consecutive hits to the same model (in the case of sequences with multiple instances of the same domain). The HMMER package consists of a collection of programs for performing functions using profile hidden Markov models. The programs include: The package contains numerous other specialised functions. In addition to the software package, the HMMER search function

HMMER - Misplaced Pages Continue

2268-411: The only viable option for a variety of complex optimization problems that need to be routinely solved in real-world applications. Heuristics underlie the whole field of Artificial Intelligence and the computer simulation of thinking, as they may be used in situations where there are no known algorithms . The trade-off criteria for deciding whether to use a heuristic for solving a given problem include

2322-681: The origins of proteins. Early genome projects, such as human and fly used Pfam extensively for functional annotation of genomic data. The InterPro website allows users to submit protein or DNA sequences to search for matches to families in the Pfam database. If DNA is submitted, a six-frame translation is performed, then each frame is searched. Rather than performing a typical BLAST search, Pfam uses profile hidden Markov models , which give greater weight to matches at conserved sites, allowing better remote homology detection, making them more suitable for annotating genomes of organisms with no well-annotated close relatives. Pfam has also been used in

2376-498: The potential to detect future viruses without requiring the virus to be first detected somewhere else, submitted to the virus scanner developer, analyzed, and a detection update for the scanner provided to the scanner's users. Some heuristics have a strong underlying theory; they are either derived in a top-down manner from the theory or are arrived at based on either experimental or real world data. Others are just rules of thumb based on real-world observation or experience without even

2430-501: The probability of incorrect outcomes. To use a heuristic for solving a search problem or a knapsack problem , it is necessary to check that the heuristic is admissible . Given a heuristic function h ( v i , v g ) {\displaystyle h(v_{i},v_{g})} meant to approximate the true optimal distance d ⋆ ( v i , v g ) {\displaystyle d^{\star }(v_{i},v_{g})} to

2484-575: The rationale behind creating the database was to have a semi-automated method of curating information on known protein families to improve the efficiency of annotating genomes. The Pfam classification of protein families has been widely adopted by biologists because of its wide coverage of proteins and sensible naming conventions. It is used by experimental biologists researching specific proteins, by structural biologists to identify new targets for structure determination, by computational biologists to organise sequences and by evolutionary biologists tracing

2538-466: The same clan. This threshold is used to assess whether a match to a family HMM should be included in the protein family. Upon each update of Pfam, gathering thresholds are reassessed to prevent overlaps between new and existing families. Domains of unknown function (DUFs) represent a growing fraction of the Pfam database. The families are so named because they have been found to be conserved across species, but perform an unknown role. Each newly added DUF

2592-547: The sequence alignment, to reflect the different frequencies of insertions and deletions across sequence alignments. The HMMER2 and HMMER3 releases used an architecture for building profile HMMs called the Plan 7 architecture, named after the seven states captured by the model. In addition to the three major states (M, I and D), six additional states capture non-homologous flanking sequence in the alignment. These 6 states collectively are important for controlling how sequences are aligned to

2646-556: The speed at which the database could be updated came in version 24.0, with the introduction of HMMER3, which is ~100 times faster than HMMER2 and more sensitive. Because the entries in Pfam-A do not cover all known proteins, an automatically generated supplement was provided called Pfam-B. Pfam-B contained a large number of small families derived from clusters produced by an algorithm called ADDA. Although of lower quality, Pfam-B families could be useful when no Pfam-A families were found. Pfam-B

2700-452: The speed of HMMER searches. While profile HMM-based homology searches were more accurate than BLAST-based approaches, their slower speed limited their applicability. The main performance gain is due to a heuristic filter that finds high-scoring un-gapped matches within database sequences to a query profile. This heuristic results in a computation time comparable to BLAST with little impact on accuracy. Further gains in performance are due to

2754-413: The step before it, thus the heuristic search learns what avenues to pursue and which ones to disregard by measuring how close the current step is to the solution. Therefore, some possibilities will never be generated as they are measured to be less likely to complete the solution. A heuristic method can accomplish its task by using search trees. However, instead of generating all possible solution branches,

SECTION 50

#1732885043630

2808-651: Was discontinued as of release 28.0, then reintroduced in release 33.1 using a new clustering algorithm, MMSeqs2. Pfam was originally hosted on three mirror sites around the world to preserve redundancy. However between 2012 and 2014, the Pfam resource was moved to EMBL-EBI , which allowed for hosting of the website from one domain (xfam.org), using duplicate independent data centres. This allowed for better centralisation of updates, and grouping with other Xfam projects such as Rfam , TreeFam , iPfam and others, whilst retaining critical resilience provided by hosting from multiple centres. From circa 2014 to 2016, Pfam underwent

2862-489: Was founded in 1995 by Erik Sonnhammer, Sean Eddy and Richard Durbin as a collection of commonly occurring protein domains that could be used to annotate the protein coding genes of multicellular animals. One of its major aims at inception was to aid in the annotation of the C. elegans genome. The project was partly driven by the assertion in ‘One thousand families for the molecular biologist’ by Cyrus Chothia that there were around 1500 different families of proteins and that

2916-520: Was the use of two alignment types for entries: a smaller, manually checked seed alignment, as well as a full alignment built by aligning sequences to a profile hidden Markov model built from the seed alignment. This smaller seed alignment was easier to update as new releases of sequence databases came out, and thus represented a promising solution to the dilemma of how to keep the database up to date as genome sequencing became more efficient and more data needed to be processed over time. A further improvement to

#629370