Choosing non-redundant representative subsets of protein sequence data sets using submodular optimization.
Choosing non-redundant representative subsets of protein sequence data sets using submodular optimization.
复制标题
DOI：
10.1002/prot.25461
复制
发表时间：
2018-04
期刊：
影响因子：
2.9
通讯作者：
Noble WS
中科院分区：
文献类型：
--
作者：
Libbrecht MW;Bilmes JA;Noble WS
选择序列的非冗余代表性子集是许多生物信息学工作流程中的常见步骤，例如为序列和结构模型创建非冗余训练集或从宏基因组学数据中选择“操作分类单元”。以前的方法，如CD-HIT，PISCES和UCLUST，应用启发式阈值为基础的算法，没有理论保证。我们提出了一种新的方法，基于子模块优化。子模优化，连续凸优化的离散模拟，已被用于其他代表性的集选择问题取得了巨大成功。我们表明，子模块优化方法的结果在代表性的蛋白质序列子集具有更大的结构多样性比现有的方法选择的集合，作为一个金标准的蛋白质结构域结构的SCOPe库。在这种情况下，子模块优化始终产生蛋白质序列子集，包括更多的SCOPe结构域的家庭比组的相同大小的选择竞争的方法。我们还展示了如何优化框架，使我们能够设计一个混合物的目标函数，表现良好的大型和小型代表集。我们描述的框架是多项式时间内最好的（在某些假设下），它是灵活和直观的，因为它应用了一套通用方法来优化各种目标函数之一。
Selecting a non-redundant representative subset of sequences is a common step in many bioinformatics workflows, such as the creation of non-redundant training sets for sequence and structural models or selection of “operational taxonomic units” from metagenomics data. Previous methods for this task, such as CD-HIT, PISCES and UCLUST, apply a heuristic threshold-based algorithm that has no theoretical guarantees. We propose a new approach based on submodular optimization. Submodular optimization, a discrete analogue to continuous convex optimization, has been used with great success for other representative set selection problems. We demonstrate that the submodular optimization approach results in representative protein sequence subsets with greater structural diversity than sets chosen by existing methods, using as a gold standard the SCOPe library of protein domain structures. In this setting, submodular optimization consistently yields protein sequence subsets that include more SCOPe domain families than sets of the same size selected by competing approaches. We also show how the optimization framework allows us to design a mixture objective function that performs well for both large and small representative sets. The framework we describe is the best possible in polynomial time (under some assumptions), and it is flexible and intuitive because it applies a suite of generic methods to optimize one of a variety of objective functions.
登录
查看更多内容
影响因子：
3
作者：
Hauser M;Mayer CE;Söding J
通讯作者：
Söding J
影响因子：
1.6
作者：
Feige, Uriel;Mirrokni, Vahab S.;Vondrak, Jan
通讯作者：
Vondrak, Jan
影响因子：
5.8
作者：
Edgar, Robert C.
通讯作者：
Edgar, Robert C.
影响因子：
14.9
作者：
Brenner, SE;Koehl, P;Levitt, R
通讯作者：
Levitt, R
DOI：
10.1007/bfb0121195
发表时间：
1978-01-01
期刊：
MATHEMATICAL PROGRAMMING STUDY
影响因子：
--
作者：
FISHER, ML;NEMHAUSER, GL;WOLSEY, LA
通讯作者：
WOLSEY, LA