minorg.minweight_sc module

Implementation of the weight-based set cover algorithm presented in Ajami, Z. and Cohen, S. (2019) Enumerating Minimal Weight Set Covers. Proceedings - International Conference on Data Engineering, 518-529

class minorg.minweight_sc.Q(set_of_sets_class=None)[source]

Bases: list

__init__(set_of_sets_class=None)[source]

extract_min()[source]

Returns Set object with lowest weight.

Returns: Set

is_empty() → bool[source]

property top: minorg.minweight_sc.e[source]

class minorg.minweight_sc.Set(name, weight, elements)[source]

Bases: set

__init__(name, weight, elements)[source]

Effectively a set object that tracks name and weight.

Parameters

name (str) – set name
weight (float) – set weight
elements (iterable) – elements in set

copy()[source]: Returns a shallow copy of self.

property w: float[source]

class minorg.minweight_sc.SetOfSets(*Sets)[source]

Bases: set

__init__(*Sets)[source]

Parameters: Sets (iter) – iter of Set objects

add(*Sets) → None[source]: Add one or more Set.

copy()[source]

Create a shallow copy of self.

Returns: SetOfSets

property elements[source]

get(*names) → list[source]

Get Set (s) by set name.

Returns: list of Set

intersection(*args, **kwargs)[source]

Implements set.intersection method for this class.

Returns: SetOfSets

property redundancy: int[source]: Returns sum of the number of times each element is present in more than one set.

remove(*Sets) → None[source]: Remove one or more Set.

property set_names[source]

property sets[source]

symmetric_difference(*args, **kwargs)[source]

Impelements set.symmetric_difference method for this class.

Returns: Set

union(*args, **kwargs)[source]

Implements set.union method for this class.

Returns: SetOfSets

property w[source]

property weight[source]

minorg.minweight_sc.approx_min_SC(U, S, seed=None, low_coverage_penalty=0) → minorg.minweight_sc.SetOfSets[source]

Approximate minimum set cover algorithm.

Parameters

U (set) – set of elements (targets) to cover
S (SetOfSets) – SetOfSets (or child class) object containing sets (gRNA coverage) for set cover
seed (Set) – Set (or child class) object to add first (optional)

Returns

Set cover solution. May also be child class of SetOfSets.

Return type

SetOfSets

minorg.minweight_sc.argmin(set_of_sets) → minorg.minweight_sc.Set[source]

Returns Set with smallest weight.

Parameters: set_of_sets (SetOfSets) – SetOfSets (or child class) object
Returns: Set

class minorg.minweight_sc.e(a, b, c, tiebreaker=None)[source]

Bases: object

property C[source]

property Sfc[source]

property So[source]

So_min()[source]

__init__(a, b, c, tiebreaker=None)[source]

copy()[source]

remove(*args, **kwargs)[source]

property w[source]

class minorg.minweight_sc.e1(a, b, c)[source]

Bases: minorg.minweight_sc.e

property Sf[source]

__init__(a, b, c)[source]

class minorg.minweight_sc.e2(a, b, c)[source]

Bases: minorg.minweight_sc.e

property Sc[source]

__init__(a, b, c)[source]

minorg.minweight_sc.enum_approx_order_SC(U, S, num_iter=100, seed=None, low_coverage_penalty=0) → list[source]

Minimum weight set cover algorithm, adapted to allow seeding and setting of enumeration limit.

Algorithm described in: Ajami, Z. and Cohen, S. (2019). Enumerating Minimal Weight Set Covers. In Proceedings - International Conference on Data Engineering, 518-529

Parameters

U (set) – set of elements (targets) to cover
S (SetOfSets) – SetOfSets (or child class) object containing sets (gRNA coverage) for set cover
num_iter (int) – maximum number of iterations/enumerations (default=100)
seed (Set) – Set (or child class) object to add first (optional)

Returns

list of SetOfSets object where each is a set cover solution

Return type

list of SetOfSets

minorg.minweight_sc.make_examples()[source]

minorg.minweight_sc.make_examples_2()[source]

minorg.minweight_sc.wc_ratio(s1, s2, low_coverage_penalty=0) → float[source]

Calculates ratio of weight of s1 to number of elements in s2 that can be covered by s1. (wc is shorthand for weight-cover, a name I came up with because the authors did not)

Low coverage penalty was added to allow disincentivisation of ultra large set covers full of small, non-overlapping, ultra low coverage sets.

Parameters

s1 (set) – first set
s2 (set) – second set
low_coverage_penalty (float) – if 0, no penalty for uncovered elements. Modifies output value into ‘<wc ratio> + (<low_coverage_penalty> * <wc ratio> * <uncovered>/<covered>)’