Choosing non-redundant representative subsets of protein sequence data sets using submodular optimization.

ABSTRACT: 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

SUBMITTER: Libbrecht MW 

PROVIDER: S-EPMC5835207 | biostudies-literature | 2018 Apr

REPOSITORIES: biostudies-literature