More Like this

1. WITCH-NG: efficient and accurate alignment of datasets with sequence length heterogeneity

   https://doi.org/10.1093/bioadv/vbad024  

   Liu, Baqiao ; Warnow, Tandy ; Lengauer, ed., Thomas ( March 2023 , Bioinformatics Advances)

   Multiple sequence alignment is a basic part of many bioinformatics pipelines, including in phylogeny estimation, prediction of structure for both RNAs and proteins, and metagenomic sequence analysis. Yet many sequence datasets exhibit substantial sequence length heterogeneity, both because of large insertions and deletions in the evolutionary history of the sequences and the inclusion of unassembled reads or incompletely assembled sequences in the input. A few methods have been developed that can be highly accurate in aligning datasets with sequence length heterogeneity, with UPP one of the first methods to achieve good accuracy, and WITCH a recent improvement on UPP for accuracy. In this article, we show how we can speed up WITCH. Our improvement includes replacing a critical step in WITCH (currently performed using a heuristic search) by a polynomial time exact algorithm using Smith–Waterman. Our new method, WITCH-NG (i.e. ‘next generation WITCH’) achieves the same accuracy but is substantially faster. WITCH-NG is available at https://github.com/RuneBlaze/WITCH-NG.

   The datasets used in this study are from prior publications and are freely available in public repositories, as indicated in the Supplementary Materials.

   Supplementary data are available at Bioinformatics Advances online.

    

   more » « less
2. mebipred : identifying metal-binding potential in protein sequence

   https://doi.org/10.1093/bioinformatics/btac358  

   Aptekmann, A. A. ; Buongiorno, J. ; Giovannelli, D. ; Glamoclija, M. ; Ferreiro, D. U. ; Bromberg, Y. ; Cowen, ed., Lenore ( May 2022 , Bioinformatics)

   metal-binding proteins have a central role in maintaining life processes. Nearly one-third of known protein structures contain metal ions that are used for a variety of needs, such as catalysis, DNA/RNA binding, protein structure stability, etc. Identifying metal-binding proteins is thus crucial for understanding the mechanisms of cellular activity. However, experimental annotation of protein metal-binding potential is severely lacking, while computational techniques are often imprecise and of limited applicability.

   we developed a novel machine learning-based method, mebipred, for identifying metal-binding proteins from sequence-derived features. This method is over 80% accurate in recognizing proteins that bind metal ion-containing ligands; the specific identity of 11 ubiquitously present metal ions can also be annotated. mebipred is reference-free, i.e. no sequence alignments are involved, and is thus faster than alignment-based methods; it is also more accurate than other sequence-based prediction methods. Additionally, mebipred can identify protein metal-binding capabilities from short sequence stretches, e.g. translated sequencing reads, and, thus, may be useful for the annotation of metal requirements of metagenomic samples. We performed an analysis of available microbiome data and found that ocean, hot spring sediments and soil microbiomes use a more diverse set of metals than human host-related ones. For human microbiomes, physiological conditions explain the observed metal preferences. Similarly, subtle changes in ocean sample ion concentration affect the abundance of relevant metal-binding proteins. These results highlight mebipred’s utility in analyzing microbiome metal requirements.

   mebipred is available as a web server at services.bromberglab.org/mebipred and as a standalone package at https://pypi.org/project/mymetal/.

   Supplementary data are available at Bioinformatics online.

    

   more » « less
3. Protein threading using residue co-variation and deep learning

   https://doi.org/10.1093/bioinformatics/bty278  

   Zhu, Jianwei ; Wang, Sheng ; Bu, Dongbo ; Xu, Jinbo ( June 2018 , Bioinformatics)

   Template-based modeling, including homology modeling and protein threading, is a popular method for protein 3D structure prediction. However, alignment generation and template selection for protein sequences without close templates remain very challenging.

   We present a new method called DeepThreader to improve protein threading, including both alignment generation and template selection, by making use of deep learning (DL) and residue co-variation information. Our method first employs DL to predict inter-residue distance distribution from residue co-variation and sequential information (e.g. sequence profile and predicted secondary structure), and then builds sequence-template alignment by integrating predicted distance information and sequential features through an ADMM algorithm. Experimental results suggest that predicted inter-residue distance is helpful to both protein alignment and template selection especially for protein sequences without very close templates, and that our method outperforms currently popular homology modeling method HHpred and threading method CNFpred by a large margin and greatly outperforms the latest contact-assisted protein threading method EigenTHREADER.

   http://raptorx.uchicago.edu/

   Supplementary data are available at Bioinformatics online.

    

   more » « less
4. Genome-wide alignment-free phylogenetic distance estimation under a no strand-bias model

   https://doi.org/10.1093/bioadv/vbac055  

   Balaban, Metin ; Bristy, Nishat Anjum ; Faisal, Ahnaf ; Bayzid, Md Shamsuzzoha ; Mirarab, Siavash ; Lengauer, ed., Thomas ( August 2022 , Bioinformatics Advances)

   Summary: While alignment has been the dominant approach for determining homology prior to phylogenetic inference, alignment-free methods can simplify the analysis, especially when analyzing genome-wide data. Furthermore, alignment-free methods present the only option for emerging forms of data, such as genome skims, which do not permit assembly. Despite the appeal, alignment-free methods have not been competitive with alignment-based methods in terms of accuracy. One limitation of alignment-free methods is their reliance on simplified models of sequence evolution such as Jukes–Cantor. If we can estimate frequencies of base substitutions in an alignment-free setting, we can compute pairwise distances under more complex models. However, since the strand of DNA sequences is unknown for many forms of genome-wide data, which arguably present the best use case for alignment-free methods, the most complex models that one can use are the so-called no strand-bias models. We show how to calculate distances under a four-parameter no strand-bias model called TK4 without relying on alignments or assemblies. The main idea is to replace letters in the input sequences and recompute Jaccard indices between k-mer sets. However, on larger genomes, we also need to compute the number of k-mer mismatches after replacement due to random chance as opposed to homology. We show in simulation that alignment-free distances can be highly accurate when genomes evolve under the assumed models and study the accuracy on assembled and unassembled biological data.

   Our software is available open source at https://github.com/nishatbristy007/NSB.

   Supplementary data are available at Bioinformatics Advances online.

    

   more » « less
5. ModuleAlign: module-based global alignment of protein–protein interaction networks

   https://doi.org/10.1093/bioinformatics/btw447  

   Hashemifar, Somaye ; Ma, Jianzhu ; Naveed, Hammad ; Canzar, Stefan ; Xu, Jinbo ( August 2016 , Bioinformatics)

   As an increasing amount of protein–protein interaction (PPI) data becomes available, their computational interpretation has become an important problem in bioinformatics. The alignment of PPI networks from different species provides valuable information about conserved subnetworks, evolutionary pathways and functional orthologs. Although several methods have been proposed for global network alignment, there is a pressing need for methods that produce more accurate alignments in terms of both topological and functional consistency.

   In this work, we present a novel global network alignment algorithm, named ModuleAlign, which makes use of local topology information to define a module-based homology score. Based on a hierarchical clustering of functionally coherent proteins involved in the same module, ModuleAlign employs a novel iterative scheme to find the alignment between two networks. Evaluated on a diverse set of benchmarks, ModuleAlign outperforms state-of-the-art methods in producing functionally consistent alignments. By aligning Pathogen–Human PPI networks, ModuleAlign also detects a novel set of conserved human genes that pathogens preferentially target to cause pathogenesis.

   http://ttic.uchicago.edu/∼hashemifar/ModuleAlign.html

   canzar@ttic.edu or j3xu.ttic.edu

   Supplementary data are available at Bioinformatics online.

    

   more » « less