Phylogeny inference lab 2

This is practice building parts that you will need for the assignment.

Binary Tree classes

Make Java classes suitable for phylogenetic trees. In these trees, the leaves represent observed taxonomic units (OTUs). There will always be at least one leaf. Let's say there are n leaves. The internal nodes represent hypothetical taxonomic units (HTUs). There will always be exactly n-1 of them. Each internal node has exactly two children, although the order of the children does not matter.

You will need:

1. An abstract TU_Tree class. You will find that each node except the very top one will need a parent. If n=1 the top node will be an OTU, otherwise it will be an HTU. If a node has a parent, the parent will be an HTU.
2. An HTU_Node class, having two children, each of which might be either an OTU_Node or an HTU_Node.
3. An OTU_Node class, which needs something to record exactly which of many observed taxonomic units it represents. That might as well be some kind of integer.

You will need some way to print a tree. The first handout has a section on Newick format. This might as well be the definition of the usual Java toString() method.

You will want to be able to create trees, maintaining the invariant that if p has a left or right child c then p is c's parent.

The full thing

We need more than just a tree. We need to be able to choose a node of a tree at random. So we want something that contains both a TU_Tree and an array (or perhaps an ArrayList) of references to the nodes of the tree. So

1. A Phylogeny class, having a TU_Tree member and an array or ArrayList member.

The operations we want on these objects are

• Create a Phylogeny containing an OTU for species 1.
• Report the size of the Phylogeny (the number n).
• Return the toString() value of the TU_Tree.
• Given a node number 0 < i < 2n-2 insert a new node for OTU n+1 by turning

        parent
           |
        node-i
  

  into

        parent
          |
        new-HTU
        /   \
      node-i new-OTU
  

  Use these classes in a simple program

  Use these classes in a program that generates random trees with 10 OTUs and prints them.

  Revise bitwise operations

  Find your Java textbook or other Java documentation and review the bitwise operators |, &, and <<. Suppose we wanted to represent a subset of the integers 0..30 by an integer, where k is in the set if and only if bit k of the integer is 1 (counting the least significant bit as bit 0).

  1. What operator would you use for set union?
  2. What operator would you use for set intersection?
  3. How would you make the set {3,8,14}?

  Add the Fitch algorithm

  Add the Fitch algorithm to your classes. Each OTU will need some characters. Add the character matrix to Phylogeny.

  To keep it simple, write your Fitch algorithm method to take a character index as its argument, and work on just that character.

  Here's a nasty problem for Java programmers: you have to return two pieces of information from each call to the Fitch algorithm. How do you do that? Considering the existence of modern processors like the SPARC T2000 which can do 64 things at once, why wouldn't you want to do this by stuffing things into OTU_Nodes and HTU_Nodes?