IDEAS home Printed from https://ideas.repec.org/a/plo/pcbi00/1004936.html
   My bibliography  Save this article

Bayesian Top-Down Protein Sequence Alignment with Inferred Position-Specific Gap Penalties

Author

Listed:
  • Andrew F Neuwald
  • Stephen F Altschul

Abstract

We describe a Bayesian Markov chain Monte Carlo (MCMC) sampler for protein multiple sequence alignment (MSA) that, as implemented in the program GISMO and applied to large numbers of diverse sequences, is more accurate than the popular MSA programs MUSCLE, MAFFT, Clustal-Ω and Kalign. Features of GISMO central to its performance are: (i) It employs a “top-down” strategy with a favorable asymptotic time complexity that first identifies regions generally shared by all the input sequences, and then realigns closely related subgroups in tandem. (ii) It infers position-specific gap penalties that favor insertions or deletions (indels) within each sequence at alignment positions in which indels are invoked in other sequences. This favors the placement of insertions between conserved blocks, which can be understood as making up the proteins’ structural core. (iii) It uses a Bayesian statistical measure of alignment quality based on the minimum description length principle and on Dirichlet mixture priors. Consequently, GISMO aligns sequence regions only when statistically justified. This is unlike methods based on the ad hoc, but widely used, sum-of-the-pairs scoring system, which will align random sequences. (iv) It defines a system for exploring alignment space that provides natural avenues for further experimentation through the development of new sampling strategies for more efficiently escaping from suboptimal traps. GISMO’s superior performance is illustrated using 408 protein sets containing, on average, 235 sequences. These sets correspond to NCBI Conserved Domain Database alignments, which have been manually curated in the light of available crystal structures, and thus provide a means to assess alignment accuracy. GISMO fills a different niche than other MSA programs, namely identifying and aligning a conserved domain present within a large, diverse set of full length sequences. The GISMO program is available at http://gismo.igs.umaryland.edu/.Author Summary: Existing multiple alignment programs typically utilize (i) bottom-up progressive strategies, which require the time-consuming alignment of each pair of input sequences, (ii) ad hoc measures of alignment quality, and (iii) pre-specified, uniformly-defined gap penalties. Here we describe an alternative strategy that first provisionally aligns regions generally shared by all the input sequences, and then refines this alignment by iteratively realigning correlated sequences in tandem. It infers position-specific gap penalties directly from the evolving alignment. It avoids suboptimal traps by stochastically traversing the complex, correlated space of alignments using a statistically rigorous measure of alignment quality. For large sequence sets, this approach offers clear advantages in alignment accuracy over the most popular programs currently available.

Suggested Citation

  • Andrew F Neuwald & Stephen F Altschul, 2016. "Bayesian Top-Down Protein Sequence Alignment with Inferred Position-Specific Gap Penalties," PLOS Computational Biology, Public Library of Science, vol. 12(5), pages 1-21, May.
  • Handle: RePEc:plo:pcbi00:1004936
    DOI: 10.1371/journal.pcbi.1004936
    as

    Download full text from publisher

    File URL: https://journals.plos.org/ploscompbiol/article?id=10.1371/journal.pcbi.1004936
    Download Restriction: no

    File URL: https://journals.plos.org/ploscompbiol/article/file?id=10.1371/journal.pcbi.1004936&type=printable
    Download Restriction: no

    File URL: https://libkey.io/10.1371/journal.pcbi.1004936?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Stephen F Altschul & John C Wootton & Elena Zaslavsky & Yi-Kuo Yu, 2010. "The Construction and Use of Log-Odds Substitution Scores for Multiple Sequence Alignment," PLOS Computational Biology, Public Library of Science, vol. 6(7), pages 1-17, July.
    2. Peter D. Grünwald, 2007. "The Minimum Description Length Principle," MIT Press Books, The MIT Press, edition 1, volume 1, number 0262072815, April.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Gerry Q Tonkin-Hill & Leily Trianty & Rintis Noviyanti & Hanh H T Nguyen & Boni F Sebayang & Daniel A Lampah & Jutta Marfurt & Simon A Cobbold & Janavi S Rambhatla & Malcolm J McConville & Stephen J R, 2018. "The Plasmodium falciparum transcriptome in severe malaria reveals altered expression of genes involved in important processes including surface antigen–encoding var genes," PLOS Biology, Public Library of Science, vol. 16(3), pages 1-40, March.
    2. Andrew F Neuwald & Stephen F Altschul, 2016. "Inference of Functionally-Relevant N-acetyltransferase Residues Based on Statistical Correlations," PLOS Computational Biology, Public Library of Science, vol. 12(12), pages 1-30, December.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Lei, Da & Cheng, Long & Wang, Pengfei & Chen, Xuewu & Zhang, Lin, 2024. "Identifying service bottlenecks in public bikesharing flow networks," Journal of Transport Geography, Elsevier, vol. 116(C).
    2. Neuwald Andrew F., 2014. "Protein domain hierarchy Gibbs sampling strategies," Statistical Applications in Genetics and Molecular Biology, De Gruyter, vol. 13(4), pages 497-517, August.
    3. Alejandro Ochoa & John D Storey & Manuel Llinás & Mona Singh, 2015. "Beyond the E-Value: Stratified Statistics for Protein Domain Prediction," PLOS Computational Biology, Public Library of Science, vol. 11(11), pages 1-21, November.
    4. Das Ujjwal & Ebrahimi Nader, 2018. "A New Method For Covariate Selection In Cox Model," Statistics in Transition New Series, Statistics Poland, vol. 19(2), pages 297-314, June.
    5. Zelaya Mendizábal, Valentina & Boullé, Marc & Rossi, Fabrice, 2023. "Fast and fully-automated histograms for large-scale data sets," Computational Statistics & Data Analysis, Elsevier, vol. 180(C).
    6. Ujjwal Das & Nader Ebrahimi, 2018. "A New Method For Covariate Selection In Cox Model," Statistics in Transition New Series, Polish Statistical Association, vol. 19(2), pages 297-314, June.
    7. Andrew F Neuwald & Stephen F Altschul, 2016. "Inference of Functionally-Relevant N-acetyltransferase Residues Based on Statistical Correlations," PLOS Computational Biology, Public Library of Science, vol. 12(12), pages 1-30, December.
    8. Yurij L. Katchanov & Natalia A. Shmatko, 2014. "Complexity-Based Modeling of Scientific Capital: An Outline of Mathematical Theory," International Journal of Mathematics and Mathematical Sciences, Hindawi, vol. 2014, pages 1-10, October.
    9. Kris V Parag & Christl A Donnelly, 2020. "Using information theory to optimise epidemic models for real-time prediction and estimation," PLOS Computational Biology, Public Library of Science, vol. 16(7), pages 1-20, July.
    10. Mullins, Joshua & Mahadevan, Sankaran, 2014. "Variable-fidelity model selection for stochastic simulation," Reliability Engineering and System Safety, Elsevier, vol. 131(C), pages 40-52.
    11. K. Vela Velupillai, 2010. "The Algorithmic Revolution in the Social Sciences: Mathematical Economics, Game Theory and Statistical Inference," ASSRU Discussion Papers 1005, ASSRU - Algorithmic Social Science Research Unit.
    12. Alperen Bektas & Valentino Piana & René Schumann, 2021. "A meso-level empirical validation approach for agent-based computational economic models drawing on micro-data: a use case with a mobility mode-choice model," SN Business & Economics, Springer, vol. 1(6), pages 1-25, June.
    13. Neuwald Andrew F., 2011. "Surveying the Manifold Divergence of an Entire Protein Class for Statistical Clues to Underlying Biochemical Mechanisms," Statistical Applications in Genetics and Molecular Biology, De Gruyter, vol. 10(1), pages 1-30, August.
    14. Löcherbach, Eva & Orlandi, Enza, 2011. "Neighborhood radius estimation for variable-neighborhood random fields," Stochastic Processes and their Applications, Elsevier, vol. 121(9), pages 2151-2185, September.
    15. Vittoria Bruni & Michela Tartaglione & Domenico Vitulano, 2020. "A Signal Complexity-Based Approach for AM–FM Signal Modes Counting," Mathematics, MDPI, vol. 8(12), pages 1-33, December.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:plo:pcbi00:1004936. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: ploscompbiol (email available below). General contact details of provider: https://journals.plos.org/ploscompbiol/ .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.