Skip to main content

Table 1 :

From: Reconstructing phylogenies from noisy quartets in polynomial time with a high success probability

Q-RAND(S, Q):

1.

Randomly select a quartet topology in Q as the initial phylogeny T;

2.

Delete the four taxa of T from the taxon set S;

3.

Randomly select a taxon s from S;

4.

Locate a separator v of T;

5.

Randomly select a taxon from each sub-phylogeny of T - {v}, say s a , s b , and s c ;

6.

Decide which sub-phylogeny of T - {v} taxon s should be inserted into based on the quartet topology for {s a , s b , s c , s};

7.

If the located sub-phylogeny has only one edge,

7.1.

   Insert s on that edge and let the new phylogeny be T;

8.

Else,

8.1.

   Merge the other two sub-phylogenies as a super taxon (which replaces v);

8.2.

   Let the located sub-phylogeny with the super taxon be the new current phylogeny T;

8.3.

   Go back to Step 4;

9.

Delete taxon s from S;

10.

If S is not empty,

10.1.

   Go back to Step 3;

11.

Else,

11.1.

   Output the phylogeny T.