Motif-biased protein sequence alignment

A memory-efficient algorithm for multiple sequence alignment with constraints

MOTIVATION

Recently, the concept of the constrained sequence alignment was proposed to incorporate the knowledge of biologists about structures/functionalities/consensuses of their datasets into sequence alignment such that the user-specified residues/nucleotides are aligned together in the computed alignment. The currently developed programs use the so-called progressive approach to efficiently obtain a constrained alignment of several sequences. However, the kernels of these programs, the dynamic programming algorithms for computing an optimal constrained alignment between two sequences, run in (gamman2) memory, where gamma is the number of the constraints and n is the maximum of the lengths of sequences. As a result, such a high memory requirement limits the overall programs to align short sequences only.

RESULTS

We adopt the divide-and-conquer approach to design a memory-efficient algorithm for computing an optimal constrained alignment between two sequences, which greatly reduces the memory requirement of the dynamic programming approaches at the expense of a small constant factor in CPU time. This new algorithm consumes only O(alphan) space, where alpha is the sum of the lengths of constraints and usually alpha << n in practical applications. Based on this algorithm, we have developed a memory-efficient tool for multiple sequence alignment with constraints.

AVAILABILITY

http://genome.life.nctu.edu.tw/MUSICME.

Multiple sequence threading: an analysis of alignment quality and stability

Methods that compare a protein sequence directly to a structure can be divided into those that construct a molecular model (threading methods) and those that perform a sequence alignment with the structure encoded as a sequence of structural states (one-dimensional/three-dimensional (1D/3D) matching). The former take into account the internal packing of the molecule but the latter do not. On the other hand, it is simple to include multiple sequence data in a 1D/3D comparison but difficult in a threading method. Here, a protein sequence/structure alignment method is described that uses a combination of matching predicted and observed residue exposure, predicted and observed secondary structure (1D/3D) together with pairwise packing interactions in the core (threading). Using a variety of distantly related and analogous protein structures, the multiple sequence threading (MST) method was compared to a single sequence threading (SST) method (that uses complex potentials of mean-force) and also to a multiple sequence alignment (MSA) program. It was found that the MST method produced alignments that were better than the best that could be obtained with either the SST or MSA method. The method was found to be stable to error in both secondary structure prediction and predicted exposure and also under variation of the key parameters (fully described in an Appendix). The contribution of the pairwise term was found to be small but without it, the correct alignments were less stable and structurally unreasonable deletions were observed when matching against larger structures. Using the parameters derived for alignment, the method was able to recognise related folds in the structure databank with a specificity comparable to other methods.

Multiple sequence threading: conditional gap placement

Preliminary work to improve on the gap placement in a novel multiple sequence threading method is presented here. Using the globin family, we construct measures for the assessment of gaps in a multiple sequence threading alignment based on the structural comparison of two of the proteins in the family. We take into account information from multiple sequence alignments on both the structure and sequence side of the problem. This work shows the parameterization of the problem allowing the foundation to optimize and test a gap placement weight or penalty. Four states were considered: deleted structure, inserted sequence, gap ends in structure, and broken ends in sequence. Each of these states was analyzed for exposure, occupancy and secondary structure. These measures enable us to gain insight into the placement of gaps in a multiple sequence threading alignment. We analyzed the most extreme violations of these properties and found in these cases that most secondary structures are broken by gaps. However, sequence inserts in structure were never found in deeply buried positions. Most end separations were 3-4 A in excess of the minimum 6 A, although some were larger. We show that the maximum amount of observed secondary structure found in inserts was about half of the predicted structure (typically 5 and 10%, respectively). A similar trend occurred with observed and predicted exposure in inserts. Our eventual aim is to devise a weight incorporating these measures of gap placement to further refine our algorithm for the threading of sequence on structure.

Multiple DNA and protein sequence alignment based on segment-to-segment comparison

In this paper, a new way to think about, and to construct, pairwise as well as multiple alignments of DNA and protein sequences is proposed. Rather than forcing alignments to either align single residues or to introduce gaps by defining an alignment as a path running right from the source up to the sink in the associated dot-matrix diagram, we propose to consider alignments as consistent equivalence relations defined on the set of all positions occurring in all sequences under consideration. We also propose constructing alignments from whole segments exhibiting highly significant overall similarity rather than by aligning individual residues. Consequently, we present an alignment algorithm that (i) is based on segment-to-segment comparison instead of the commonly used residue-to-residue comparison and which (ii) avoids the well-known difficulties concerning the choice of appropriate gap penalties: gaps are not treated explicity, but remain as those parts of the sequences that do not belong to any of the aligned segments. Finally, we discuss the application of our algorithm to two test examples and compare it with commonly used alignment methods. As a first example, we aligned a set of 11 DNA sequences coding for functional helix-loop-helix proteins. Though the sequences show only low overall similarity, our program correctly aligned all of the 11 functional sites, which was a unique result among the methods tested. As a by-product, the reading frames of the sequences were identified. Next, we aligned a set of ribonuclease H proteins and compared our results with alignments produced by other programs as reported by McClure et al. [McClure, M. A., Vasi, T. K. & Fitch, W. M. (1994) Mol. Biol. Evol. 11, 571-592]. Our program was one of the best scoring programs. However, in contrast to other methods, our protein alignments are independent of user-defined parameters.

Scores for sequence searches and alignments

Every sequence comparison method requires a set of scores. For aligning protein sequences, substitution scores are based on models of amino acid conservation and properties, and matrices of these scores have substantially improved in recent years. Position-specific scoring matrices provide representations of sequence families that are capable of detecting subtle similarities. Comprehensive evaluations can effectively guide the choice of scores for sequence alignment and searching applications, including those that aid in the prediction of protein structures.

A non-local gap-penalty for profile alignment

The length of an alignment of biological sequences is typically longer than the mean length of its component sequences. (This arises from the insertion of gaps in the alignment.) When such an alignment is used as a profile for the alignment of further sequences (or profiles), it will have a bias toward additional sequences that match the length of the profile, rather than the mean length of sequences in the profile, as the alignment of these will entail fewer (or smaller) insertions (so avoiding gap-penalties). An algorithm is described to correct this bias that entails monitoring the correspondence, for every pair of positions, of the mean separations in both profiles as they are aligned. The correction was incorporated into a standard dynamic programming algorithm through a modification of the gap-penalty, but, unlike other approaches, this modification is not local and takes into consideration the overall alignment of the sequences. This implies that the algorithm cannot guarantee to find the optimal alignment, but tests suggest that close approximations are obtained. The method was tested on protein families by measuring the area in the parameter space of the phase containing the correct multiple alignment. No improvement (increase in phase area) was found with a family that required few gaps to be aligned correctly. However, for highly gapped alignments, a 50% increase in area was obtained with one family and the correct alignment was found for another that could not be aligned with the unbiased method.

An investigation of conservation-biased gap-penalties for multiple protein sequence alignment

Sequence conservation in a multiple sequence alignment (or profile) is often used to influence the alignment of further sequences onto the profile. Most methods, however, have considered only the opening of a gap at a single point and not what is contained in the inserted segment of one sequence (or profile) or what terminates the 'broken' ends of the other. An alignment algorithm is described that incorporates these aspects and the relative importance of the contribution from the insert and the 'broken' ends has been assessed. The approach was tested on families of very remotely related sequences using a novel protocol that was developed to quantify both the stability and generality of the solution.