You will be presented with the abstract, introduction, and discussion section from a biomedical research article. Your task is to create a summary that a layperson can understand, capturing the essence of the research article. Keep essential scientific terms, but ensure that the language remains clear and the concepts are explained in an uncomplicated manner.

Title: Matt: Local Flexibility Aids Protein Multiple Structure Alignment}
Article:
Abstract:
Even when there is agreement on what measure a protein multiple structure alignment should be optimizing, finding the optimal alignment is computationally prohibitive. One approach used by many previous methods is aligned fragment pair chaining, where short structural fragments from all the proteins are aligned against each other optimally, and the final alignment chains these together in geometrically consistent ways. Ye and Godzik have recently suggested that adding geometric flexibility may help better model protein structures in a variety of contexts. We introduce the program Matt( Multiple Alignment with Translations and Twists), an aligned fragment pair chaining algorithm that, in intermediate steps, allows local flexibility between fragments: small translations and rotations are temporarily allowed to bring sets of aligned fragments closer, even if they are physically impossible under rigid body transformations. After a dynamic programming assembly guided by these “bent” alignments, geometric consistency is restored in the final step before the alignment is output. Matt is tested against other recent multiple protein structure alignment programs on the popular Homstrad and SABmark benchmark datasets. Matt's global performance is competitive with the other programs on Homstrad, but outperforms the other programs on SABmark, a benchmark of multiple structure alignments of proteins with more distant homology. On both datasets, Matt demonstrates an ability to better align the ends of α-helices and β-strands, an important characteristic of any structure alignment program intended to help construct a structural template library for threading approaches to the inverse protein-folding problem. The related question of whether Matt alignments can be used to distinguish distantly homologous structure pairs from pairs of proteins that are not homologous is also considered. For this purpose, a p-value score based on the length of the common core and average root mean squared deviation( RMSD) of Matt alignments is shown to largely separate decoys from homologous protein structures in the SABmark benchmark dataset. We postulate that Matt's strong performance comes from its ability to model proteins in different conformational states and, perhaps even more important, its ability to model backbone distortions in more distantly related proteins.
Introduction:
There are two related problems that protein structure alignment programs are designed to address. The first we will call the alignment problem, where the input is a set of k proteins that have a conserved structural common core, where the common core is defined as in Eidhammer et al.[25] as a set of residues that can be simultaneously superimposed with small structural variation. The desired output consists of a superimposition of the proteins in 3-D space, coupled with the list of which amino acid residues are declared to be in alignment and part of the core. The second problem, which we will call the discrimination problem, takes as input a pair of protein structures, and is supposed to output a yes/no answer( together with an associated score or confidence value) as to whether a good alignment can be found for these two protein structures or not. We discuss how to measure performance on the alignment problem first, and then on the discrimination problem below. The classical geometric way to measure the quality of a protein structural alignment involves two parameters: the number of amino acid residue positions that are found to participate in the alignment( and are therefore found to be part of the conserved structural core), as well as the average pairwise root mean squared deviation( RMSD)( where RMSD is calculated from the best rigid body transformation using least squares minimization[26]) between backbone atoms placed in alignment in the conserved core. Clearly, this is a bi-criteria optimization problem: the goal is to minimize the RMSD of the conserved core while maximizing the number of residues placed in the conserved core. We first take a traditional geometric approach: reporting for all programs and all benchmark datasets, the average number of residues placed into the common core structure, alongside the average RMS of the pairwise RMSDs among all pairs of residues that participate in a multiple alignment of a set of structures. In addition, results are compared against Homstrad reference alignments. This approach follows Godzik and Ye's evaluation of their multiple structure alignment program, POSA[27]. More sophisticated geometric scoring measures have also been suggested, some to collapse the bi-criteria optimization problem into a single score to be optimized[28], such as the Structal score[1], others to incorporate more environmental information into the similarity measure, such as secondary structure, or solvent accessibility[29, 30]. The p-value score that we develop to handle the discrimination problem, described below, is a collapse of the bi-criteria optimization problem into one score that provides a single lens on pairwise alignment quality. An alternative approach to measuring the performance of a structure alignment algorithm comes from the discrimination problem directly. Here, the measure is typically ROC curves; looking for the ratio of true and false positives and negatives from a “gold-standard” classification for what is alignable or not, based either on decoy structures or a classification scheme such as SCOP or CATH. Indeed, a possible concern with adding flexibility to protein structure would be that the added flexibility in our alignment might lead to an inability to distinguish structures that should have good alignments from those that do not. We therefore test our ability to distinguish true alignable structures from decoys on the SABmark dataset( which comes with a ready-made set of decoy structures) as compared to competitor programs. We introduce the program Matt( Multiple Alignment with Translations and Twists), an AFP fragment chaining method for pairwise and multiple sequence alignment that outperforms existing popular multiple structure alignment methods when tested on standard benchmark datasets. At the heart of Matt is a relaxation of the traditional rigid protein backbone transformations for protein superimposition, which allows protein structures flexibility to bend or rotate in order to come into alignment. While flexibility has been introduced into the study of protein folding in the context of docking[31, 32], particularly for the modeling of ligand binding[33], and more recently in decoy construction for ab initio folding algorithms[34, 35], it has only recently been incorporated into general-purpose pairwise[14, 36] and multiple[27] structure alignment programs. There are two reasons it makes sense to introduce flexibility into protein structure alignment. The first is the main reason that has been addressed in previous work, namely, aligning proteins that do not align well by means of rigid body transformations because their structures have been determined in different conformational states: a well-known example is that the fold of a protein will change depending on whether it is bound to a ligand or not[33]. Matt is designed to also address the second reason to introduce flexibility into protein structure alignment, namely to handle structural distortions as we align proteins whose shape becomes increasingly divergent outside the conserved core. We find that at each fixed value for number of aligned residues, Matt is competitive with other recent multiple structure alignment programs in average RMSD on the popular Homstrad[37] and outperforms them on the SABmark[38] benchmark datasets( see Tables 1, 2, and 3). We emphasize again that this is an apples-to-apples comparison of the best( i. e., the standard least squares RMSD minimization) rigid body transformation for Matt's alignments, just as it is for the other programs—while Matt allows impossible bends and breaks in intermediate stages of the algorithm, it is stressed that the final Matt alignments and RMSD scores come from legal, allowable “unbent” rigid body transformations. We also present RMSD/alignment length tradeoffs for Matt performance on the same datasets. In the case of Homstrad, where a manually curated “correct” structural alignment is made available as part of the benchmark, Matt alignments are also measured against the reference alignments, where we are again competitive with or outperforming previous structure alignment programs( see Table 1). In addition, Matt's ability to distinguish truly alignable folds from decoy folds is tested with the standard benchmark SABmark set of alignments and decoys[38]. The SABmark decoy set was constructed to contain, for each alignable subset, decoy structures that belong to a different SCOP superfamily, but whose sequences align reasonably well according to BLAST[38]. Thus, they may be more similar at the local level to the true positive examples, and thus fool a structure alignment program better than a random structure. Here, we tested both the “unbent” Matt alignments described above, but also the “bent” Matt alignments, where the residues are aligned allowing the impossible bends and breaks. We test Matt's performance both against the decoy set and also against random structures taken from the Protein Data Bank( PDB; http://www. rcsb. org/pdb). We use Matt's performance on the truly random structures to generate a p-value score for pairwise Matt alignments. Rather than choose from among the large number of competitor pairwise structural alignment programs, Matt was instead tested against other multiple structure aligners, in fact the same programs we used for measuring how well they aligned protein families known to have good alignments. The exception was that we also tested the FlexProt program[36], a purely pairwise structure alignment program that was of special interest because it also claims to handle flexibility in protein structures. We have made Matt along with its structural alignments available at http://groups. csail. mit. edu/cb/matt and http://matt. cs. tufts. edu so anyone can additionally compute any alternate alignment quality scores they favor. The only general protein structure alignment programs that previously tried to model flexibility are FlexProt[36] and Ye and Godzik's Fatcat[14]( both for pairwise alignment), and Fatcat's generalization to multiple structure alignment, POSA[27]. Fatcat is also an AFP chaining algorithm, except it allows a globally minimized number of translations or bends in the structure if it improves the overall alignment. In this way, it is able to capture homologous proteins with hinges, or other discrete points of flexibility, due to conformational change. Our program Matt is fundamentally different: it instead allows flexibilities everywhere between short fragments—that is, it does not seek to globally minimize the number of bends, but rather allows continuous small local perturbations in order to better match the “bent” RMSD between structures. Because Matt allows these flexibilities, it can put strict tolerance limits on “bent” RMSD, so it only keeps fragments that locally have very tight alignments. Up until the last step, Matt allows the dynamic program to assemble fragments in ways that are structurally impossible—one chain may have to break or rotate beyond the physical constraints imposed by the backbone molecules in order to simultaneously fit the best transformation. This is repaired in a final step, when the residue to residue alignment produced by this unrealistic “bent” transformation is retained; the best rigid-body transformation that preserves that alignment is found, and then either output along with the residue–residue correspondences produced by the “bent” Matt alignment or extended to include as yet unaligned residues that fall within a user-settable maximum RMSD cutoff under the new rigid-body transformation to form the final Matt “unbent” alignment. Matt accepts standard PDB files as input, and outputs alignment coordinates in PDB format as well. In addition, when only two structures are input, Matt outputs a p-value for whether or not Matt believes the structures are alignable( see below). There is an option to output the “bent” structures in PDB format. Matt also outputs the sequence alignment derived from the structural alignment in FASTA format and a Rasmol script to highlight aligned residues. Windows and Linux binaries and source code are available at http://groups. csail. mit. edu/cb/matt and http://matt. cs. tufts. edu. The input to Matt is a set of g groups of already multiply aligned protein structures( at the beginning of the algorithm, each structure is placed by itself into its own group). The iterative portion of the Matt algorithm runs g − 1 times, each time reducing the number of separate groups by 1 as it merges two sets of aligned structures in a progressive alignment. As we discuss in detail below, the Matt alignments produced in the iterative portion are not geometrically realized by rigid body transformations: they allow local “bends” in the form of transpositions and rotations. Once there is only one group left, Matt enters a final pass, where it corrects the global alignment into an alignment that obeys a user-settable RMSD cutoff by means of geometrically realizably rigid-body transformations. A flowchart describing the stages of the Matt algorithm appears in Figure 1.
Discussion:
We introduced the program Matt, which showed that detouring through local flexibility in an AFP alignment algorithm could aid in protein multiple structure alignment. We suggest that looking at local bends in protein structure captures similarity well for fundamental biological as well as for mathematical reasons. In particular, Matt may be both capturing flexibility inherent naturally in some protein structures themselves and modeling structural distortions in the common core that arise as proteins become more evolutionarily distant. Matt runs in O( k2n3 log n) time, where k is the number of sequences participating in the alignment and n is the length of the longest sequence in the alignment. Compared with Mustang and MultiProt, Matt takes about the same amount of time to complete running on the benchmark datasets. We find that Matt is typically several times slower on most sets of structures; however, there are a small percentage of sets of substructures in both benchmark datasets where both Mustang and MultiProt take orders of magnitude more time to complete their alignments than they do on the typical set of structures. Matt is saved in these difficult cases with lots of self-similar substructures by its implementation of the oct-trees, which allows for better pruning of the search space. Matt also supports a multithreaded implementation, which is faster still. Matt is sufficiently fast that it should be feasible to construct a set of reference alignments for similar fold classes based on Matt, covering the space of all known folds, which we intend to do. Examining some of the Matt alignments by hand, the program seems to typically do a better job of aligning the ends of α-helices and β-strands than its competitors; we therefore suggest that Matt may be a useful tool for construction of better sequence profiles for protein structure prediction, and for the construction of better templates for protein threading libraries. For these applications, both Matt's rigid unbent alignments and the geometrically impossible bent alignments may be of interest. Finally, looking at how Matt( or the other structure aligners) performs on the two SABmark benchmarks raises again the philosophical question of how far into the twilight zone it makes sense to align protein structures. Clearly at the superfamily level, there is typically substantial structural similarity. At the twilight zone level, there is much increased divergence. Examining these alignments in more details may help develop our intuition about the limits of comparative modeling for protein structure prediction as we go further into the twilight zone.
Proteins fold into complicated highly asymmetrical 3-D shapes . When a protein is found to fold in a shape that is sufficiently similar to other proteins whose functional roles are known , this can significantly aid in predicting function in the new protein . In addition , the areas where structure is highly conserved in a set of such similar proteins may indicate functional or structural importance of the conserved region . Given a set of protein structures , the protein structural alignment problem is to determine the superimposition of the backbones of these protein structures that places as much of the structures as possible into close spatial alignment . We introduce an algorithm that allows local flexibility in the structures when it brings them into closer alignment . The algorithm performs as well as its competitors when the structures to be aligned are highly similar , and outperforms them by a larger and larger margin as similarity decreases . In addition , for the related classification problem that asks if the degree of structural similarity between two proteins implies if they likely evolved from a common ancestor , a scoring function assesses , based on the best alignment generated for each pair of protein structures , whether they should be declared sufficiently structurally similar or not . This score can be used to predict when two proteins have sufficiently similar shapes to likely share functional characteristics .