CONTENTS OF THIS FILE
---------------------

* Motivation
* Requirements
* Instructions
* Examples


Motivation
----------

This program implements the algorithms in:
[CPR15] G. Cardona, J-C. Pons, F. Rossello. A reconstruction problem for
a class of phylogenetic networks with lateral gene transfers. Submitted

Requirements
-------------

This program requires the python libraries networkx and pyparsing. 


Instructions
------------

Run the program with the python interpreter:
$ python recoverLGT.py

Then, enter the trees T, T’_1,…, T’_m that are the input to Algorithm 2:

1.  You must enter the eNewick strings of this set of trees to
    apply the Algorithm.
2.  First, enter the candidate to reduced principal subtree (T),
    and then each one of the candidates to reduced secondary
    subtree (T'_1, T'_2, ...).
3.  To stop entering secondary subtrees, give an empty string.

As output, the program can return:

 - The eNewick string of the restricted LGT network whose principal and 
   secondary subtrees are T and T_1,…,T_m (if it exists), or

 - A message specifying that a cycle has been found, or

 - A message of error if any of the conditions (a) to (f) in Proposition 8
   is not satisfied. 

Examples
--------

Next, we give a set of examples. The first three of them correspond to the 
examples in [CPR15].
 
Example 1:

T = ((1,2),((3,4),5));
T'_1= (1,(2,((3,4),5)));
T'_2= ((1,(2,3)),(4,5));
T'_3= (5,((1,2),(3,4)));

Example 2: 

T = (((1,2),3),(4,(5,6)));
T'1= (4,(3,(2,(1,(5,6)))));
T'2= (3,(4,(5,(6,(1,2)))));


Experiment in Section 5:

T=(((((9,8),7),6),5),((4,3),(1,2)));
T'1=(((((9,8),7),6),5),(((2,3),1),4));
T'2=(((((9,8),7),6),5),(((1,3),2),4));
T'3=((((((9,8),7),6),5),4),((3,(1,2))));


Other examples:

T= ((1,(2,3)),(4,((5,6),7)));
T'_1=(((1,(2,3)),(5,6)),(4,7));
T'_2=(1,(4,((2,3),(7,(5,6)))));
T'_3=(1,(((2,3),4),((5,6),7)));
T'_4=((1,(2,3)),((4,(5,6)),7));


T= (((((4,5),3),1,2),(((6,7),8),9)),10);
T'_1=(((1,2),((((4,5),3),(6,7),8),9)),10);
T'_2=((((3,4),1,2),((((6,7),8),5),9)),10);
T'_3=((((((4,5),3),1,2),((6,7),8)),9),10);
T'_4=((((((4,5),3),1,2),6),((7,8),9)),10);


T= ((((2,3),1),(4,5)),(6,7));
T'_1=(((4,5),1),((2,3),6,7));
T'_2=(((1,(2,3,5)),4),(6,7));
T'_3=((1,(5,(4,(2,3)))),(6,7));
T'_4=(((1,(2,3)),((4,7),5)),6);