Python!!!!!!!!!!!!!

a class Tree. This should have at least the attributes listed below, together with the appropriate methods for accessing them:

_name or _id: the name of the node. For leaf nodes, this should be the ID of the corresponding organism. For non-leaf nodes, one simple way to indicate that the node is not a leaf is to set this attribute to None.

_left and _right: references to the left and right subtrees of the node.

Additionally, you may want to have an attribute at each node giving the set of IDs of all of the leaf nodes "under" that node: this can be useful when computing the similarity between two trees. This is not a requirement, just a suggestion.

Put the code implementing this class in a file tree.py. You will have to import this code into your program using something like

from tree import *

Use a list comprehension to compute the list of N-grams for each genome sequence (make sure that the last few elements of this list are not shorter than the value of N specified). (You can obtain a set of N-grams by applying set() to this list.)

Use a dictionary to map pairs of organism IDs to the similarity between those organisms.

To facilitate grading, set the children of each non-leaf node in the phylogenetic tree as as follows. During the iterative construction of the tree, when you combine two trees t1 and t2 as subtrees of a new tree node, if str(t1) < str(t2)then t1 should be the left child; otherwise t2 should be the left child of the new node.

with using ::

def __str__(self): if self.is_leaf(): return self.id() else: return "({}, {})".format(str(self.left()), str(self.right()))

Here the method is_leaf() returns True if and only if the tree node it is invoked on is a leaf node; and id(), left(), and right() return, respectively, the ID of the node and the left and right subtrees of the tree node.