Filling a Protein Scaffold With a Reference.
Filling a Protein Scaffold With a Reference.
复制标题
用参考填充蛋白质支架。
DOI：
10.1109/tnb.2017.2666780
复制
发表时间：
2017
影响因子：
3.9
通讯作者：
Zhu,Binhai
中科院分区：
文献类型：
--
作者：
Qingge,Letu;Liu,Xiaowen;Zhong,Farong;Zhu,Binhai
在基于质谱的从头蛋白质测序中，很难完成整个蛋白质的测序。受此启发，我们研究了用一些缺失的氨基酸填充蛋白质支架S的（单方面的）问题，给定一个不允许改变的重叠群序列，相对于长度为n的完整参考蛋白质P，使得P和填充序列S'之间的BLOSUM62得分最大化。我们证明这个问题可以在 O(n26) 时间内多项式时间求解。我们还考虑了重叠群质量不高并且它们连接成（不完整）序列 I 的情况，其中缺失的氨基酸可以插入 I 中的任何位置以获得 I'，从而使 P 和 I' 之间的 BLOSUM62 得分最大化。我们证明这个问题可以在 O(n26) 时间内多项式时间求解。由于时间复杂度较高，这两种算法都不实用，因此我们提出了几种基于贪心和局部搜索的算法，试图解决实际问题。基于一些抗体和哺乳动物蛋白的实证结果表明，只要给出一对良好的支架和参考，该算法可以高质量地填充蛋白质支架。
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 scaffoldS 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(n26) 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 betweenP and I' is maximized. We show that this problem is polynomial-time solvable in O(n26) 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.