CONVEXCOUNT
-----------

This, CONVEXCOUNT, is the first piece of software associated with the 
paper "A note on convex characters, Fibonacci numbers and exponential-time 
algorithms", by Kelk et al.

For a given (unrooted) binary input tree the code counts, samples and 
lists convex characters where each state occurs on at least k taxa.

The other piece of software associated with the paper (CONVEXMPDIST), 
which can be used to compute maximum parsimony distance, can be found at

	http://skelk.sdf-eu.org/convexmpdist/

RUNNING THE CODE
----------------

You will need Java to be installed on your computer (these days it is 
automatically installed on most platforms).

To use the already-compiled .jar file, simply type (for example):

java -jar ConvexCount.jar < tree.txt

The output should look something like this:

	$ java -jar ConvexCount.jar < tree.txt
	// Taxa in tree: 9
	// Only considering convex characters where each state has at least 1 
	taxa.
	// Total characters = 1597

If no command-line options are specified then the code simply counts the 
number of convex characters on the input tree. The input tree here has
9 taxa, so (as expected) the number of characters is equal to the 
((2*9)-1)th Fibonacci number i.e. F(17) = 1597.

Note that, although characters are oblivious to the presence or absence of 
a root, the Newick that you feed to the software should be 'rooted'. That is,
at the top level of the parantheses there should be 2 children, not 3. So, if your tree has the
form (A,B,C) this should be recoded for example as (A,(B,C)). This does 
not alter the results in any way.

COMPILING THE CODE
------------------

To compile the code from scratch, you'll need to have both the Java 
Development Kit and the JavaCC parser software (used for parsing
the input trees) installed on your system.

Once installed type,

javacc ConvexCount.jj
javac ConvexCount.java

Then you can run the software by typing,

java ConvexCount < tree.txt

COMMAND-LINE OPTIONS
--------------------

If you add -help as a command-line option you will see the following.

	$ java ConvexCount -help
	java ConvexCount [options] < treeFile.txt
	-----------------------------------------
	Options:
	-help : displays this message.
	-k [arg] : consider only convex characters in which each state occurs on 
	at least [arg] taxa. If not specified, k defaults to 1.
	-list : list all the convex characters in which each state occurs on at 
	least k taxa.
	-sample [arg] : generate u.a.r. [arg] convex characters in which each 
	state occurs on at least k taxa. If [arg] is set to -1, an infinite number 
	of samples are generated.
	-spectrum : generate the g_k spectrum for this tree.

Here are a few examples. 

The files tree.txt and tree2.txt correspond to the two trees shown in 
Figure 2 in the paper. The paper claims that they have different g_3 
values, so let's test this. First we analyse tree2.txt :

	$ java -jar ConvexCount.jar -k 3 -list < tree.txt
	// Taxa in tree: 9
	// Only considering convex characters where each state has at least 3 
	taxa.
	// Total characters = 5
	// Generating all the characters!
	1: {{a,b,c},{d,e,f},{g,h,i}}
	2: {{a,b,c,d,e,f},{g,h,i}}
	3: {{d,e,f,g,h,i},{a,b,c}}
	4: {{a,b,c,g,h,i},{d,e,f}}
	5: {{a,b,c,d,e,f,g,h,i}}

Next we analyse tree2.txt:

	$ java -jar ConvexCount.jar -k 3 -list < tree.txt
	// Taxa in tree: 9
	// Only considering convex characters where each state has at least 3 
	taxa.
	// Total characters = 6
	// Generating all the characters!
	1: {{a,b,c},{d,e,f},{g,h,i}}
	2: {{a,b,c},{d,e,f,g,h,i}}
	3: {{a,b,c,d},{e,f,g,h,i}}
	4: {{a,b,c,d,e},{f,g,h,i}}
	5: {{a,b,c,d,e,f},{g,h,i}}
	6: {{a,b,c,d,e,f,g,h,i}}

As claimed in the article, the first tree has g_3 = 5 and the second tree 
has g_3 = 6.

This can also be seen by generating the spectrum of each tree, which is 
simply the vector of values g_i for 1 <= i <= n where n is the number of 
taxa.

	$ java -jar ConvexCount.jar -spectrum < tree.txt
	// Taxa in tree: 9
	// Generating g_k spectrum for this tree.
	1597, 21, 5, 1, 1, 1, 1, 1, 1

	$ java -jar ConvexCount.jar -spectrum < tree2.txt
	// Taxa in tree: 9
	// Generating g_k spectrum for this tree.
	1597, 21, 6, 3, 1, 1, 1, 1, 1

Let's confirm that the tree from Figure 1 (figure1.txt) indeed has 8 
convex characters where each state appears on at least 2 taxa.

	$ java -jar ConvexCount.jar -k 2 -list < figure1.txt
	// Taxa in tree: 7
	// Only considering convex characters where each state has at least 2 
	taxa.
	// Total characters = 8
	// Generating all the characters!
	1: {{a,b},{c,d},{e,g,f}}
	2: {{a,b},{c,d,e},{g,f}}
	3: {{a,b},{c,d,e,g,f}}
	4: {{a,b,c},{d,e},{g,f}}
	5: {{a,b,c},{d,e,g,f}}
	6: {{a,b,c,d},{e,g,f}}
	7: {{a,b,c,d,e},{g,f}}
	8: {{a,b,c,d,e,g,f}}

Finally, let's u.a.r. sample 15 convex characters (out of a total of 
233) from this tree.

	$ java ConvexCount -k 1 -sample 15 < figure1.txt
	// Taxa in tree: 7
	// Only considering convex characters where each state has at least 1 
	taxa.
	// Total characters = 233
	// Sampling 15 characters u.a.r.
	79: {{b,d},{a},{e,f},{g},{c}}
	134: {{a,d},{b},{e,f},{g},{c}}
	143: {{a,d,e,g},{b},{f},{c}}
	6: {{a},{b},{c},{d,f},{g},{e}}
	78: {{b,d},{a},{e},{g,f},{c}}
	55: {{a,b},{c,e,g,f},{d}}
	21: {{a},{b},{c,e,g,f},{d}}
	61: {{a,b},{c,d,f},{g},{e}}
	51: {{a,b},{c,e},{g},{f},{d}}
	113: {{b,c,d},{a},{e,f},{g}}
	47: {{a,b},{c},{d,e,g,f}}
	50: {{a,b},{c,g,f},{e},{d}}
	80: {{b,d},{a},{e,g},{f},{c}}
	155: {{a,c},{b},{d,e,f},{g}}
	204: {{a,b,c},{d},{e,g,f}}

Note that it is sampling with replacement, so duplicates are possible.

MISCELLANEOUS
-------------

The files spectrum1.txt and spectrum2.txt contain two trees on 11 taxa 
that are non-isomorphic (in the unlabelled sense i.e. disregarding the 
taxa labels) but which do have the same spectrum:

10946, 55, 8, 3, 2, 1, 1, 1, 1, 1, 1

A picture of these two trees is shown in 
CounterExampleSpectrumConjecture.jpg. The files analysisSpectrum1.txt 
and analysisSpectrum2.txt list the 8,3,2 characters for g_3, g_4 and g_5 
respectively.

See the file

	proof_spectrum_conjecture_until_10taxa.txt

for a computational proof that up until 10 taxa the spectrum *does* 
uniquely specify the tree topology.

CONTACT
-------

For more information don't hesitate to contact me at my Maastricht 
University email address.

Kind regards,

Steven Kelk, 23rd July 2016