Skip to content

RM all can trigger combinatorial explosion in all_best_solutions.tsv during best-solution enumeration #85

Description

@shixingzhao00

Environment:

  • DefenseFinder 3.0.0
  • defense-finder-models 3.0.0
  • MacSyFinder 2.1.4 via DefenseFinder, also reproduced with MacSyFinder 2.1.6
  • Python 3.12 / 3.14 tested
  • ordered_replicon mode
  • model: defense-finder-models/RM all

Problem:
In a batch of 20,822 bacterial genomes, 21 genomes stalled during the RM best-solution stage. One reproducible example is GCF_000332235.1.

The run reaches:
Computing best solutions for GCF_000332235.1 (nb of candidate systems 52)

The process is CPU-bound and not stuck in HMMER. py-spy showed hotspots in best-solution / solution serialization. all_best_solutions.tsv grows explosively: from 1.79 GB to 2.86 GB in ~60 seconds, and the partial file already reached sol_id=532567.

This appears to be caused by exhaustive enumeration/output of a very large number of equivalent best solutions for RM candidate systems.

Expected behavior:
The tool should either:

  1. complete without writing GB-scale all_best_solutions.tsv,
  2. provide a way to cap the number of equivalent best solutions,
  3. provide a single-best-solution mode that returns one representative best solution, or
  4. warn/timeout specifically when all_best_solutions enumeration explodes.

Local workaround:
We patched find_best_solutions() to support a single-best representative mode. It uses a maximum-weight clique objective with lexicographic weights approximating the original Solution ordering:
system score -> hit number -> system number -> wholeness.

With this patch, the same example completes:
Computing best solutions for GCF_000332235.1 (nb of candidate systems 52)
It took 0.06 sec to find best solution (38.00)
END

The patch does not alter HMM search, candidate system construction, compatibility checking, or system scoring. It only avoids exhaustive enumeration of all equivalent best solutions.

Metadata

Metadata

Assignees

No one assigned

    Type

    No type

    Fields

    No fields configured for issues without a type.

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions