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

Area of Science:

• Bioinformatics
• Computational Biology
• Structural Biology

Background:

• Selecting non-redundant sequence subsets is crucial for bioinformatics tasks like training models and metagenomics analysis.
• Existing methods (e.g., CD-HIT, PISCES, UCLUST) use heuristic, threshold-based algorithms lacking theoretical guarantees.

Purpose of the Study:

• To develop a new, theoretically grounded approach for selecting representative sequence subsets.
• To improve the structural diversity of selected protein sequence sets.

Main Methods:

• Utilized submodular optimization, a discrete optimization technique analogous to continuous convex optimization.
• Applied the framework to select representative protein sequence subsets using the SCOPe library as a benchmark.

Main Results:

• Submodular optimization yielded protein sequence subsets with greater structural diversity than existing methods.
• The approach consistently identified more SCOPe domain families in subsets of equivalent size compared to competing methods.
• A flexible mixture objective function was designed to perform well for both large and small representative sets.

Conclusions:

• Submodular optimization offers a theoretically sound and flexible framework for representative sequence selection.
• This method surpasses existing heuristic approaches in capturing structural diversity and identifying diverse protein families.
• The polynomial-time optimal framework provides a powerful and intuitive tool for bioinformatics workflows.