Convergent algorithms for protein structural alignment
Convergent algorithms for protein structural alignment
复制标题
DOI：
10.1186/1471-2105-8-306
复制
发表时间：
2007-08-22
影响因子：
3
通讯作者：
Martinez, Jose Mario
中科院分区：
文献类型：
--
作者：
Martinez, Leandro;Andreani, Roberto;Martinez, Jose Mario
背景资料：蛋白质结构比对有许多算法，它们基于蛋白质内部坐标或结构的显式叠加。这些方法通常是成功的检测结构相似性。然而，目前的实用方法很少得到收敛理论的支持。特别是，虽然每个算法的目标是最大化一些评分函数，但没有实际的方法在理论上保证得分最大化。一个实用的算法与固体收敛性能将是有用的蛋白质折叠图的细化，并为开发新的分数设计相关的功能similarity.Results：在这项工作中，最大化的评分功能在蛋白质比对被解释为一个低阶值优化（LOVO）问题。新的解释提供了一个框架的基础上完善的连续优化方法的算法的发展。所得到的算法是收敛的，并在每次迭代中增加评分函数。所得解是评分函数的临界点。介绍了两种算法：一种是基于动态规划的评分函数的最大化，然后是连续最大化相同的分数，相对于蛋白质的位置，使用光滑牛顿方法。第二个算法取代了动态规划步骤的快速程序计算C原子之间的对应关系。该算法被证明是非常有效的最大化的MAPICTAL score.Conclusion：蛋白质比对的解释为LOVO问题提供了一个新的理论框架，收敛的蛋白质比对算法的发展。这些算法被证明是非常可靠的最大限度地提高了的距离依赖的分数，和其他距离依赖的分数可以用相同的策略进行优化。由这些算法提供的改进的评分优化提供了用于细化蛋白质折叠图的手段，并且还提供了用于开发设计成匹配生物功能的评分的手段。LOVO策略也可以用于更一般的结构叠加问题，如灵活或非顺序排列。该套教材可在网上查阅，网址为：http：//www.时间。单声道放大器br/类似于martinez/lovoalign。
Background: Many algorithms exist for protein structural alignment, based on internal protein coordinates or on explicit superposition of the structures. These methods are usually successful for detecting structural similarities. However, current practical methods are seldom supported by convergence theories. In particular, although the goal of each algorithm is to maximize some scoring function, there is no practical method that theoretically guarantees score maximization. A practical algorithm with solid convergence properties would be useful for the refinement of protein folding maps, and for the development of new scores designed to be correlated with functional similarity.Results: In this work, the maximization of scoring functions in protein alignment is interpreted as a Low Order Value Optimization ( LOVO) problem. The new interpretation provides a framework for the development of algorithms based on well established methods of continuous optimization. The resulting algorithms are convergent and increase the scoring functions at every iteration. The solutions obtained are critical points of the scoring functions. Two algorithms are introduced: One is based on the maximization of the scoring function with Dynamic Programming followed by the continuous maximization of the same score, with respect to the protein position, using a smooth Newtonian method. The second algorithm replaces the Dynamic Programming step by a fast procedure for computing the correspondence between C a atoms. The algorithms are shown to be very effective for the maximization of the STRUCTAL score.Conclusion: The interpretation of protein alignment as a LOVO problem provides a new theoretical framework for the development of convergent protein alignment algorithms. These algorithms are shown to be very reliable for the maximization of the STRUCTAL score, and other distance-dependent scores may be optimized with same strategy. The improved score optimization provided by these algorithms provide means for the refinement of protein fold maps and also for the development of scores designed to match biological function. The LOVO strategy may be also used for more general structural superposition problems such as flexible or non-sequential alignments. The package is available on-line at http:// www. ime. unicamp. br/similar to martinez/lovoalign.