skip to main content

Title: Identification of all-against-all protein–protein interactions based on deep hash learning
Abstract Background

Protein–protein interaction (PPI) is vital for life processes, disease treatment, and drug discovery. The computational prediction of PPI is relatively inexpensive and efficient when compared to traditional wet-lab experiments. Given a new protein, one may wish to find whether the protein has any PPI relationship with other existing proteins. Current computational PPI prediction methods usually compare the new protein to existing proteins one by one in a pairwise manner. This is time consuming.


In this work, we propose a more efficient model, called deep hash learning protein-and-protein interaction (DHL-PPI), to predict all-against-all PPI relationships in a database of proteins. First, DHL-PPI encodes a protein sequence into a binary hash code based on deep features extracted from the protein sequences using deep learning techniques. This encoding scheme enables us to turn the PPI discrimination problem into a much simpler searching problem. The binary hash code for a protein sequence can be regarded as a number. Thus, in the pre-screening stage of DHL-PPI, the string matching problem of comparing a protein sequence against a database withMproteins can be transformed into a much more simpler problem: to find a number inside a sorted array of lengthM. This pre-screening process narrows down the search to a much smaller set of candidate proteins for further confirmation. As a final step, DHL-PPI uses the Hamming distance to verify the final PPI relationship.


The experimental results confirmed that DHL-PPI is feasible and effective. Using a dataset with strictly negative PPI examples of four species, DHL-PPI is shown to be superior or competitive when compared to the other state-of-the-art methods in terms of precision, recall or F1 score. Furthermore, in the prediction stage, the proposed DHL-PPI reduced the time complexity from$$O(M^2)$$O(M2)to$$O(M\log M)$$O(MlogM)for performing an all-against-all PPI prediction for a database withMproteins. With the proposed approach, a protein database can be preprocessed and stored for later search using the proposed encoding scheme. This can provide a more efficient way to cope with the rapidly increasing volume of protein datasets.

more » « less
Award ID(s):
Author(s) / Creator(s):
; ; ; ; ;
Publisher / Repository:
Springer Science + Business Media
Date Published:
Journal Name:
BMC Bioinformatics
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Abstract

    Sequence mappability is an important task in genome resequencing. In the (km)-mappability problem, for a given sequenceTof lengthn, the goal is to compute a table whoseith entry is the number of indices$$j \ne i$$jisuch that the length-msubstrings ofTstarting at positionsiandjhave at mostkmismatches. Previous works on this problem focused on heuristics computing a rough approximation of the result or on the case of$$k=1$$k=1. We present several efficient algorithms for the general case of the problem. Our main result is an algorithm that, for$$k=O(1)$$k=O(1), works in$$O(n)$$O(n)space and, with high probability, in$$O(n \cdot \min \{m^k,\log ^k n\})$$O(n·min{mk,logkn})time. Our algorithm requires a careful adaptation of thek-errata trees of Cole et al. [STOC 2004] to avoid multiple counting of pairs of substrings. Our technique can also be applied to solve the all-pairs Hamming distance problem introduced by Crochemore et al. [WABI 2017]. We further develop$$O(n^2)$$O(n2)-time algorithms to computeall(km)-mappability tables for a fixedmand all$$k\in \{0,\ldots ,m\}$$k{0,,m}or a fixedkand all$$m\in \{k,\ldots ,n\}$$m{k,,n}. Finally, we show that, for$$k,m = \Theta (\log n)$$k,m=Θ(logn), the (km)-mappability problem cannot be solved in strongly subquadratic time unless the Strong Exponential Time Hypothesis fails. This is an improved and extended version of a paper presented at SPIRE 2018.

    more » « less
  2. Abstract Background

    Given a sequencing read, the broad goal of read mapping is to find the location(s) in the reference genome that have a “similar sequence”. Traditionally, “similar sequence” was defined as having a high alignment score and read mappers were viewed as heuristic solutions to this well-defined problem. For sketch-based mappers, however, there has not been a problem formulation to capture what problem an exact sketch-based mapping algorithm should solve. Moreover, there is no sketch-based method that can find all possible mapping positions for a read above a certain score threshold.


    In this paper, we formulate the problem of read mapping at the level of sequence sketches. We give an exact dynamic programming algorithm that finds all hits above a given similarity threshold. It runs in$$\mathcal {O} (|t| + |p| + \ell ^2)$$O(|t|+|p|+2)time and$$\mathcal {O} (\ell \log \ell )$$O(log)space, where |t| is the number of$$k$$k-mers inside the sketch of the reference, |p| is the number of$$k$$k-mers inside the read’s sketch and$$\ell$$is the number of times that$$k$$k-mers from the pattern sketch occur in the sketch of the text. We evaluate our algorithm’s performance in mapping long reads to the T2T assembly of human chromosome Y, where ampliconic regions make it desirable to find all good mapping positions. For an equivalent level of precision as minimap2, the recall of our algorithm is 0.88, compared to only 0.76 of minimap2.

    more » « less
  3. Abstract

    Let$$X\rightarrow {{\mathbb {P}}}^1$$XP1be an elliptically fiberedK3 surface, admitting a sequence$$\omega _{i}$$ωiof Ricci-flat metrics collapsing the fibers. LetVbe a holomorphicSU(n) bundle overX, stable with respect to$$\omega _i$$ωi. Given the corresponding sequence$$\Xi _i$$Ξiof Hermitian–Yang–Mills connections onV, we prove that, ifEis a generic fiber, the restricted sequence$$\Xi _i|_{E}$$Ξi|Econverges to a flat connection$$A_0$$A0. Furthermore, if the restriction$$V|_E$$V|Eis of the form$$\oplus _{j=1}^n{\mathcal {O}}_E(q_j-0)$$j=1nOE(qj-0)forndistinct points$$q_j\in E$$qjE, then these points uniquely determine$$A_0$$A0.

    more » « less
  4. Abstract

    Matrix reduction is the standard procedure for computing the persistent homology of a filtered simplicial complex withmsimplices. Its output is a particular decomposition of the total boundary matrix, from which the persistence diagrams and generating cycles are derived. Persistence diagrams are known to vary continuously with respect to their input, motivating the study of their computation for time-varying filtered complexes. Computing persistence dynamically can be reduced to maintaining a valid decomposition under adjacent transpositions in the filtration order. Since there are$$O(m^2)$$O(m2)such transpositions, this maintenance procedure exhibits limited scalability and is often too fine for many applications. We propose a coarser strategy for maintaining the decomposition over a 1-parameter family of filtrations. By reduction to a particular longest common subsequence problem, we show that the minimal number of decomposition updatesdcan be found in$$O(m \log \log m)$$O(mloglogm)time andO(m) space, and that the corresponding sequence of permutations—which we call aschedule—can be constructed in$$O(d m \log m)$$O(dmlogm)time. We also show that, in expectation, the storage needed to employ this strategy is actually sublinear inm. Exploiting this connection, we show experimentally that the decrease in operations to compute diagrams across a family of filtrations is proportional to the difference between the expected quadratic number of states and the proposed sublinear coarsening. Applications to video data, dynamic metric space data, and multiparameter persistence are also presented.

    more » « less
  5. Abstract

    LetM(x) denote the largest cardinality of a subset of$$\{n \in \mathbb {N}: n \le x\}$${nN:nx}on which the Euler totient function$$\varphi (n)$$φ(n)is nondecreasing. We show that$$M(x) = \left( 1+O\left( \frac{(\log \log x)^5}{\log x}\right) \right) \pi (x)$$M(x)=1+O(loglogx)5logxπ(x)for all$$x \ge 10$$x10, answering questions of Erdős and Pollack–Pomerance–Treviño. A similar result is also obtained for the sum of divisors function$$\sigma (n)$$σ(n).

    more » « less