We define the length of a path in a tree as the sum of the lengths of its edges, rather than the number of edges on the path. As a result, the evolutionary distance between two present-day species corresponding to leaves $$i$$ and $$j$$ in a tree $$\mathcal{T}$$ is equal to the length of the unique path connecting $$i$$ and $$j$$, denoted $$d_{i, j}(\mathcal{T})$$.
Define a class DistanceMatrix that can be used to represent distance matrices. A distance matrix is a square symmetric matrix with diagonal elements equal to zero and positive off-diagonal elements. The initialisation method takes the same arguments as the numpy.array1 method. In case these arguments do not represent a valid distance matrix, a ValueError must be raised with the message invalid distance matrix. The class DistanceMatrix must support at least the following methods:
A static or class method loadtxt that can be used to read a distance matrix from a text file. The method takes the same arguments as the numpy.loadtxt2 method and must return an object of the class DistanceMatrix. The distance matrix in the text file must be formatted according to the specifications of the numpy.loadtxt3 method.
A method savetxt that can be used to write a distance matrix to a text file. The method takes a filename or file handle as a first argument and supports the same keyword arguments as the numpy.savetxt4 method. The distance matrix in the text file is formatted according to the specifications of the numpy.savetxt5 method.
Make sure the built-in function repr and str return string representations of objects of the class DistanceMatrix that are formatted as a list of lists (see example below).
Define a class UnrootedTree that can be used to represent unrooted trees whose nodes are uniquely labeled and whose edges are weighted with a floating point number. The initialisation method takes zero or more edges. Each edge is represented as a tuple $$(i, j, w)$$, with $$i$$ and $$j$$ the labels of the nodes connected by the edge and $$w$$ the edge weight. The class UnrootedTree must support at least the following methods:
A static or class method loadtxt that can be used to read an unrooted tree from a text file. The method takes the file name or the file handle of the text file. The text file must contain a description of an unrooted tree as an adjacency list. Each line contains the description of an edge $$(i, j, w)$$ in the tree: the label $$i$$, the symbols <->, the label $$j$$, a colon (:) and weight $$w$$. Node labels that contain only digits must be converted to integers, otherwise the node labels are considered as strings. Edge weights must be converted to floating point numbers. The method must return an object of the class UnrootedTree.
A method path that takes two node labels $$i$$ and $$j$$ and returns a list containing the labels of the unique path between $$i$$ and $$j$$ in the unrooted tree.
A method distance_matrix that returns a distance matrix (an object of the class DistanceMatrix) containing the pairwise distances between any pair of leaves in the unrooted tree. The rows and columns of the distance matrix correspond to the leaves of the unrooted tree, sorted in increasing order according to their unique label.
Make sure the built-in function repr returns string representations of objects of the class UnrootedTree that are formatted according to the example given below.
In the following example we assume the text files distances.txt6 and edges.txt7 to be located in the current directory.
>>> D = DistanceMatrix([[0, 13, 21, 22], [13, 0, 12, 13], [21, 12, 0, 13], [22, 13, 13, 0]]) >>> D DistanceMatrix([[0, 13, 21, 22], [13, 0, 12, 13], [21, 12, 0, 13], [22, 13, 13, 0]]) >>> print(D) [[0, 13, 21, 22], [13, 0, 12, 13], [21, 12, 0, 13], [22, 13, 13, 0]] >>> D = DistanceMatrix.loadtxt('distances.txt') >>> D DistanceMatrix([[0.0, 13.0, 21.0, 22.0], [13.0, 0.0, 12.0, 13.0], [21.0, 12.0, 0.0, 13.0], [22.0, 13.0, 13.0, 0.0]]) >>> D.savetxt('copy.txt', fmt='%g') >>> print(open('copy.txt').read().rstrip()) 0 13 21 22 13 0 12 13 21 12 0 13 22 13 13 0 >>> tree = UnrootedTree((0, 4, 11), (1, 4, 2), (2, 5, 6), (3, 5, 7), (4, 5, 4)) >>> tree UnrootedTree((0, 4, 11.0), (1, 4, 2.0), (2, 5, 6.0), (3, 5, 7.0), (4, 5, 4.0)) >>> tree.path(0, 2) [0, 4, 5, 2] >>> tree.path(1, 3) [1, 4, 5, 3] >>> tree = UnrootedTree.loadtxt('edges.txt') >>> tree UnrootedTree((0, 4, 11.0), (1, 4, 2.0), (2, 5, 6.0), (3, 5, 7.0), (4, 5, 4.0)) >>> tree.distance_matrix().savetxt('distances.txt', fmt='%g') >>> print(open('distances.txt').read().rstrip()) 0 13 21 22 13 0 12 13 21 12 0 13 22 13 13 0