Filling a Protein Scaffold With a Reference

peer-reviewed · IEEE Transactions on NanoBioscience · 2017

peer-reviewed · IEEE Transactions on NanoBioscience · 2017. Letu Qingge et al. In mass spectrometry-based de novo protein sequencing, it is hard to complete the sequence of the whole…
Date 2017-03-01
Type peer-reviewed
Venue IEEE Transactions on NanoBioscience
Publisher Institute of Electrical and Electronics Engineers (IEEE)
Contribution post-processor
DOI 10.1109/tnb.2017.2666780
Citations (OpenAlex) 10

Abstract

In mass spectrometry-based de novo protein sequencing, it is hard to complete the sequence of the whole protein. Motivated by this, we study the (one-sided) problem of filling a protein scaffold S with some missing amino acids, given a sequence of contigs none of which is allowed to be altered, with respect to a complete reference protein P of length n , such that the BLOSUM62 score between P and the filled sequence S’ is maximized. We show that this problem is polynomial-time solvable in O(n 26) time. We also consider the case when the contigs are not of high quality and they are concatenated into an (incomplete) sequence I , where the missing amino acids can be inserted anywhere in I to obtain I’ , such that the BLOSUM62 score between P and I’ is maximized. We show that this problem is polynomial-time solvable in O(n 22) time. Due to the high time complexity, both of these algorithms are impractical, we hence present several algorithms based on greedy and local search, trying to solve the problems practically. The empirical results, based on some antibody and mammalian proteins, show that the algorithms can fill protein scaffolds with high quality, provided that a good pair of scaffold and reference are given.

Authors

  1. Letu Qingge · Montana State University, North Carolina Agricultural and Technical State University, Texas A&M University – Kingsville
  2. Xiaowen Liu · Indiana University Indianapolis, Indiana University School of Medicine, Indiana University-Purdue University Indianapolis, Tulane University, University of Waterloo
  3. Farong Zhong · Zhejiang Normal University
  4. Binhai Zhu (Montana State University) · Montana State University, North Carolina Agricultural and Technical State University

Methods and tools

  • Protein scaffold filling with a reference: Fills missing residues in de novo protein scaffolds against a homologous reference to maximise BLOSUM62 score, with exact and greedy algorithms tested on antibodies.

Cites (6)

Cited by (2)

Seen in the charts

Back to the full map

Back to top