BB_search

Module summary

A branch-and-bound search scheme implementation for the align-sequences problem: alignts two varseq.VarSeq objects.

Tests coverage: BB_search_test.

(In the implementation details below, click on class/function names for additional documentation and links to the source code.)

❖❖❖

Implements classes:

`BBSearch`(A, B)	Implements the search tree.
`SearchNode`(name, parent, Aresid, Bresid, ...)	Implements search tree node.

Implements functions (outside the classes above):

`LB_by_level`(A, B)	LB: Inversions-driven heuristic.
`LB_by_level_complicated`(A, B)	LB: Another variant of the inversions-driven heuristic (improved)
`LB_current`(A, B)	LB: current size (before the alignment).
`LB_first_aligned`(A, B)	LB: min current size after aligning the first element only.
`LB_last_aligned`(A, B)	LB: min current size after aligning the last element (enumeration).
`LB_lvl_compl_symm`(A, B)	LB: Symmetric version of the previous one.
`LB_lvl_symm`(A, B)	Symmetric version of the `LB_by_level()`.
`nodeattrfunc`(node)	Helper: Generates node attributes for graphviz export.
`nodenamefunc`(node)	Helper: Generates node names for graphviz export.

Attributes defined in the module:

BB_search.LOWER_BOUNDS = [['LB_first', <function LB_first_aligned>, 'min size first element aligned'], ['LB_last', <function LB_last_aligned>, 'min size last element aligned'], ['LB_levels', <function LB_by_level>, 'inversions-driven LB']]: List of lower bounds to examine (used in a separate experiment).

❖❖❖

Implementation details

❖❖❖

BBSearch

class BB_search.BBSearch(A, B)[source]

Implements the search tree.

A, B

first sequence,

Type: varseq.VarSeq

step

current step number,

Type: int

tree_size

current number of nodes in the tree,

Type: int

verbose

debug information printing flag,

Type: Boolean

logging

log bounds flag,

Type: Boolean

logs_UB, logs_LB

upper/lower bounds by step (if verbose),

Type: list

logs_step

step numbers (if verbose),

Type: list

status

search status,

Type: str

root

root node,

Type: class SearchNode

Ap_cand, Bp_cand

A / B aligned to the current candidate optimum,

Type: varseq.VarSeq

node_cand, cand_parent

node corresponding to the current candidate and its parent,

Type: SearchNode

open_nodes

list of nodes to process during the search, each entry is a tuple (<lower bound>,``SearchNode``).

Type: list

Public Methods:

`__init__`(A, B)	Class constructor
`current_best`()	Returns current upper bound (best objective seen).
`dump`([filename])	Technical: dump the tree into a DOT-file (graphivz).
`make_graph_gap`([ax, trueOpt])	figure: produces an LB/UB vs step no.
`set_logging`(logfile, prefix, steps_list)	Sets up the logging process for BB search.
`search`()	Performs BB search (the main procedure).

current_best()[source]: Returns current upper bound (best objective seen).

dump(filename=None)[source]: Technical: dump the tree into a DOT-file (graphivz).

make_graph_gap(ax=None, trueOpt=None)[source]: figure: produces an LB/UB vs step no. figure

search()[source]

Performs BB search (the main procedure).

Note

After the call, the following attributes allow to recover the solution:

status (str): optimal, timeout (initialized before),

Ap_cand, Bp_cand (varseq.VarSeq): A and B after aligning to the candidate (optimum if status = optimal).

set_logging(logfile, prefix, steps_list)[source]: Sets up the logging process for BB search.

❖❖❖

SearchNode

class BB_search.SearchNode(name, parent, Aresid, Bresid, A_tail_start, B_tail_start, A, B)[source]

Implements search tree node.

name

node name,

Type: str

parent

parent node,

Type: SearchNode

A, B

sequences to align,

Type: varseq.VarSeq

Ar, Br

not-yet-aligned parts of A and B.

Type: varseq.VarSeq

A_tail_start, B_tail_start

position for the already-aligned tail start.

Type: int

status

node type (see the note below),

Type: str

tree_UB, tree_LB

current (tree) upper / lower bound,

Type: int

best_obj

current best objective seen,

Type: int

Note

possible node types are: T = Terminal, O = Optimal, I = initialized, P = pruned, ? = unknown (‘open’, not processed), E = processed (‘expanded’)

Public Data Attributes:

Inherited from NodeMixin

`separator`	The `NodeMixin` class extends any Python class to a tree node.
`parent`	Parent Node.
`children`	All child nodes.
`path`	Path of this Node.
`ancestors`	All parent nodes and their parent nodes.
`anchestors`	All parent nodes and their parent nodes - see `ancestors`.
`descendants`	All child nodes and all their child nodes.
`root`	Tree Root Node.
`siblings`	Tuple of nodes with the same parent.
`leaves`	Tuple of all leaf nodes.
`is_leaf`	Node has no children (External Node).
`is_root`	Node is tree root.
`height`	Number of edges on the longest path to a leaf Node.
`depth`	Number of edges to the root Node.

Public Methods:

`__init__`(name, parent, Aresid, Bresid, ...)	Class constructor
`size`()	Returns node size (total no.
`calculate_UB`([t])	Returns an upper bound for the specific node.
`calculate_LB`()	Returns a lower bound for the current search tree node.
`__lt__`(other)	A special methods used to break ties (if LBs are equal) -- randomly.

Inherited from NodeMixin

iter_path_reverse()

Iterate up the tree from the current node.

Private Data Attributes:

Inherited from NodeMixin

`_NodeMixin__children_or_empty`
`_path`

Private Methods:

Inherited from NodeMixin

`_NodeMixin__check_loop`(node)
`_NodeMixin__detach`(parent)
`_NodeMixin__attach`(parent)
`_NodeMixin__check_children`(children)
`_pre_detach_children`(children)	Method call before detaching children.
`_post_detach_children`(children)	Method call after detaching children.
`_pre_attach_children`(children)	Method call before attaching children.
`_post_attach_children`(children)	Method call after attaching children.
`_pre_detach`(parent)	Method call before detaching from parent.
`_post_detach`(parent)	Method call after detaching from parent.
`_pre_attach`(parent)	Method call before attaching to parent.
`_post_attach`(parent)	Method call after attaching to parent.

calculate_LB()[source]: Returns a lower bound for the current search tree node.

calculate_UB(t='fast')[source]: Returns an upper bound for the specific node.

size()[source]: Returns node size (total no. of nodes in both diagrams).

❖❖❖

Functions

BB_search.LB_by_level(A, B)[source]

LB: Inversions-driven heuristic.

The one based on the lemma presented in the paper.

BB_search.LB_by_level_complicated(A, B)[source]: LB: Another variant of the inversions-driven heuristic (improved)

BB_search.LB_current(A, B)[source]: LB: current size (before the alignment).

BB_search.LB_first_aligned(A, B)[source]: LB: min current size after aligning the first element only.

BB_search.LB_last_aligned(A, B)[source]: LB: min current size after aligning the last element (enumeration).

BB_search.LB_lvl_compl_symm(A, B)[source]: LB: Symmetric version of the previous one.

BB_search.LB_lvl_symm(A, B)[source]: Symmetric version of the LB_by_level().

BB_search.nodeattrfunc(node)[source]: Helper: Generates node attributes for graphviz export.

BB_search.nodenamefunc(node)[source]: Helper: Generates node names for graphviz export.