EXTERNAL LOOP:
~~~~~~~~~~~~~
IF --besttree, --bestsimple or --bestgreedy specified
THEN
let N be the best network obtained by the relevant subroutine
ELSE
let N be the result of running the MAIN ALGORITHM.
ENDIF
- Compute stats for N, display some pre post-processing results
- Mild post-processing on N, unless all post-processing switched off. (This involves
repeatedly contracting edges with neither endpoint a reticulation, where this does not damage
triplet consistency)
- Radical post-processing of N, but ONLY if radical post-processing switched on (and
post-processing has not been totally disabled). This involves executing the
following loop:
SD-min loop:
Keep deleting edges until that doesn't reduce SD anymore
Keep contracting edges until that doesn't reduce SD anymore
Go back to Loop for as long as something is deleted or contracted
- List surplus/missing triplets if the user has requested this information
- Display final network (DOT/eNewick)
- Print final stats
FINISHED
-----------------------------------------------------------------------------------------------
The MAIN ALGORITHM consists of running the following MAIN LOOP until we are finished. The high-level
description of the MAIN LOOP is: { try Aho, if that fails try the polytime J&S algorithm, if that
fails then use the J&S "5/12" scoring function. Compute a good simple level-1 network for the triplets
induced by the partition, and (if possible) a good tree, if the tree is better use the tree, otherwise
use the simple level-1 network }.
MAIN LOOP:
1) CHOOSE THE PARTITION
-----------------------
- IF --forcemaxsn is TRUE, use the max SN-sets as a partition, DONE;
ELSE
IF Aho graph is not connected THEN return a 2-block partition
where one of the blocks is equal to one of the connected
components in the Aho graph, and the other is equal to
the remaining leaves, DONE
ELSE
IF we are allowed to look for local perfection (i.e. --noperfection is false) THEN
look at the max SN-sets of the set: if they
form a genuine partition of the leaves
-and- the induced set of triplets is dense
-and- they are 100% consistent with some
level-1 network -then- we found local perfection: use
the max SN-sets as the partition! DONE
ELSE
Use the J&S "5/12" scoring function to choose
a partition (up to the maximum number of
blocks allowed), DONE
2) DECIDE WHAT TO DO WITH THE PARTITION
---------------------------------------
- IF the partition contains only two blocks, then we're done because we introduce a
tree vertex (i.e. indegree 1, outdegree 2) and we recurse inside the blocks
ELSE
- Induce a set of triplets on the partition
- IF we were allowed to look for local perfection and we found it
THEN
introduce a simple level-1 network (constructed using the J&S algorithm) consistent with 100% of the induced triplets, and recurse inside the blocks, done
ELSE
- IF the number of leaves in the induced triplet set is not
above the --simmax thresshold
THEN
use the exponential-time best simple level-1 algorithm
ELSE
use the greedy simple level-1 algorithm
- IF the number of leaves in the induced triplet set is not above
the --wumax threshhold,
THEN
use Wu's exponential-time algorithm to get the best
Introduce the computed simple level-1 network UNLESS we also ran
Wu's algorithm and it was better than the computed simple level-1
algorithm. Recurse inside the blocks, DONE.