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:
|
Implements the search tree. |
|
Implements search tree node. |
Implements functions (outside the classes above):
|
LB: Inversions-driven heuristic. |
|
LB: Another variant of the inversions-driven heuristic (improved) |
|
LB: current size (before the alignment). |
|
LB: min current size after aligning the first element only. |
|
LB: min current size after aligning the last element (enumeration). |
|
LB: Symmetric version of the previous one. |
|
Symmetric version of the |
|
Helper: Generates node attributes for graphviz export. |
|
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
- 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
- node_cand, cand_parent
node corresponding to the current candidate and its parent,
- Type
- 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
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).
- 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
andB
after aligning to the candidate (optimum ifstatus
=optimal
).
❖❖❖
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
- A, B
sequences to align,
- Type
- Ar, Br
not-yet-aligned parts of
A
andB
.- Type
- 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 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.
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.
❖❖❖
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_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_symm(A, B)[source]
Symmetric version of the
LB_by_level()
.