Lower bounds on multiple sequence alignment using exact 3-way alignment
Genre
Journal ArticleDate
2007-04-30Author
Colbourn, CJKumar, S
Subject
AlgorithmsBase Sequence
DNA
Molecular Sequence Data
Reproducibility of Results
Sensitivity and Specificity
Sequence Alignment
Sequence Analysis, DNA
Permanent link to this record
http://hdl.handle.net/20.500.12613/5623Metadata
Show full item recordDOI
10.1186/1471-2105-8-140Abstract
Background: Multiple sequence alignment is fundamental. Exponential growth in computation time appears to be inevitable when an optimal alignment is required for many sequences. Exact costs of optimum alignments are therefore rarely computed. Consequently much effort has been invested in algorithms for alignment that are heuristic, or explore a restricted class of solutions. These give an upper bound on the alignment cost, but it is equally important to determine the quality of the solution obtained. In the absence of an optimal alignment with which to compare, lower bounds may be calculated to assess the quality of the alignment. As more effort is invested in improving upper bounds (alignment algorithms), it is therefore important to improve lower bounds as well. Although numerous cost metrics can be used to determine the quality of an alignment, many are based on sum-of-pairs (SP) measures and their generalizations. Results: Two standard and two new methods are considered for using exact 2-way and 3-way alignments to compute lower bounds on total SP alignment cost; one new method fares well with respect to accuracy, while the other reduces the computation time. The first employs exhaustive computation of exact 3-way alignments, while the second employs an efficient heuristic to compute a much smaller number of exact 3-way alignments. Calculating all 3-way alignments exactly and computing their average improves lower bounds on sum of SP cost in v-way alignments. However judicious selection of a subset of all 3-way alignments can yield a further improvement with minimal additional effort. On the other hand, a simple heuristic to select a random subset of 3-way alignments (a random packing) yields accuracy comparable to averaging all 3-way alignments with substantially less computational effort. Conclusion: Calculation of lower bounds on SP cost (and thus the quality of an alignment) can be improved by employing a mixture of 3-way and 2-way alignments. © 2007 Colbourn and Kumar; licensee BioMed Central Ltd.Citation to related work
Springer Science and Business Media LLCHas part
BMC BioinformaticsADA compliance
For Americans with Disabilities Act (ADA) accommodation, including help with reading this content, please contact scholarshare@temple.eduScopus Count
Collections
Related items
Showing items related by title, author, creator and subject.
-
Evolutionary interactions between N-Linked glycosylation sites in the HIV-1 envelopeThe addition of asparagine (N)-linked polysaccharide chains (i.e., glycans) to the gp120 and gp41 glycoproteins of human immunodeficiency virus type 1 (HIV-1) envelope is not only required for correct protein folding, but also may provide protection against neutralizing antibodies as a "glycan shield." As a result, strong host-specific selection is frequently associated with codon positions where nonsynonymous substitutions can create or disrupt potential N-linked glycosylation sites (PNGSs). Moreover, empirical data suggest that the individual contribution of PNGSs to the neutralization sensitivity or infectivity of HIV-1 may be critically dependent on the presence or absence of other PNGSs in the envelope sequence. Here we evaluate how glycan-glycan interactions have shaped the evolution of HIV-1 envelope sequences by analyzing the distribution of PNGSs in a large-sequence alignment. Using a "covarion"-type phylogenetic model, we find that the rates at which individual PNGSs are gained or lost vary significantly over time, suggesting that the selective advantage of having a PNGS may depend on the presence or absence of other PNGSs in the sequence. Consequently, we identify specific interactions between PNGSs in the alignment using a new paired-character phylogenetic model of evolution, and a Bayesian graphical model. Despite the fundamental differences between these two methods, several interactions are jointly identified by both. Mapping these interactions onto a structural model of HIV-1 gp120 reveals that negative (exclusive) interactions occur significantly more often between colocalized glycans, while positive (inclusive) interactions are restricted to more distant glycans. Our results imply that the adaptive repertoire of alternative configurations in the HIV-1 glycan shield is limited by functional interactions between the N-linked glycans. This represents a potential vulnerability of rapidly evolving HIV-1 populations that may provide useful glycan-based targets for neutralizing antibodies. © 2007 Poon et al.
-
A cyclic nucleotide-gated channel mutation associated with canine daylight blindness provides insight into a role for the S2 segment Tri-Asp motif in channel biogenesisCone cyclic nucleotide-gated channels are tetramers formed by CNGA3 and CNGB3 subunits; CNGA3 subunits function as homotetrameric channels but CNGB3 exhibits channel function only when co-expressed with CNGA3. An aspartatic acid (Asp) to asparagine (Asn) missense mutation at position 262 in the canine CNGB3 (D262N) subunit results in loss of cone function (daylight blindness), suggesting an important role for this aspartic acid residue in channel biogenesis and/or function. Asp 262 is located in a conserved region of the second transmembrane segment containing three Asp residues designated the Tri-Asp motif. This motif is conserved in all CNG channels. Here we examine mutations in canine CNGA3 homomeric channels using a combination of experimental and computational approaches. Mutations of these conserved Asp residues result in the absence of nucleotide-activated currents in heterologous expression. A fluorescent tag on CNGA3 shows mislocalization of mutant channels. Co-expressing CNGB3 Tri-Asp mutants with wild type CNGA3 results in some functional channels, however, their electrophysiological characterization matches the properties of homomeric CNGA3 channels. This failure to record heteromeric currents suggests that Asp/Asn mutations affect heteromeric subunit assembly. A homology model of S1-S6 of the CNGA3 channel was generated and relaxed in a membrane using molecular dynamics simulations. The model predicts that the Tri-Asp motif is involved in non-specific salt bridge pairings with positive residues of S3/S4. We propose that the D262N mutation in dogs with CNGB3-day blindness results in the loss of these inter-helical interactions altering the electrostatic equilibrium within in the S1-S4 bundle. Because residues analogous to Tri-Asp in the voltage-gated Shaker potassium channel family were implicated in monomer folding, we hypothesize that destabilizing these electrostatic interactions impairs the monomer folding state in D262N mutant CNG channels during biogenesis. © 2014 Tanaka et al.
-
Characterization of hARD2, a processed hARD1 gene duplicate, encoding a human protein N-α-acetyltransferaseBackground: Protein acetylation is increasingly recognized as an important mechanism regulating a variety of cellular functions. Several human protein acetyltransferases have been characterized, most of them catalyzing ε-acetylation of histones and transcription factors. We recently described the human protein acetyltransferase hARD1 (human Arrest Defective 1). hARD1 interacts with NATH (N-Acetyl Transferase Human) forming a complex expressing protein N-terminal α-acetylation activity. Results: We here describe a human protein, hARD2, with 81 % sequence identity to hARD1. The gene encoding hARD2 most likely originates from a eutherian mammal specific retrotransposition event. hARD2 mRNA and protein are expressed in several human cell lines. Immunoprecipitation experiments show that hARD2 protein potentially interacts with NATH, suggesting that hARD2-NATH complexes may be responsible for protein N-α-acetylation in human cells. In NB4 cells undergoing retinoic acid mediated differentiation, the level of endogenous hARD1 and NATH protein decreases while the level of hARD2 protein is stable. Conclusion: A human protein N-α-acetyltransferase is herein described. ARD2 potentially complements the functions of ARD1, adding more flexibility and complexity to protein N-α-acetylation in human cells as compared to lower organisms which only have one ARD. © 2006 Arnesen et al; licensee BioMed Central Ltd.
