Skip to content

Commit f68a180

Browse files
author
Dmytro Guzenko
committed
local symmetry detection based on clustering and contact graphs
1 parent fd10e64 commit f68a180

6 files changed

Lines changed: 277 additions & 116 deletions

File tree

‎biojava-structure/pom.xml‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -59,7 +59,7 @@
5959
<dependency>
6060
<groupId>org.jgrapht</groupId>
6161
<artifactId>jgrapht-core</artifactId>
62-
<version>0.9.2</version>
62+
<version>1.1.0</version>
6363
</dependency>
6464

6565
<!-- logging dependencies (managed by parent pom, don't set versions or

‎biojava-structure/src/main/java/org/biojava/nbio/structure/cluster/SubunitClusterUtils.java‎

Lines changed: 9 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -35,10 +35,10 @@ public static String getStoichiometryString(List<SubunitCluster> clusters) {
3535

3636
// List number of members in each cluster
3737
List<Integer> stoichiometries =
38-
clusters.stream().
39-
map(SubunitCluster::size).
40-
sorted().
41-
collect(Collectors.toList());
38+
clusters.stream().
39+
map(SubunitCluster::size).
40+
sorted().
41+
collect(Collectors.toList());
4242

4343
Collections.reverse(stoichiometries);
4444

@@ -75,11 +75,11 @@ public static List<SubunitCluster> orderByStoichiometry(List<SubunitCluster> clu
7575
String alpha = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
7676

7777
List<SubunitCluster> clustersSorted =
78-
clusters.stream().
79-
sorted(Comparator.
80-
comparing(SubunitCluster::size).
81-
reversed()).
82-
collect(Collectors.toList());
78+
clusters.stream().
79+
sorted(Comparator.
80+
comparing(SubunitCluster::size).
81+
reversed()).
82+
collect(Collectors.toList());
8383

8484
for (int i = 0; i < clustersSorted.size(); i++) {
8585
int ind = i % alpha.length();

‎biojava-structure/src/main/java/org/biojava/nbio/structure/symmetry/core/QuatSymmetryDetector.java‎

Lines changed: 238 additions & 57 deletions
Original file line numberDiff line numberDiff line change
@@ -23,15 +23,17 @@
2323
package org.biojava.nbio.structure.symmetry.core;
2424

2525
import org.biojava.nbio.structure.Structure;
26-
import org.biojava.nbio.structure.cluster.Subunit;
27-
import org.biojava.nbio.structure.cluster.SubunitCluster;
28-
import org.biojava.nbio.structure.cluster.SubunitClusterer;
29-
import org.biojava.nbio.structure.cluster.SubunitClustererParameters;
30-
import org.biojava.nbio.structure.symmetry.utils.PowerSet;
26+
import org.biojava.nbio.structure.cluster.*;
3127
import org.slf4j.Logger;
3228
import org.slf4j.LoggerFactory;
3329

30+
import org.jgrapht.alg.clique.CliqueMinimalSeparatorDecomposition;
31+
import org.jgrapht.graph.DefaultEdge;
32+
import org.jgrapht.graph.AsSubgraph;
33+
import org.jgrapht.Graph;
34+
3435
import java.util.*;
36+
import java.util.stream.Collectors;
3537

3638
/**
3739
* Detects the symmetry (global, pseudo, internal and local) of protein
@@ -109,6 +111,7 @@ public static QuatSymmetryResults calcGlobalSymmetry(
109111
return calcQuatSymmetry(clusters, symmParams);
110112
}
111113

114+
112115
/**
113116
* Returns a List of LOCAL symmetry results. This means that a subset of the
114117
* {@link SubunitCluster} is left out of the symmetry calculation. Each
@@ -130,8 +133,8 @@ public static QuatSymmetryResults calcGlobalSymmetry(
130133
public static List<QuatSymmetryResults> calcLocalSymmetries(
131134
Structure structure, QuatSymmetryParameters symmParams,
132135
SubunitClustererParameters clusterParams) {
133-
List<SubunitCluster> clusters = SubunitClusterer.cluster(structure,
134-
clusterParams);
136+
137+
List<SubunitCluster> clusters = SubunitClusterer.cluster(structure, clusterParams);
135138
return calcLocalSymmetries(clusters, symmParams);
136139
}
137140

@@ -156,8 +159,8 @@ public static List<QuatSymmetryResults> calcLocalSymmetries(
156159
public static List<QuatSymmetryResults> calcLocalSymmetries(
157160
List<Subunit> subunits, QuatSymmetryParameters symmParams,
158161
SubunitClustererParameters clusterParams) {
159-
List<SubunitCluster> clusters = SubunitClusterer.cluster(subunits,
160-
clusterParams);
162+
163+
List<SubunitCluster> clusters = SubunitClusterer.cluster(subunits, clusterParams);
161164
return calcLocalSymmetries(clusters, symmParams);
162165
}
163166

@@ -177,79 +180,257 @@ public static List<QuatSymmetryResults> calcLocalSymmetries(
177180
* @return List of LOCAL quaternary structure symmetry results. Empty if
178181
* none.
179182
*/
180-
public static List<QuatSymmetryResults> calcLocalSymmetries(
181-
List<SubunitCluster> clusters, QuatSymmetryParameters symmParams) {
182183

183-
List<QuatSymmetryResults> localSymmetries = new ArrayList<QuatSymmetryResults>();
184+
public static List<QuatSymmetryResults> calcLocalSymmetries(List<SubunitCluster> clusters, QuatSymmetryParameters symmParams) {
184185

185-
// If it is homomeric return empty
186-
if (clusters.size() < 2)
187-
return localSymmetries;
186+
symmParams.setLocalTimeStart(System.nanoTime());
188187

189-
// If there are less than 3 or more than maximum Subunits return empty
190-
QuatSymmetrySubunits subunits = new QuatSymmetrySubunits(clusters);
191-
if (subunits.getSubunitCount() < 3
192-
|| subunits.getSubunitCount() > symmParams
193-
.getMaximumLocalSubunits())
194-
return localSymmetries;
188+
Set<Set<Integer>> knownResults = new HashSet<>();
189+
List<QuatSymmetryResults> outputSymmetries = new ArrayList<>();
190+
191+
List<SubunitCluster> nontrivialClusters =
192+
clusters.stream().
193+
filter(cluster -> (cluster.size()>1)).
194+
collect(Collectors.toList());
195+
196+
QuatSymmetrySubunits allSubunits = new QuatSymmetrySubunits(nontrivialClusters);
197+
198+
if (allSubunits.getSubunitCount() < 2)
199+
return outputSymmetries;
195200

196-
// Start local symmetry calculations
197-
long start = System.nanoTime();
201+
Graph<Integer, DefaultEdge> graph = SubunitContactGraph.calculateGraph(allSubunits.getTraces());
198202

199-
// Calculate the power Set of the clusters
200-
Set<Set<SubunitCluster>> powerSet = new PowerSet<SubunitCluster>()
201-
.powerSet(new LinkedHashSet<SubunitCluster>(clusters));
203+
List<Integer> allSubunitIds = new ArrayList<>(graph.vertexSet());
204+
Collections.sort(allSubunitIds);
205+
List<Integer> allSubunitClusterIds = allSubunits.getClusterIds();
202206

203-
int combinations = 1;
204-
for (Set<SubunitCluster> cluster : powerSet) {
207+
Map<Integer, List<Integer>> clusterIdToSubunitIds =
208+
allSubunitIds.stream().
209+
collect(Collectors.
210+
groupingBy(allSubunitClusterIds::get, Collectors.toList()));
205211

206-
// Break if time limit passed
207-
double time = (System.nanoTime() - start) / 1000000000;
208-
if (time > symmParams.getLocalTimeLimit()) {
209-
logger.warn("Exceeded time limit for local symmetry "
210-
+ "calculations. {} seconds elapsed. "
211-
+ "Local symmetry results may be incomplete.", time);
212-
break;
212+
List<QuatSymmetryResults> redundantSymmetries = new ArrayList<>();
213+
if (clusters.size()>1) {
214+
List<QuatSymmetryResults> clusterSymmetries =
215+
calcLocalSymmetriesCluster(nontrivialClusters, clusterIdToSubunitIds,symmParams, knownResults);
216+
redundantSymmetries.addAll(clusterSymmetries);
217+
}
218+
219+
List<QuatSymmetryResults> graphSymmetries = calcLocalSymmetriesGraph(nontrivialClusters,
220+
allSubunitClusterIds,
221+
clusterIdToSubunitIds,
222+
symmParams,
223+
knownResults,
224+
graph);
225+
226+
redundantSymmetries.addAll(graphSymmetries);
227+
228+
redundantSymmetries =
229+
redundantSymmetries.stream().
230+
sorted(Comparator.
231+
comparing((QuatSymmetryResults r) -> r.getRotationGroup().getOrder()).
232+
thenComparing(r -> r.getSubunitCount()).reversed()).
233+
collect(Collectors.toList());
234+
235+
for (QuatSymmetryResults redundantSymmetry:redundantSymmetries) {
236+
if (outputSymmetries.stream().
237+
noneMatch(redundantSymmetry::isSupersededBy)) {
238+
outputSymmetries.add(redundantSymmetry);
213239
}
240+
}
241+
242+
double time = (System.nanoTime() - symmParams.getLocalTimeStart()) / 1000000000;
243+
if (time > symmParams.getLocalTimeLimit()) {
244+
logger.warn("Exceeded time limit for local symmetry "
245+
+ "calculations. {} seconds elapsed. "
246+
+ "Local symmetry results may be incomplete.", time);
247+
}
248+
return outputSymmetries;
249+
}
250+
251+
private static List<QuatSymmetryResults> calcLocalSymmetriesCluster(List<SubunitCluster> nontrivialClusters,
252+
Map<Integer, List<Integer>> clusterIdToSubunitIds,
253+
QuatSymmetryParameters symmParams,
254+
Set<Set<Integer>> knownResults) {
255+
256+
List<QuatSymmetryResults> clusterSymmetries = new ArrayList<>();
214257

215-
// Break if maximum number of results exceeded
216-
if (localSymmetries.size() > symmParams.getMaximumLocalResults()) {
217-
logger.warn("Exceeded maximum number of local symmetry "
218-
+ "results. {} results calculated. "
219-
+ "Local symmetry results may be incomplete.",
220-
localSymmetries.size());
221-
break;
258+
// find solutions for single clusters
259+
for (int i=0;i<nontrivialClusters.size();i++) {
260+
SubunitCluster nontrivialCluster = nontrivialClusters.get(i);
261+
QuatSymmetryResults localResult =
262+
calcQuatSymmetry(Collections.singletonList(nontrivialCluster),symmParams);
263+
264+
if(localResult!=null && !localResult.getSymmetry().equals("C1")) {
265+
localResult.setLocal(true);
266+
clusterSymmetries.add(localResult);
267+
Set<Integer> knownResult = new HashSet<>(clusterIdToSubunitIds.get(i));
268+
knownResults.add(knownResult);
222269
}
270+
}
271+
272+
// group clusters by symmetries found, in case they all share axes and have the same number of subunits
273+
Map<String, Map<Integer,List<QuatSymmetryResults>>> groupedSymmetries =
274+
clusterSymmetries.stream().
275+
collect(Collectors.
276+
groupingBy(QuatSymmetryResults::getSymmetry,Collectors.
277+
groupingBy(QuatSymmetryResults::getSubunitCount,Collectors.toList())));
278+
279+
for (Map<Integer,List<QuatSymmetryResults>> symmetriesByGroup: groupedSymmetries.values()) {
280+
for (List<QuatSymmetryResults> symmetriesBySubunits: symmetriesByGroup.values()) {
281+
282+
List<SubunitCluster> clustersGroup =
283+
symmetriesBySubunits.stream().
284+
map(r -> r.getSubunitClusters().get(0)).
285+
collect(Collectors.toList());
286+
287+
if (clustersGroup.size() < 2) {
288+
continue;
289+
}
223290

224-
// Break if maximum number of tried combinations exceeded
225-
if (combinations > symmParams.getMaximumLocalCombinations()) {
226-
logger.warn("Exceeded maximum number of local combinations."
227-
+ " {} combinations tried. "
228-
+ "Local symmetry results may be incomplete.",
229-
combinations);
230-
break;
291+
QuatSymmetryResults localResult = calcQuatSymmetry(clustersGroup,symmParams);
292+
293+
if(localResult!=null && !localResult.getSymmetry().equals("C1")) {
294+
localResult.setLocal(true);
295+
clusterSymmetries.add(localResult);
296+
// find subunit ids in this cluster list
297+
Set<Integer> knownResult = new HashSet<>();
298+
for (SubunitCluster cluster: clustersGroup) {
299+
int i = nontrivialClusters.indexOf(cluster);
300+
knownResult.addAll(clusterIdToSubunitIds.get(i));
301+
}
302+
knownResults.add(knownResult);
303+
}
231304
}
305+
}
306+
return clusterSymmetries;
307+
}
308+
309+
310+
private static List<QuatSymmetryResults> calcLocalSymmetriesGraph(final List<SubunitCluster> allClusters,
311+
final List<Integer> allSubunitClusterIds,
312+
final Map<Integer, List<Integer>> clusterIdToSubunitIds,
313+
QuatSymmetryParameters symmParams,
314+
Set<Set<Integer>> knownResults,
315+
Graph<Integer, DefaultEdge> graph) {
316+
317+
List<QuatSymmetryResults> localSymmetries = new ArrayList<>();
318+
319+
double time = (System.nanoTime() - symmParams.getLocalTimeStart()) / 1000000000;
320+
if (time > symmParams.getLocalTimeLimit()) {
321+
return localSymmetries;
322+
}
323+
324+
// calc components of a (sub-)graph
325+
CliqueMinimalSeparatorDecomposition<Integer, DefaultEdge> cmsd =
326+
new CliqueMinimalSeparatorDecomposition<>(graph);
327+
328+
Set<Set<Integer>> graphComponents =
329+
cmsd.getAtoms().stream().
330+
filter(component -> component.size()>1).
331+
collect(Collectors.toSet());
332+
333+
//subtract known results
334+
graphComponents.removeAll(knownResults);
232335

233-
// Do not use empty set or identity set
234-
if (cluster.size() == 0 || cluster.size() == clusters.size())
336+
for (Set<Integer> graphComponent: graphComponents) {
337+
knownResults.add(graphComponent);
338+
339+
List<Integer> usedSubunitIds = new ArrayList<>(graphComponent);
340+
Collections.sort(usedSubunitIds);
341+
List<SubunitCluster> localClusters =
342+
trimSubunitClusters(allClusters, allSubunitClusterIds, clusterIdToSubunitIds, usedSubunitIds);
343+
344+
if (localClusters.size()==0) {
235345
continue;
346+
}
236347

237-
List<SubunitCluster> localClusters = new ArrayList<SubunitCluster>(
238-
cluster);
239-
QuatSymmetryResults localResult = calcGlobalSymmetry(localClusters,
240-
symmParams);
348+
//NB: usedSubunitIds might have changed when trimming clusters
349+
Set<Integer> usedSubunitIdsSet = new HashSet<>(usedSubunitIds);
350+
if(!graphComponent.equals(usedSubunitIdsSet)) {
351+
if(knownResults.contains(usedSubunitIdsSet)) {
352+
continue;
353+
} else {
354+
knownResults.add(usedSubunitIdsSet);
355+
}
356+
}
241357

242-
if (!localResult.getSymmetry().equals("C1")) {
358+
QuatSymmetryResults localResult = calcQuatSymmetry(localClusters,symmParams);
359+
if(localResult!=null && !localResult.getSymmetry().equals("C1")) {
243360
localResult.setLocal(true);
244361
localSymmetries.add(localResult);
362+
continue;
363+
}
364+
365+
if (usedSubunitIds.size() < 3) {
366+
continue;
367+
}
368+
369+
for (Integer removeSubunitId: usedSubunitIds) {
370+
371+
Set<Integer> prunedGraphVertices = new HashSet<>(usedSubunitIds);
372+
prunedGraphVertices.remove(removeSubunitId);
373+
if (knownResults.contains(prunedGraphVertices)) {
374+
continue;
375+
}
376+
knownResults.add(prunedGraphVertices);
377+
378+
Graph<Integer, DefaultEdge> subGraph = new AsSubgraph<>(graph,prunedGraphVertices);
379+
380+
List<QuatSymmetryResults> localSubSymmetries = calcLocalSymmetriesGraph(allClusters,
381+
allSubunitClusterIds,
382+
clusterIdToSubunitIds,
383+
symmParams,
384+
knownResults,
385+
subGraph);
386+
localSymmetries.addAll(localSubSymmetries);
245387
}
246388

247-
combinations++;
248389
}
249390

250391
return localSymmetries;
251392
}
252393

394+
private static List<SubunitCluster> trimSubunitClusters(List<SubunitCluster> allClusters,
395+
List<Integer> allSubunitClusterIds,
396+
Map<Integer, List<Integer>> clusterIdToSubunitIds,
397+
List<Integer> usedSubunitIds) {
398+
List<SubunitCluster> localClusters = new ArrayList<>();
399+
400+
Set<Integer> usedClusterIds =
401+
usedSubunitIds.stream().
402+
map(allSubunitClusterIds::get).
403+
distinct().
404+
collect(Collectors.toSet());
405+
406+
// for each used cluster, remove unused subunits
407+
for(Integer usedClusterId:usedClusterIds) {
408+
SubunitCluster originalCluster = allClusters.get(usedClusterId);
409+
List<Integer> allSubunitIdsInCluster = clusterIdToSubunitIds.get(usedClusterId);
410+
411+
//subunit numbering is global for the entire graph
412+
// make it zero-based for the inside of a cluster
413+
int minSUValue = Collections.min(allSubunitIdsInCluster);
414+
List<Integer> usedSubunitIdsInCluster = new ArrayList<>(allSubunitIdsInCluster);
415+
usedSubunitIdsInCluster.retainAll(usedSubunitIds);
416+
417+
List<Integer> subunitsToRetain =
418+
usedSubunitIdsInCluster.stream().
419+
map(i -> i-minSUValue).
420+
collect(Collectors.toList());
421+
422+
if (subunitsToRetain.size()>1) {
423+
SubunitCluster filteredCluster = new SubunitCluster(originalCluster, subunitsToRetain);
424+
localClusters.add(filteredCluster);
425+
} else {
426+
// if the cluster ends up having only 1 subunit, remove it from further processing
427+
usedSubunitIds.removeAll(usedSubunitIdsInCluster);
428+
}
429+
}
430+
return localClusters;
431+
}
432+
433+
253434
private static QuatSymmetryResults calcQuatSymmetry(
254435
List<SubunitCluster> clusters, QuatSymmetryParameters parameters) {
255436

0 commit comments

Comments
 (0)