Volk Jochen, Herrmann Torsten, Wüthrich Kurt
Institut für Molekularbiologie und Biophysik, ETH Zürich, Zurich, Switzerland.
J Biomol NMR. 2008 Jul;41(3):127-38. doi: 10.1007/s10858-008-9243-5. Epub 2008 May 30.
MATCH (Memetic Algorithm and Combinatorial Optimization Heuristics) is a new memetic algorithm for automated sequence-specific polypeptide backbone NMR assignment of proteins. MATCH employs local optimization for tracing partial sequence-specific assignments within a global, population-based search environment, where the simultaneous application of local and global optimization heuristics guarantees high efficiency and robustness. MATCH thus makes combined use of the two predominant concepts in use for automated NMR assignment of proteins. Dynamic transition and inherent mutation are new techniques that enable automatic adaptation to variable quality of the experimental input data. The concept of dynamic transition is incorporated in all major building blocks of the algorithm, where it enables switching between local and global optimization heuristics at any time during the assignment process. Inherent mutation restricts the intrinsically required randomness of the evolutionary algorithm to those regions of the conformation space that are compatible with the experimental input data. Using intact and artificially deteriorated APSY-NMR input data of proteins, MATCH performed sequence-specific resonance assignment with high efficiency and robustness.
MATCH（记忆算法与组合优化启发式算法）是一种用于蛋白质序列特异性多肽主链核磁共振自动归属的新型记忆算法。MATCH在基于群体的全局搜索环境中采用局部优化来追踪部分序列特异性归属，在该环境中，局部和全局优化启发式算法的同时应用保证了高效性和稳健性。MATCH因此结合了用于蛋白质核磁共振自动归属的两个主要概念。动态转换和固有突变是能够自动适应实验输入数据质量变化的新技术。动态转换概念被纳入算法的所有主要构建模块中，在归属过程中的任何时候，它都能使局部和全局优化启发式算法之间进行切换。固有突变将进化算法内在所需的随机性限制在构象空间中与实验输入数据兼容的那些区域。利用完整的和人为恶化的蛋白质APSY-NMR输入数据，MATCH高效且稳健地进行了序列特异性共振归属。
