The Construction and Use of Log-Odds Substitution Scores for Multiple Sequence Alignment
[['Protein and DNA sequence alignment is a fundamental tool of computational molecular biology .', 'It is used for functional prediction , genome annotation , the discovery of functional elements and motifs , homology-based structure prediction and modeling , phylogenetic reconstruction , and in numerous other applications .', 'The effectiveness of alignment programs depends crucially upon the scoring systems they employ to evaluate possible alignments .', 'For pairwise alignments , scores typically are defined as the sum of “substitution scores” for aligning pairs of letters ( amino acids or nucleotides ) , and “gap scores” for aligning letters in one sequence with null characters between letters in the other .', 'Substitution and gap scores may be generalized to multiple alignments , i . e . those involving three or more sequences .', 'Most useful local pairwise alignment algorithms allow gaps and explicitly assign them scores [1]–[4] .', 'However , many local multiple alignment algorithms do not allow gaps , or allow them only implicitly as spacers between distinct ungapped alignment blocks .', 'Indeed the alignments recorded in some protein family databases are explicitly constructed with ungapped alignment blocks separated by variable length spacers [5] , and it has been argued that this formalism corresponds well to the observed relationships imposed by protein structure [6] .', 'Short ungapped blocks are also used in the DNA context , to represent , for example , transcription factor binding sites .', 'Many pairwise substitution scores have been developed for protein [7]–[20] and DNA [21] , [22] sequence comparison , and a statistical theory for substitution scores has been developed for local alignments without gaps [23] , [24] .', 'It is not trivial to generalize pairwise scoring systems to multiple alignments , and the following four principal approaches have been proposed to this long-standing problem: A ) Tree scores .', 'An evolutionary tree can be defined relating the sequences in question , with each sequence residing at one leaf of the tree .', 'By reconstructing letters at the internal nodes of the tree , the score for an aligned column of letters is defined as the sum of pairwise substitution scores for all edges of the tree [25] , [26] .', 'B ) Star scores .', 'As a special case of tree-scores , a single “consensus” letter can be defined for an alignment column .', 'The column score is defined as the sum of pairwise scores for the consensus letter to each letter in the column .', 'The tree in question reduces to a star , with the consensus at the central node .', 'C ) Sum-of-the-Pairs or SP scores .', 'A column score can be constructed as the sum of substitution scores for all pairs of letters in the column [27] , [28] .', 'D ) Entropy scores .', 'Scores can be based on the entropy of the letter frequencies observed in a column [29]; these scores have become particularly popular for DNA alignments .', 'All these approaches are open to refinement , for example by weighting the pairwise scores of the sequences involved .', 'All reasonable substitution scores for pairwise local alignment are implicitly log-odds scores [23] , [30] , which compare the probabilities of aligning two letters under models of relatedness and non-relatedness , and the most popular are explicitly so constructed [7] , [8] , [14] .', 'We argue that multiple alignment column scores should be similarly constructed , based upon explicit target frequency predictions for columns from accurate alignments of related sequences .', 'For this purpose , we propose , the method with the strongest theoretical foundation relies upon the specification of a Bayesian prior , over the space of multinomial distributions for describing alignment columns representing true biological relationships [31] , [32] .', 'We call column scores based on such a formalism “Bayesian Integral Log-odds” or BILD scores .', 'Although these scores are implicit in earlier work , their full generality and utility has not been recognized .', 'They may be calculated efficiently , and may be generalized to allow for the differential weighting of sequences in a multiple alignment .', 'We also consider an alternative approach that allows log-odds column scores to be derived from any pairwise substitution matrix .', 'Given their form , multiple alignment log-odds scores can be used directly to define the proper extent of multiple alignment blocks , and to derive natural scores for profile-profile comparison .', 'We show that they also arise from the perspective of the Minimum Description Length Principle [33] , which allows them to be combined naturally with other information theoretic measures .', 'Other direct applications are specifying when a sequence should be included in a multiple alignment at all , and when an alignment of many related sequences is better split into several alignments each involving fewer sequences .', 'Efficient methods for calculating BILD scores allow them to be incorporated into Gibbs sampling algorithms for ungapped local multiple alignment .', 'Most practical protein applications , however , require provisions for gaps .', 'We describe two methods for extending an ungapped local multiple alignment produced by the Gibbs sampling strategy to a gapped alignment , the first using asymmetric affine gap costs , and the second hidden Markov models .', 'In the latter , column BILD scores inform the construction of position-specific gap costs , and yield gapped alignments in greater conformity with considerations of protein structure .', 'We illustrate the applications of the programs by using them to uncover previously undescribed Api-AP2 domains of Toxoplasma gondii and Plasmodium falciparum .', 'Multiple sequence alignment comprises a diverse set of problems and approaches .', 'Many sophisticated statistical inference techniques have been applied to the multiple alignment problem and to the related problem of phylogenetic reconstruction , e . g . [34]–[37] .', 'It is not our purpose here to develop a new multiple alignment program .', 'Rather , we seek only to argue that the “substitution scores” for multiple alignment columns which lie at the core of most multiple alignment methods can in many cases be improved .', 'Although many statistical alignment methods are Bayesian-based , the BILD scores directly implied by Bayesian reasoning have been heretofore unrecognized .'], ['Log-odds pairwise substitution scores can be written .', 'Here , is the frequency with which residues and correspond in accurate alignments of related sequences , and is the background probability with which residue occurs .', 'The base of the logarithm is arbitrary , and merely defines a scale for the scoring system .', 'We henceforth assume that unless the natural logarithm is specified , all logarithms are base , and the resulting scores are therefore in the units of bits [30] .', 'Note that no target frequencies are uniquely optimal for pairwise sequence alignment , because different are appropriate for comparing sequences diverged by different amounts of evolution [7] , [8] , [13] , [30] .', 'This perception gives rise to families of substitution matrices , such as the PAM [7] , [8] and BLOSUM [14] series for protein comparison .', 'To generalize log-odds scores to multiple alignments , we first develop some notation .', 'We consider the alphabet from which the letters in our sequences are drawn to consist of elements , which for convenience we represent by the numbers 1 through .', 'An ungapped column from a multiple alignment of sequences is a vector , each of whose components through takes on a value in .', 'In essence , the log-odds approach compares two theories , one in which all the letters aligned are related or homologous , and the other in which none are .', 'Each theory implies a probability for observing any given set of data .', 'For the alignment column , we define as the probability of observing the data under the assumption of relatedness , and under the assumption of non-relatedness .', 'Then the log-odds score for this column is defined as ( 1 ) Assuming background probabilities through for the various letters , is given simply by ( 2 ) We will consider one primary strategy for deriving .', 'As with pairwise scores , all sets of multiple alignment column scores with negative expected value are implicitly log-odds scores [23] , [30] .', 'However , unless their values for are explicitly constructed in a sensible way , log-odds scores are unlikely to perform well in the applications suggested below .', 'For alignments of more than two sequences , there are of course other possibilities than for all or none of the sequences to be related .', 'However , as we will describe below , scores of the form of equation ( 1 ) can be applied to the comparison of sequences where only a subset are related , by adding indicator variables to include or exclude sequences .', 'Log-odds scores for alignment columns immediately suggest substitution scores for aligning two different columns of letters .', 'Specifically , letting be the concatenation of the vectors and , define ( 3 ) These column-column alignment scores may be used consistently in progressive alignment algorithms , which proceed by aligning the most closely related sequences first [38] , [39] , although as will be discussed below problems may arise in the definition of gap scores .', 'They may also be used for profile-profile alignment , a topic of considerable recent interest [40]–[48] .', 'For multiple alignments , perhaps the best approach to defining and calculating is a Bayesian one [31] , [32] .', '( An alternative approach , based on pairwise scoring matrices , is described in Text S1 . )', 'Assume that the letters in a specific column from an accurate alignment of related sequences are generated independently , but with probabilities through that in general differ from the background probabilities .', 'Assume further that it is possible to assign a prior probability distribution to the multinomial distributions associated with columns of related letters .', 'This prior can be derived from a detailed study of related protein or DNA sequences .', 'Although the data associated with a specific column generally have no temporal or other privileged order , assume for convenience that they are observed sequentially , in the order to .', "Then we may apply Bayes' theorem to transform the prior distribution to a posterior , after the observation of .", 'More generally , each subsequent observation can be seen to transform the prior into a posterior distribution .', 'We may then use the chain rule to write ( 4 ) The individual terms in this product may be calculated by integrating over all possible multinomial distributions : ( 5 ) Finally , combining equations ( 1 ) , ( 2 ) and ( 4 ) yields ( 6 ) We call scores defined in this way Bayesian Integral Log-odds or BILD scores .', 'They can be understood simply as the sum of log-odds scores for the individual letters observed in a column , with the “target frequency” for each letter calculated based upon the prior distribution , and the “previously observed” letters through .', "Even though , by this formula , the log-odds score for a letter varies with its position in the column , the total column score is nevertheless invariant under permutation of the column's letters .", 'BILD scores have some conceptual connections to star- and entropy-based multiple alignment scoring systems .', 'The simplest generalization of star scores imposes a prior probability distribution on the consensus letter , but still assumes a probabilistic pairwise substitution model .', 'As we describe in Text S1 , this yields a class of log-odds scores we call MELD scores .', 'BILD scores arise , in contrast , by thinking of the “consensus” not as an ancestral letter , but rather as a generative probabilistic model , and by integrating over a prior distribution placed on this model .', 'Given observed and background letter distributions and , entropy scores have been defined variously , and conceptually distinctly , as:', 'i ) , the entropy difference between and ;', 'ii ) , the entropy difference between a uniform distribution on letters and ; and', 'iii ) , the relative entropy of and .', 'Definitions', 'i ) and', 'ii ) differ only by a constant .', 'One may refine any of these definitions by taking to be a posterior letter distribution , derived from a prior and a set of observations .', 'Both BILD and entropy-based scores can be viewed as the sum of scores derived from the probabilities for individual observations .', 'The central distinction is that BILD scores estimate the probability for a given such observation using only “earlier” ones , whereas entropy scores estimate this probability using the complete collection of observations .', 'Although the definition of BILD scores is valid for any prior distribution one wishes to specify , it is in general impractical to calculate the , or the integral in equation ( 5 ) , except when takes the form of a Dirichlet distribution [49] , or a mixture of a finite number of Dirichlet distributions [31] , [32] .', 'In this case , as described below , all the are also Dirichlet distributions , or Dirichlet mixtures , and is easily calculated .', 'Therefore , for mathematical as opposed to biological reasons , we always assume that BILD scores are defined using a Dirichlet or Dirichlet mixture prior .', 'The family of Dirichlet mixtures , however , is rich enough that it can capture well much relevant prior knowledge concerning relationships among the various amino acids or nucleotides .', 'We review here the essentials of Dirichlet distributions .', 'A multinomial distribution on letters is specified by an -dimensional vector , within the simplex defined by , and .', 'The requirement that the sum to 1 renders the space of multinomials dimensional .', 'A Dirichlet distribution , defined over this space , is parametrized by an -dimensional vector with all positive .', 'We shall sometimes refer to such a distribution by its parameters , and we define as the sum of the .', 'The Dirichlet distribution is given by the probability density function ( 7 ) where the normalizing scalar ensures that integrating over its domain yields 1 .', 'Here , is the Gamma function , and for positive integral .', 'The uniform density is a special case that arises when all the are 1 .', 'Dirichlet distributions have two convenient properties .', 'First , the expected frequency of letter implied by is .', "Second , the posterior distribution yielded by Bayes' theorem , after the observation of the letter , is a Dirichlet distribution with , but with all other parameters equal to those of .", 'To illustrate how to calculate BILD scores using these properties , consider the case of DNA comparison ( with the numbers 1 through 4 identified respectively with the nucleotides A , C , G and T ) , with uniform background probabilities , and a Dirichlet prior given by the parameter vector ( 1 , 1 , 1 , 1 ) .', 'By equation ( 4 ) , the target frequency associated with the alignment column “AATC” is given by .', 'Thus the score for the column is bits .', 'In contrast , for the column “AAAC” , , and the score for this column is bits .', 'The essence of a Dirichlet distribution is perhaps best understood through the alternative parametrization ( ; ) , where , and .', 'Because the must sum to 1 , there are still only independent parameters .', 'The vector describes the center of mass of the distribution , while indicates how concentrated the distribution is about this point .', 'Large values of correspond to distributions with most of their mass near , whereas values of near 0 correspond to distributions with most of their mass near the boundaries of the simplex .', 'It is frequently sensible , although not necessary , to choose a prior whose is identical to the background frequencies .', 'In this case , , and the first summand in equation ( 6 ) is always 0 .', 'In other words , no letter in a column , considered in isolation , carries any information as to whether the column represents a true biological relationship .', 'Single Dirichlet distributions frequently are adequate for capturing prior knowledge concerning “true” alignment columns of related DNA sequences , but this is not the case for proteins .', 'Most simply , distinct regions of multinomial space , representing different collections of amino acids , should have high prior probabilities .', 'In order to address the deficiency of single Dirichlet distributions , Brown [31] proposed the use of Dirichlet mixture priors .', 'A Dirichlet mixture is simply the weighted sum of distinct Dirichlet distributions .', 'It is specified by positive “mixture parameters” through that sum to 1 , and a set of standard Dirichlet parameters , through , for each of the component Dirichlet distributions .', '( It will be useful later to define as . )', 'In all , because of the restriction on the sum of the , a Dirichlet mixture has independent parameters .', 'The Dirichlet components of a mixture generally are thought of as describing various types of positions ( e . g . hydrophobic , charged , aromatic ) typically found in proteins .', "Bayes' theorem implies that , given a -component Dirichlet mixture as a prior , the posterior distribution after the observation of a single letter is also a -component Dirichlet mixture [31] , [32] .", 'Brown [31] proposed Dirichlet mixture priors in the context of deriving “substitution” scores for aligning amino acids to columns from a multiple protein sequence alignment .', 'This restricted context can be understood as comprehending a single summand from equation ( 6 ) .', "BILD scores extend Brown 's sequence-profile alignment scores to comprehensive scores for multiple alignment columns . Generalizing the development above , we describe here how to calculate the probability of a particular observation given a Dirichlet mixture prior , and how to calculate the posterior resulting from this observation . First , given a Dirichlet mixture , with parameters and , the probability of observing letter is given simply by ( 8 ) which follows directly from the definition of Dirichlet mixtures , and the result for single Dirichlet distributions . Second , given the observation of letter , and a Dirichlet mixture prior parametrized as above , the parameters and of the posterior distribution may be calculated as follows: ( 9 ) In short , first multiply the mixture parameters by the Bayesian factors and normalize , and then add 1 to each . Mathematics establishing the validity of this procedure appears in [32] . Their development is more complex than we require here , because we modify the Dirichlet mixture parameters only one observation at a time . We note that given the and , it is simple to invert procedure ( 9 ) to determine the and . This is useful for applications such as the Gibbs sampling algorithm discussed below . Many multiple alignment problems involve subsets of sequences that are much more closely related to one another than to the other sequences being considered , and this may yield suboptimal results , because a large number of closely related sequences can “outvote” a few more divergent sequences . One remedy has been to assign each sequence a numerical weight , with closely related sequences down-weighted [50]–[61] . Also , subsumed in such weights may be the recognition that the total number of effective observations represented by an alignment column may be smaller than the number of sequences it comprehends [4] , [62] , [63] . Thus , for certain applications it may be desirable to generalize BILD scores to weighted sequences . To do so , we need to define the concept of the probability of a “fractional observation” of a letter , and describe as well how a posterior distribution is calculated after such a fractional observation . Arguments supporting how this may be done can be extracted from the mathematical development in [32] . Both equation ( 8 ) and the first step of procedure ( 9 ) involve multiplication by the factors . For the fraction of an observation of letter , these factors must be replaced by the alternative factors ( 10 ) Also , in the last step of procedure ( 9 ) , the quantity rather than 1 must be added to each . The factors are identical to the original factors when , and all approach 1 as approaches 0 , as some reflection shows they must . Finally , note that equation ( 10 ) may be applied to as well as , and may be useful even when all observations are unitary . Thus , by aggregating observations , the BILD score for a column containing unique letters may be calculated with summands , rather than the summands of equation ( 6 ) . For a single Dirichlet prior , reduces to the simple formula ( 11 ) where is the count of letter , and is the total count of all residues . Only the numerator inside the product varies from column to column within an alignment , yielding further efficiency for calculation . Only the research team that first proposed Dirichlet mixtures for protein sequence comparison has derived , from analyses of large protein alignment collections , sets of Dirichlet mixture prior parameters [31] , [32] . Twelve such sets , involving various numbers of Dirichlet components , can currently be found at http://compbio . soe . ucsc . edu/dirichlets/index . html . We list five of these in Table 1 , which we refer to as through . Proteins diverged by different degrees of evolutionary change are best studied using pairwise substitution matrices with different relative entropies [30] , and the analogous claim should hold for Dirichlet mixture priors . A Dirichlet mixture prior implies a background amino acid frequency distribution , as well as a symmetric pairwise substitution matrix , by means of the formula . The relative entropies of the substitution matrices implicit in the priors through range from 1 . 44 bits , roughly equivalent to that of the PAM-80 matrix [7] , [8] , which is appropriate for fairly close evolutionary relationships , to 0 . 18 bits , roughly equivalent to that of the PAM-360 matrix , which is appropriate only for extremely distant relationships ( Table 1 ) . As well as , one may calculate the mean relative entropy of the multinomial distributions described by a Dirichlet mixture prior to the background frequencies ( see Text S2 ) . For to , ranges from to bits ( Table 1 ) . That has a much greater value than indicates that on average much more information is available per position from an accurate multiple alignment of many related sequences than from a single sequence . We note that , in lieu of using different priors , the effective relative entropy of a particular Dirichlet mixture may be tuned by scaling the weights of the sequences to which it is applied [43] . Standard pairwise substitution matrices are constructed from sets of proteins with certain background amino acid frequencies , and are non-optimal for the comparison of proteins with compositions that differ greatly from [64] . Similarly , a Dirichlet mixture prior has an implicit background amino acid composition , and should not be optimal when applied to proteins with compositions that differ greatly from . It is possible to adjust standard matrices for use with non-standard compositions [64] , [65] , and we will discuss elsewhere an analogous strategy that can be applied to adjust Dirichlet mixture priors . Single Dirichlet priors may be appropriate for DNA sequence comparison . The uniform density , arising when all ( ) , has frequently been advocated in the absence of prior knowledge , and “Jeffreys' prior” [66] , which is uninformative in a deeper sense , corresponds to all ( ) [33] .", 'When specific prior knowledge concerning an application domain is available , however , there is generally not a strong argument for using uninformative priors .', 'For related DNA sequences , the columns of accurate alignments are sometimes dominated by one or two nucleotides , suggesting that all should be smaller than .', 'Furthermore , it usually makes sense for the to be proportional to the background frequencies .', 'If this is stipulated , the specification of a Dirichlet prior reduces to the specification of .', 'Assuming a uniform nucleotide composition , the values of and implied by from to are given in Table 2 .', 'An empirical study of transcription factor binding sites [67] concludes that , at least for the analysis of such sites , should be or lower .', 'A direct application of multiple alignment log-odds scores is to determining local alignment width .', 'As formulated by Smith and Waterman [1] , an optimal local alignment is one that maximizes an alignment score but is of arbitrary width .', 'Such scores should fall on the log side of the “log-linear phase transition” [68] , which implies that for ungapped local alignments , substitution scores must be of log-odds form [23] , [30] .', 'Equation ( 1 ) explicitly generalizes pairwise log-odds scores to the multiple alignment case .', 'They are positive for some alignment columns , negative for others , and must have negative expected value .', 'Therefore it is appropriate to define an optimal ungapped multiple alignment as one with maximal aggregate log-odds score .', 'This immediately allows one to define the proper width or extent of an ungapped multiple DNA or protein alignment , without resorting to the ad hoc principles frequently required for other scoring systems [69] .', 'Although the Smith-Waterman algorithm can be applied to optimize log-odds-scored local multiple alignments , it is too slow for most purposes .', 'Nevertheless , once relative offsets have been fixed for a set of sequences , it is trivial to determine an optimal ungapped local multiple alignment along the single implied diagonal .', 'The ungapped local multiple alignment problem may be formulated as seeking segments of common width within multiple DNA or protein sequences that , when aligned , optimize a defined objective function .', 'We take this function here to be the aggregate log-odds score for the aligned columns .', 'One way to approach this optimization is by means of a Gibbs sampling strategy , as described by Lawrence [69] .', 'Log-odds scores can be used to adjust dynamically , by applying the Smith-Waterman algorithm to the diagonal implied by a provisional alignment , without the need for an arbitrary parameter or an ad hoc optimization .', 'They may also be used to determine dynamically whether or not a sequence should participate in the multiple alignment at all , for which purpose it is useful first to consider log-odds scores from the perspective of the Minimum Description Length Principle .', 'The Minimum Description Length ( MDL ) Principle provides a criterion for choosing among alternative theories for describing a set of data [33] , [49] .', 'To simplify greatly , it suggests that given a set of alternative theories to describe a set of data , that theory should be chosen which minimizes , defined as the sum of , the description length of the theory , and , the description length of the data given the theory .', 'By convention , description lengths are measured in bits .', 'From information theory [70] , the information associated with an event of probability is bits .', 'Focusing on actual encoding schemes for probabilistic events can unduly complicate MDL analyses .', 'Accordingly , we here follow the approach of section 3 . 2 . 2 of [33] , in which description lengths are allowed to be non-integral , and are identified with negative log probabilities .', 'Thus , if the data can be described probabilistically , .', 'The length of the theory is defined as the number of bits needed to specify the free parameters of , i . e . those that are fitted to the data [33] .', 'For local multiple alignment , the theory that the input sequences are unrelated has only the background probabilities as parameters , whose description length we will call .', 'The data is comprised of sequences , with lengths through , and consisting of the letters .', 'Then .', 'The theory states that segments of width beginning at positions within the various sequences are related , and that the probability of the data within each column of the implied alignment is ; the probability of the rest of the data may be described with the background frequencies .', 'The free parameters are , the vector of starting positions , and .', 'Each may take on one of values , so its description length is approximately , if is not too large compared to .', 'Thus , we have , where is the description length of .', '( If all feasible widths are taken to be equally likely , is just . Other encodings have grow slowly with [33] , [49] . )', 'It is apparent that , where the latter sum is taken only over those letters not participating in the local multiple alignment .', 'Everything simplifies when we consider the difference in the total description lengths of the two theories: ( 12 ) where is simply the log-odds score for the implied alignment .', 'In other words , is preferred whenever exceeds .', 'As described in Text S3 , this prescription is related to the statistical theory for ungapped local alignments [23] .', 'To allow one or more sequences to be excluded from the multiple alignment , we consider not 2 , but theories , distinguished by binary indices , which take on the value 1 to indicate that sequence participates in the alignment , and otherwise .', 'These theories need not be a priori equally likely; if necessary , for from 1 to we can specify prior probabilities that sequence contains a segment related to segments in the other sequences .', 'Let us consider the difference in the description lengths of two theories , and , that differ only in their index .', 'Theory incurs the cost for the prior probability that , and also requires describing the location of the related segment , which costs bits .', 'In contrast , theory incurs only the cost , so costs more bits to describe than .', 'Thus , for to be preferred , the log-odds score of the multiple alignment must increase by at least when the segment from the th sequence is added .', 'If is close to 1 , can be negative , and is if .', 'In short , the greater the prior probability that a given sequence contains a relevant segment , the lower the score of such a segment need be for inclusion in the alignment .', 'The change in the log-odds score with the addition of a segment from the th sequence depends upon which other sequences , and which of their segments , participate in the alignment .', 'Consequently , the values of the indicator variables must be part of the larger optimization , and their selection can be readily incorporated into a Gibbs sampling algorithm .', 'The MDL Principle can also be extended to the case where a single sequence may contain more than one copy of a pattern , and , as previously described [62] , [71] , [72] and discussed in Text S4 , to the clustering of multiple alignments into subfamilies .', 'Although our central concern is to define a new type of multiple alignment substitution score , many important applications require the construction of gapped multiple alignments , and these generally entail scores for insertions and deletions .', 'Multiple alignment gap scores should be defined in a manner consistent with the substitution scores used [73] , so we will consider what type gap scores might fruitfully be paired with BILD scores .', 'Just as the log-odds perspective places pairwise substitution scores in a probabilistic framework [7] , [8] , [23] , [30] , so pairwise gap scores can be viewed as specifying probabilities for insertions and deletions within biologically accurate alignments [74]–[82] .', 'For pairwise alignments , “affine” gap scores , of the form for a gap of length [83]–[85] , are those most commonly used [3] , [4] , although more complex gap scores have frequently been proposed [86]–[89] .', 'When there is an essential asymmetry between the sequences being aligned , differing scores may be assigned to gaps within the two sequences .', 'Furthermore , when substitution and gap scores are properly integrated and both expressed in the units of bits , the two parameters of affine gap scores can be understood to specify jointly the average frequencies and lengths of gaps in the alignments sought [82] .', 'If gaps are to be introduced into the BILD score formalism , an immediate problem is which , if any , letters from individual sequences should be understood as insertions with respect to the “canonical” pattern 
['Introduction', 'Methods', 'Results', 'Discussion']
['Most pairwise and multiple sequence alignment programs seek alignments with optimal scores .', 'Central to defining such scores is selecting a set of substitution scores for aligned amino acids or nucleotides .', 'For local pairwise alignment , substitution scores are implicitly of log-odds form .', 'We now extend the log-odds formalism to multiple alignments , using Bayesian methods to construct “BILD” ( “Bayesian Integral Log-odds” ) substitution scores from prior distributions describing columns of related letters .', 'This approach has been used previously only to define scores for aligning individual sequences to sequence profiles , but it has much broader applicability .', 'We describe how to calculate BILD scores efficiently , and illustrate their uses in Gibbs sampling optimization procedures , gapped alignment , and the construction of hidden Markov model profiles .', 'BILD scores enable automated selection of optimal motif and domain model widths , and can inform the decision of whether to include a sequence in a multiple alignment , and the selection of insertion and deletion locations .', 'Other applications include the classification of related sequences into subfamilies , and the definition of profile-profile alignment scores .', 'Although a fully realized multiple alignment program must rely upon more than substitution scores , many existing multiple alignment programs can be modified to employ BILD scores .', 'We illustrate how simple BILD score based strategies can enhance the recognition of DNA binding domains , including the Api-AP2 domain in Toxoplasma gondii and Plasmodium falciparum .']
['Multiple sequence alignment is a fundamental tool of biological research , widely used to identify important regions of DNA or protein molecules , to infer their biological functions , to reconstruct ancestries , and in numerous other applications .', 'The effectiveness and accuracy of sequence comparison programs depends crucially upon the quality of the scoring systems they use to measure sequence similarity .', 'To compare pairs of DNA or protein sequences , the best strategy for constructing similarity measures has long been understood , but there has been a lack of consensus about how to measure similarity among multiple ( i . e . more than two ) sequences .', 'In this paper , we describe a natural generalization to multiple alignment of the accepted measure of pairwise similarity .', 'A large variety of methods that are used to compare and analyze DNA or protein molecules , or to model protein domain families , could be rendered more sensitive and precise by adopting this similarity measure .', 'We illustrate how our measure can enhance the recognition of important DNA binding domains .']
['computational biology/macromolecular sequence analysis', 'computational biology/protein homology detection', 'computational biology/sequence motif analysis', 'computational biology']