content/08_phylogenetic_trees/phylogenetic_trees.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Representing Phylogenetic Trees Using Python Classes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Phylogenetic Trees  succinctly represent life's diversity\n",
    "\n",
    "The only diagram in Darwin's *On the Origin of Species* was a tree, so we know they're important. Why is this particular representation so crucial to biology? Biologists turn to phylogenetic trees for several reasons. One is that life's diversity is so vast that for many practical applications it is crucial to have a sensible way to refer to whole groups of organisms that tend to share many traits. \n",
    "\n",
    "#### Trees classify life's mind-bending diversity.\n",
    "As early as we have records, humans have always been fascinated by life's diversity. More than 35,000 years ago an artist in Makassar, Indonesia was already painting babirusa ('deer-pigs') on the walls of a [cave](https://en.wikipedia.org/wiki/Caves_in_the_Maros-Pangkep_karst) that you can still see today M. [1]. Yet the nature of life is such that it is very difficult to speak of living things without categories to put them in. In conversation, we might refer casually to 'bees', and expect listeners to understand what we are talking about. Yet there are more than 4000 species of bees in the United States alone. Even amongst experts, there are probably very few if any who could recall all of them without error. \n",
    "\n",
    "Taxonomists address this issue by dividing life's diversity into named groups or taxa. [Carl Linnaeus](https://en.wikipedia.org/wiki/Carl_Linnaeus) is perhaps the most famous taxonomist - he proposed the system of *binomial nomenclature* of a capitalized genus name (e.g. *Homo*) followed by a lower case species name (*sapiens*), and organized living things into taxonomic ranks based on shared traits. Linnaeus' taxonomic classifications were hardly perfect - he placed whales with fish, for example. Yet his systematic approach allowed subsequent generations of taxonomists to continue to improve on the general scheme. However, at the time Linnaeus developed this system, the mechanisms by which biological diversity is generated were not understood. Linnaeus' system was a convenient way to classify similar organisms together, based on shared traits, but why traits should happen to be shared in nested fashion -- why, for example, there are no mammals with scales nor snails with feathery wings --  was mysterious.\n",
    "\n",
    "One of the key contributions of Darwin's idea that biological diversity could be explained by a tree of life is that it provides a mechanistic explanation for why we see nested trait variation in nature. While all cellular organisms share common ancestors, some pairs of organisms (like some tips on a tree) split apart much earlier than others. So in Darwin's tree organisms with many shared traits (like wolves and dogs) are thought to do so because they split from one another only recently in life's history, whereas those with very few shared traits (like wolves and slime moulds) likely split from one another a very long time ago indeed.\n",
    "\n",
    "In modern bioinformatics, trees are used not just to represent the diversity of species, but also the diversity of other evolving entities. For example, genes in a genome can also be represented by a *gene tree*. Such trees show, for example, that the genes encoding receptor proteins that sense sex hormones like estrogen and androgen are much more related to one another than, say, the gene for alcohol dehydrogenase, which breaks down alcohol.\n",
    "\n",
    "Let's take a deeper dive into Darwin's Tree of Life and how we can represent it in python."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    " \n",
    "\n",
    "<img src=\"./resources/tree_of_life.png\" width=\"250\" style=\"margin:0px 25px\"  description=\"An upward-looking view of a tree from Hawaii set against a blue sky. The trunck and branches twist as they head upwards before spreading out in a bright green canopy\"> \n",
    "\n",
    "## Darwin's Tree of Life\n",
    "\n",
    "In Darwin's metaphor of a tree of life, we are asked to imagine a physical tree. The tips of each of its branches represent one living species. The points where two tips join together represent the last ancestor that two living species shared before they broke apart or *speciated* into two different species. The root of the tree (in this metaphor there is a single root) represents the common ancestor of all the different species in the tree.\n",
    "\n",
    "This metaphor has proven to be an extremely compact and useful representation of the relationships amongs evolving entities, inclusing both organisms and the genes they carry. However, it is worth noting that as with any techique phylogenetic trees have limitations. For example, they cannot easily represent more complex networks of relationships among populations, hybridization between species, or horizontal gene transfer of genes among unrelated species. Despite these limitations, trees are everywhere in bioinformatics and can be extremely powerful tools for understanding biology.\n",
    "\n",
    "## Parts of a Tree\n",
    "\n",
    "#### Nodes and edges. \n",
    "\n",
    "Phylogenetic trees have two main parts: **nodes** and the **branches** that connect them. Several terms apply to these parts.\n",
    "\n",
    "<img src=\"./resources/tips_nodes_branches_root.png\" width=\"1000\" style=\"margin:0px 25px\" description=\"A tree diagram illustrating nodes, the branches that connect them, and labeling each part of the tree according to its definition. The definitions are given in text form below.\"> \n",
    "\n",
    "* The **children** of a node represent the nodes that descend *directly* from that node by a single branch.\n",
    "* The **parent** of a node is the node from which that node directly descends. Parent nodes are connected to their children by a single node.\n",
    "* The **descendants** of a node represent all the nodes that descend from a node, by one or more branches.\n",
    "* The **ancestors** of a node represent all the nodes from which a node descends, by one or more branches. Effectively, these are all the nodes \"further back\" in the tree.\n",
    "\n",
    "* The nodes representing living species that have no children are called **tips**. So, for example, *Homo sapiens* is a tip node on the tree of life. \n",
    "* Nodes that have children are called **internal nodes**. (This is the opposite of a tip node).\n",
    "* The common ancestor of all tips on a tree is the **root** of the tree. By definition, the root of a tree has no parent on that tree.\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Classes in Python\n",
    "Let's figure out how to represent a phylogenetic tree in python. To do so we'll need to learn more about objects and classes in python.\n",
    "\n",
    "#### Everything is an object\n",
    "In python, virtually everything we've encountered so far - integers, lists, dictionaries, etc - is represented as an object. Objects in python have two main kinds of features:\n",
    "* properties - these are information stored by the object. They are accessed by using the name of the object, a period (.), and then the name of the property.\n",
    "* methods - these are things the object can do. More specifically, they are like functions that are associated with each objects. \n",
    "\n",
    "Here are some properties and methods from objects you've already seen: \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Here is __class__, a property of our greeting string:\n",
      "<class 'str'>\n",
      "Here is a method called upper that belongs to our greeting string:\n",
      "<built-in method upper of str object at 0x10da52430>\n",
      "HELLO WORLD!\n"
     ]
    }
   ],
   "source": [
    "greeting = \"Hello World!\"\n",
    "\n",
    "print(\"Here is __class__, a property of our greeting string:\")\n",
    "#We access the property with a . after the name of our object\n",
    "print(greeting.__class__)\n",
    "\n",
    "print(\"Here is a method called upper that belongs to our greeting string:\")\n",
    "#We access the method itself with a . after the name of our object\n",
    "print(greeting.upper)\n",
    "#Note that this doesn't call the upper case method!\n",
    "\n",
    "#Here's how we would actually use the upper method (note the parentheses after upper):\n",
    "print(greeting.upper())\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Representing phylogenetic trees using python classes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's figure out how to represent a phylogenetic tree using python classes. A key insight into how to do so is to realize that we needen't represent the entire tree as a class. Instead, we can think of the whole tree as a collection of many nodes that happen to link together. Thus, our problem can be reduced to how to represent a single *node* on a phylogenetic tree using a python class. We can then use that class definition as a blueprint to make the many nodes that compose the tree and link them together in the right way to represent the relationships shown in the tree.\n",
    "\n",
    "<img src=\"./resources/tree_of_life_blueprint.jpg\" width=\"250\" style=\"margin:25px 25px\" description=\"A version of the tree image from before, but styled to look like a blueprint. Text reads: Plans for one node on a phylogenetic tree. Schematics show a branch point on the tree marked 'Node', with arrows coming from it and pointing to two other nodes marked children. An arrow from a node marked 'Parent' points at the node\">\n",
    "\n",
    "The blueprint to the left shows the main types of information that each node object needs to have to represent part of a phylogenetic tree. Each node should have a **parent node**, and some **child** nodes. We will have to decide if we want each node to have exactly two children (as shown on the blueprint to the left) or to allow more than one child per node. \n",
    "\n",
    "In the literature, trees where every non-tip node has exactly two children are called **strictly bifurcating**. Working with **strictly bifurcating** trees simplifies some algorithms, but not all trees meet this property. A place on a non-strictly bifurcating tree where a node has three or more children is called a **polytomy**. Polytomies can occur in nature- for example if a population of organisms split into three subpopulations all at once and subsequently speciated. More often, however, they arise because the exact order of relationships can't be determined.\n",
    "\n",
    "\n",
    " \n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The simplest possible class definition \n",
    "\n",
    "\n",
    "We're going to quickly build up to doing some reasonably sophisticated simulations of evolution using trees. But before we get to that, we'll need to build up a workable tree node object in stages. To start, let's define the simplest class object possible. It *really* won't do a lot yet, so I'll call it a BoringNode"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Define the blueprint for a BoringNode object \n",
    "#(but don't make one yet!)\n",
    "\n",
    "class BoringNode():\n",
    "    \"\"\"A node on a phylogenetic tree\"\"\"\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It doesn't get much simpler than that! Let's analyze this very short piece of code. What are some features of the code defining this class?\n",
    "\n",
    "- Like all class definitions the code starts with the keyword class\n",
    "- The name we want to give the class (PhyloNode) comes next\n",
    "- By convention, classes with multiword names use an initial uppercase letter for each word and no underscores. This gives an easy hint as to which names are names of functions (those use snake_case) and which are classes (those use UpperCamelCase or PascalCase). \n",
    "- The parentheses after PhyloNode have special meaning: they are used if using another class as a template for the class (**class inheritance**). We'll discuss this later but since we don't use this important feature of classes here we just leave the parenthesis empty.\n",
    "- After the parentheses we have a colon, and all subsequent code that is part of the class is indented an extra level. Right now the class definition doesn't contain anything.\n",
    "\n",
    "#### Taking our placeholder BoringNode object for a spin\n",
    "\n",
    "Classes in python serve as blueprints for objects. Let's try this out by actually using our placeholder PhyloNode blueprint to make a couple of PhyloNode objects. We'll then test if they are the same or not to illustrate that a single class definition can make multiple distinct and different objects - just like the blueprint for a house can be used over and over again to build similar houses."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Is node1 the same thing as node2?  False\n",
      "What type of object is node1? <class '__main__.BoringNode'>\n"
     ]
    }
   ],
   "source": [
    "#Actually build two phylogenetic nodes from our blueprint\n",
    "node1 = BoringNode()\n",
    "node2 = BoringNode()\n",
    "print(\"Is node1 the same thing as node2? \", node1 is node2)\n",
    "\n",
    "print(\"What type of object is node1?\", type(node1))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "<img src=\"./resources/two_boring_nodes.png\" width=\"175\" style=\"margin:25px 25px\" description=\"Two rather boring nodes\" > \n",
    " \n",
    "Well, as promised in the class name, this BoringNode class isn't so exciting yet. But at least we've created an empty and not very interesting blueprint, and shown that we can use it to make objects. If we ask python about the type of one of these objects, it will tell us it is a BoringNode object. Although we've only defined the class once, we've proven that the objects it creates are distinct (node1 is node2 returned False, showing these nodes are saved separately in memory). \n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It turns out that even our minimal class definition is enough to allow python's built in help() function to give users help on our object. In addition to some generic properties common to all objects, you'll see "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "What happens if I call help(PhyloNode)?\n",
      "Help on class BoringNode in module __main__:\n",
      "\n",
      "class BoringNode(builtins.object)\n",
      " |  A node on a phylogenetic tree\n",
      " |  \n",
      " |  Data descriptors defined here:\n",
      " |  \n",
      " |  __dict__\n",
      " |      dictionary for instance variables (if defined)\n",
      " |  \n",
      " |  __weakref__\n",
      " |      list of weak references to the object (if defined)\n",
      "\n"
     ]
    }
   ],
   "source": [
    "print(\"What happens if I call help(PhyloNode)?\")\n",
    "help(type(node1))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Most of this is generic boilerplate describing common properties of objects. But the first line \"A node on a phylogenetic tree\" matches the documentation string we put under our class definition. Thus, these docstrings are a key way to communicate to users (including yourself after you haven't looked at your code in six months) what the class is and how it works."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## An artisinal hand-crafted tree\n",
    "Let's start by making a PhyloNode class and using it to represent a very simple tree consisting of a parent node with two children. Our tree will be artisinally crafted - like an expensive cheese - in the sense that we will issue specific commands to join together the nodes to form the tree. Later we will consider how to grow an entire tree automatically using a simulated birth/death model. \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### The \\__init\\__ function\n",
    "\n",
    "A key element in the definition of a useful class is its initialization function. This is a function that will be classed when an instance of the class is created. It usually helps set up key parameters for the class. If our class represented a character in a video game, it's init function might set up the character's initial location, health, etc. For our phylogenetic tree objects, our initialization function will set up our nodes children and parent nodes, as well as storing information about the name of the node.\n",
    "\n",
    "In python the name of the function that sets up an object based on a class definition is called __init__ (that is, the word init with two underscores on either side).\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "class PhyloNode():\n",
    "    \"\"\"A node on a phylogenetic tree\"\"\"\n",
    "\n",
    "    def __init__(self,children=None,parent=None,\\\n",
    "      name = None):\n",
    "      \"\"\"Initiate a node on a phylogenetic tree\n",
    "      children -- a list of PhyloNode objects\n",
    "        descending immediately from this node\n",
    "      name -- a string for the name of the node\n",
    "      parent -- a single PhyloNode object for the parent\n",
    "      \"\"\"\n",
    "      self.Name = name\n",
    "      self.Children = []\n",
    "      if children:\n",
    "        self.Children.extend(children)\n",
    "      self.Parent = parent"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### The special *self* variable\n",
    "\n",
    "Python methods make use of a special 'self' variable that refers to the object itself (rather than the general class that it is a member of). When a python method is called (e.g. greeting.upper()) the first argument to the method function is automatically set to be a reference to the object. This special reference to the particular object is called **self**.\n",
    "\n",
    "This may seem very confusing at first, but see how it works in the above example. Because we have a reference to the new node we are creating bound into a variable name, we can now easily set the different properties of that new object by saying things like self.Name = name (where lowercase name is supplied by the user for each object).\n",
    "\n",
    "We can now make new tree nodes like this:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "root = PhyloNode(name=\"root\")\n",
    "A = PhyloNode(name=\"A\",parent = root)\n",
    "B = PhyloNode(name=\"B\",parent = root)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This produces a tree that looks roughly like this:\n",
    "\n",
    "<img src=\"./resources/rooted_tiny_tree.png\" width=\"175\" style=\"margin:25px 25px\" description=\"A tiny tree consisting of a root node and two descendants: A and B.\" > \n",
    "\n",
    "We can now start to reason about the tree (at least a little bit) using the small amount of information we've encoded in our 3 PhyloNode objects so far:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "What is the parent of A? <__main__.PhyloNode object at 0x107a803c8>\n",
      "What is the name of the parent of A? root\n",
      "What is the name of the parent of B? root\n"
     ]
    }
   ],
   "source": [
    "print(\"What is the parent of A?\", A.Parent)\n",
    "print(\"What is the name of the parent of A?\", A.Parent.Name)\n",
    "print(\"What is the name of the parent of B?\", B.Parent.Name)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Connecting parent nodes to their children after they are created.\n",
    "\n",
    "Let's further test our tiny tree. Try printing the children of the root node. Before you do, what answer should the code output? What does it output?\n",
    "<br><br><br>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The Children of the root node are: []\n"
     ]
    }
   ],
   "source": [
    "print(\"The Children of the root node are:\",root.Children)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Although we specified (via the parent = root parameter) that A and B both have root as a parent, we've never specified that A and B are it's children. We couldn't do that when we created the root, since A and B didn't exist yet at that time! We need a way to add children to a node after it is created. Let's add a addChild() class method to PhyloNode to do this. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "class PhyloNode():\n",
    "    \"\"\"A node on a phylogenetic tree\"\"\"\n",
    "\n",
    "    def __init__(self,children=None,parent=None,\\\n",
    "      name = None):\n",
    "      \"\"\"Initiate a node on a phylogenetic tree\n",
    "      children -- a list of PhyloNode objects\n",
    "        descending immediately from this node\n",
    "      name -- a string for the name of the node\n",
    "      parent -- a single PhyloNode object for the parent\n",
    "      \"\"\"\n",
    "      self.Name = name\n",
    "      self.Children = []\n",
    "      if children:\n",
    "        self.Children.extend(children)\n",
    "      self.Parent = parent\n",
    "    \n",
    "    def addChild(self,child):\n",
    "        \"\"\"Attach a child node\"\"\"\n",
    "        if child not in self.Children:\n",
    "            self.Children.append(child)\n",
    "        child.Parent = self"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can now use this new method to fix the problem we detected with A and B not being children of the root. Notice that the addChild method takes two parameters - self and child - but only one will be supplied by the user. The other (self) will be automatically added when we call the method."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "root = PhyloNode(name=\"root\")\n",
    "A = PhyloNode(name=\"A\",parent = root)\n",
    "root.addChild(A)\n",
    "B = PhyloNode(name=\"B\",parent = root)\n",
    "root.addChild(B)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can now test if the previous code works:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The Children of the root node are: [<__main__.PhyloNode object at 0x107a93668>, <__main__.PhyloNode object at 0x107a80358>]\n"
     ]
    }
   ],
   "source": [
    "print(\"The Children of the root node are:\",root.Children)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Great! We now have references to the two children of the root node in a list. Note that it is a reference to the *children themselves* (not for example their Name variables) that gets added to the child list"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Testing whether nodes are tips or the root using our PhyloNode object\n",
    "\n",
    "Knowing which nodes are tips or roots ends up being important for many algorithms on trees. By the definitions for **tips** and **roots** given above, tips are nodes without children, and the root is a node without a parent. Let's add some additional methods to our PhyloNode object to be able to test whether nodes are tips or roots."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "class PhyloNode():\n",
    "    \"\"\"A node on a phylogenetic tree\"\"\"\n",
    "\n",
    "    def __init__(self,children=None,parent=None,\\\n",
    "      name = None):\n",
    "      \"\"\"Initiate a node on a phylogenetic tree\n",
    "      children -- a list of PhyloNode objects\n",
    "        descending immediately from this node\n",
    "      name -- a string for the name of the node\n",
    "      parent -- a single PhyloNode object for the parent\n",
    "      \"\"\"\n",
    "      self.Name = name\n",
    "      self.Children = []\n",
    "      if children:\n",
    "        self.Children.extend(children)\n",
    "      self.Parent = parent\n",
    "    \n",
    "    def addChild(self,child):\n",
    "        \"\"\"Attach a child node\"\"\"\n",
    "        if child not in self.Children:\n",
    "            self.Children.append(child)\n",
    "        child.Parent = self\n",
    "    \n",
    "    def isTip(self):\n",
    "      \"\"\"Return True if the node is a tip\"\"\"\n",
    "      if not self.Children: #false if Children is None or []\n",
    "        return True\n",
    "      else:\n",
    "        return False\n",
    "\n",
    "    def isRoot(self):\n",
    "      \"\"\"Return True if the node is the root of the whole tree\"\"\"\n",
    "      if not self.Parent:\n",
    "        return True\n",
    "      else:\n",
    "        return False\n",
    "\n",
    "    \n",
    "#Build our simple tree\n",
    "root = PhyloNode(name=\"root\")\n",
    "A = PhyloNode(name=\"A\",parent = root)\n",
    "root.addChild(A)\n",
    "B = PhyloNode(name=\"B\",parent = root)\n",
    "root.addChild(B)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Testing out our isTip and isRoot methods\n",
    "\n",
    "Now  test these new functions out. Try to find examples where isTip should return either True or False."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Is node A a tip? True\n",
      "Is node A the root? False\n",
      "Is the root node a tip? False\n",
      "Is the root node really the root? True\n"
     ]
    }
   ],
   "source": [
    "print(\"Is node A a tip?\", A.isTip())\n",
    "print(\"Is node A the root?\", A.isRoot())\n",
    "print(\"Is the root node a tip?\", root.isTip())\n",
    "print(\"Is the root node really the root?\", root.isRoot())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Getting all the ancestors or descendants of a node\n",
    "\n",
    "The ability to tell if a node is a tip, the root, or just another plain 'ol internal node seems simple, but also makes it possible to write several other, increasingly useful class methods for our PhyloNode class. \n",
    "\n",
    "The next set we will implement involves finding all the descendants of a node. Recall that  descendant nodes on a phylogenetic tree work much like descendants on a family tree: the descendants of a node will be it's children, the children of its children, etc up to the tips of the tree. \n",
    "\n",
    "When you read the above, I hope you see that somehow we will have to use some type of iteration to trace descendants in the tree. Depending on the exact tree we might need very few or an extremely large number of steps to get to a tip from any given node. \n",
    "\n",
    "Here we will use a coding strategy known as *recursion* to write a getDescendants method for our PhyloNode object. Each node knows about it's immediate children. Recursion is a strategy in which a function calls itself to iteratively solve small pieces of a larger problem. In our case, case a key realization is that the descendants of any node are simply it's children plus the combined descendants of those children. \n",
    "\n",
    "This allows us to right a small piece of code that may feel a little like magic: we simply ask each non-tip child to get it's descendants, and afterwards return the combined set of the current node's children plus each of those children's descendants. As we do, we'll have to take some care to maintain a list of descendants and add to it as we get reports back from each child about it's descendants.\n",
    "\n",
    "We can write a similar getAncestors method, except that in that case the code is simpler because each node only has one parent.\n",
    "\n",
    "Here's how that method will look once getDescendants and getAncestors are integrated into our class:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "class PhyloNode():\n",
    "    \"\"\"A node on a phylogenetic tree\"\"\"\n",
    "\n",
    "    def __init__(self,children=None,parent=None,\\\n",
    "      name = None):\n",
    "      \"\"\"Initiate a node on a phylogenetic tree\n",
    "      children -- a list of PhyloNode objects\n",
    "        descending immediately from this node\n",
    "      name -- a string for the name of the node\n",
    "      parent -- a single PhyloNode object for the parent\n",
    "      \"\"\"\n",
    "      self.Name = name\n",
    "      self.Children = []\n",
    "      if children:\n",
    "        self.Children.extend(children)\n",
    "      self.Parent = parent\n",
    "    \n",
    "    def addChild(self,child):\n",
    "        \"\"\"Attach a child node\"\"\"\n",
    "        if child not in self.Children:\n",
    "            self.Children.append(child)\n",
    "        child.Parent = self\n",
    "    \n",
    "    def isTip(self):\n",
    "      \"\"\"Return True if the node is a tip\"\"\"\n",
    "      if not self.Children: #false if Children is None or []\n",
    "        return True\n",
    "      else:\n",
    "        return False\n",
    "\n",
    "    def isRoot(self):\n",
    "      \"\"\"Return True if the node is the root of the whole tree\"\"\"\n",
    "      if not self.Parent:\n",
    "        return True\n",
    "      else:\n",
    "        return False \n",
    "    \n",
    "    def getDescendants(self):\n",
    "        \"\"\"Return a list of PhyloNodes descending from the current node\"\"\"\n",
    "\n",
    "        if self.isTip():\n",
    "            return []\n",
    "\n",
    "        descendants = self.Children or []\n",
    "        for c in self.Children:\n",
    "            #The set of descendants is described\n",
    "            #by the descendants of all the nodes\n",
    "            #immediate children.\n",
    "            if not c.isTip():\n",
    "                child_descendants = c.getDescendants()\n",
    "                descendants.extend([c for c in child_descendants if c not in descendants])\n",
    "\n",
    "            #Side note: this will fail on enormous trees\n",
    "            #due to the recursion limit. Not normally a problem though.\n",
    "        return descendants\n",
    "    \n",
    "    def getAncestors(self):\n",
    "        \"\"\"Return a list of PhyloNodes that are ancestors of the given node\"\"\"\n",
    "        \n",
    "        if self.isRoot():\n",
    "            return None\n",
    "\n",
    "        ancestors = [self.Parent]\n",
    "        parents_ancestors = self.Parent.getAncestors()\n",
    "        if parents_ancestors:\n",
    "            ancestors.extend(parents_ancestors)\n",
    "        return ancestors"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Testing out the getDescendants and getAncestors functions on a small hand-built tree\n",
    "\n",
    "Let's now try out our new class methods on a tree that looks like this:\n",
    "\n",
    "This produces a tree that looks roughly like this:\n",
    "\n",
    "<img src=\"./resources/rooted_small_tree.png\" width=\"175\" style=\"margin:25px 25px\" description=\"A small tree consisting of a root node and two descendants: A and B. Two additional nodes B1 and B2 descend from node B\" > \n",
    "\n",
    "Let's build this tree by hand and try reasoning about the ancestors and descendants of these 5 nodes. This will help us to ensure our code is working as expected:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "All descendants of the root node: ['A', 'B', 'B1', 'B2']\n",
      "All ancestors of node B2: ['B', 'root']\n",
      "All descendants of node B2: []\n"
     ]
    }
   ],
   "source": [
    "#Build our simple tree\n",
    "root = PhyloNode(name=\"root\")\n",
    "A = PhyloNode(name=\"A\",parent = root)\n",
    "root.addChild(A)\n",
    "B = PhyloNode(name=\"B\",parent = root)\n",
    "root.addChild(B)\n",
    "B1 = PhyloNode(name=\"B1\",parent=B)\n",
    "B2 = PhyloNode(name=\"B2\",parent=B)\n",
    "B.addChild(B1)\n",
    "B.addChild(B2)\n",
    "\n",
    "#Test the results so we can compare them aganinst the diagram:\n",
    "print(\"All descendants of the root node:\",[n.Name for n in root.getDescendants()])\n",
    "print(\"All ancestors of node B2:\",[n.Name for n in B2.getAncestors()])\n",
    "print(\"All descendants of node B2:\",[n.Name for n in B2.getDescendants()])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Defining relatedness on a phylogenetic tree\n",
    "\n",
    "The key piece of information that trees convey is the *phylogenetic relatedness* of different organisms. Evolutionary biologists define relatedness in relative terms based on recency of common ancestry. \n",
    "\n",
    ">**Definition of Phylogenetic Relatedness**:Two organisms A and B are *more related* to one another than they are to another organism C if they share a *more recent common ancestor* with one another than either does to C.  \n",
    "\n",
    "This is a somewhat long definition, but in practice it allows relative relatedness to be tested using a simple procedure: find the common ancestor of A and B and of A and C. Either one of those two MRCA nodes will be more recent than the other, or they will be the same. If the MRCA of A and B is more recent, then A is more closely related to B than it is to C. If the MRCA of A and C is more recent, then A is more closely related to C than to B.\n",
    "\n",
    "#### Finding the most recent common ancestor (MRCA) of two species by hand\n",
    "This procedure is easy enough to cary out by hand. To find the common ancestor of A and B, place your fingers on those two nodes on the tree. Then trace backwards along the tree from each to their ancestors. Stop when you hit a node that is an ancestor of both A and B (e.g. the first node that both fingers touch when tracing backwards in the tree from A and B. Mark that node as the most recent common ancestor (MRCA) of A and B. \n",
    "\n",
    "Now let's use our PhyloNode object to find the MRCA of two nodes so we can later calculate relatedness. Recall that the getAncestors function we wrote up above provided us a *list* of ancestors in order of recency (e.g. the parent node of the current node first, then the parent's parent etc). If we get the ancestors for any two nodes and look for the first shared ancestor, that will be the MRCA.\n",
    "\n",
    "We'll have to be careful to handle and potentially raise informative errors in a few special cases:\n",
    "* the case where one node is the root \n",
    "* the case where there is no MRCA (e.g. the nodes aren't connected in the same tree)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "class PhyloNode():\n",
    "    \"\"\"A node on a phylogenetic tree\"\"\"\n",
    "\n",
    "    def __init__(self,children=None,parent=None,\\\n",
    "      name = None):\n",
    "      \"\"\"Initiate a node on a phylogenetic tree\n",
    "      children -- a list of PhyloNode objects\n",
    "        descending immediately from this node\n",
    "      name -- a string for the name of the node\n",
    "      parent -- a single PhyloNode object for the parent\n",
    "      \"\"\"\n",
    "      self.Name = name\n",
    "      self.Children = []\n",
    "      if children:\n",
    "        self.Children.extend(children)\n",
    "      self.Parent = parent\n",
    "    \n",
    "    def addChild(self,child):\n",
    "        \"\"\"Attach a child node\"\"\"\n",
    "        if child not in self.Children:\n",
    "            self.Children.append(child)\n",
    "        child.Parent = self\n",
    "    \n",
    "    def isTip(self):\n",
    "      \"\"\"Return True if the node is a tip\"\"\"\n",
    "      if not self.Children: #false if Children is None or []\n",
    "        return True\n",
    "      else:\n",
    "        return False\n",
    "\n",
    "    def isRoot(self):\n",
    "      \"\"\"Return True if the node is the root of the whole tree\"\"\"\n",
    "      if not self.Parent:\n",
    "        return True\n",
    "      else:\n",
    "        return False \n",
    "    \n",
    "    def getDescendants(self):\n",
    "        \"\"\"Return a list of PhyloNodes descending from the current node\"\"\"\n",
    "\n",
    "        if self.isTip():\n",
    "            return []\n",
    "\n",
    "        descendants = self.Children or []\n",
    "        for c in self.Children:\n",
    "            #The set of descendants is described\n",
    "            #by the descendants of all the nodes\n",
    "            #immediate children.\n",
    "            if not c.isTip():\n",
    "                child_descendants = c.getDescendants()\n",
    "                descendants.extend([c for c in child_descendants if c not in descendants])\n",
    "\n",
    "            #Side note: this will fail on enormous trees\n",
    "            #due to the recursion limit. Not normally a problem though.\n",
    "        return descendants\n",
    "    \n",
    "    def getAncestors(self):\n",
    "        \"\"\"Return a list of PhyloNodes that are ancestors of the given node\"\"\"\n",
    "        \n",
    "        if self.isRoot():\n",
    "            return []\n",
    "\n",
    "        ancestors = [self.Parent]\n",
    "        parents_ancestors = self.Parent.getAncestors()\n",
    "        if parents_ancestors:\n",
    "            ancestors.extend(parents_ancestors)\n",
    "        return ancestors\n",
    "    \n",
    "    def getMRCA(self,other):\n",
    "        \"\"\"Return PhyloNode for the most recent common ancestor with other\n",
    "        other -- another PhyloNode object in the same tree\n",
    "        \"\"\"\n",
    "        most_recent_common_ancestor = None\n",
    "        #Cache the ancestors of other since\n",
    "        #we'll refer to it often\n",
    "        other_ancestors = other.getAncestors()\n",
    "        self_ancestors = self.getAncestors()\n",
    "        #First check for the trivial case\n",
    "        #where one node is root (but be sure they're on the same tree)\n",
    "        if self.isRoot() and self in other_ancestors:\n",
    "            return self\n",
    "\n",
    "        if other.isRoot() and other in self_ancestors:\n",
    "            return other\n",
    "\n",
    "        for a in self_ancestors:\n",
    "            #Note these will be in order of relatedness\n",
    "            if a in other_ancestors:\n",
    "                #End the loop the first time this happens\n",
    "                #since we want the most\n",
    "                #recent common ancestor\n",
    "                most_recent_common_ancestor = a\n",
    "                break\n",
    "\n",
    "        if not most_recent_common_ancestor:\n",
    "            raise ValueError(\"No common ancestor found for \",self.Name,\" and \",other.Name,\\\n",
    "            \". Are they on the same tree?\")\n",
    "\n",
    "        return most_recent_common_ancestor"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now let's try it out on a test tree, like the small tree (Fig. 5) above. Using the manual method, we expect the MRCA of B1 and B2 to be the node labelled B, and the MRCA of A and B1 to be the root of the tree."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The MRCA of B1 and B2 is: B\n",
      "The MRCA of A and B1 is: root\n"
     ]
    }
   ],
   "source": [
    "#Build our simple tree\n",
    "root = PhyloNode(name=\"root\")\n",
    "A = PhyloNode(name=\"A\",parent = root)\n",
    "root.addChild(A)\n",
    "B = PhyloNode(name=\"B\",parent = root)\n",
    "root.addChild(B)\n",
    "B1 = PhyloNode(name=\"B1\",parent=B)\n",
    "B2 = PhyloNode(name=\"B2\",parent=B)\n",
    "B.addChild(B1)\n",
    "B.addChild(B2)\n",
    "\n",
    "A_B1_MRCA = B1.getMRCA(A)\n",
    "B1_B2_MRCA = B1.getMRCA(B2)\n",
    "\n",
    "print(\"The MRCA of B1 and B2 is:\",B1_B2_MRCA.Name)\n",
    "print(\"The MRCA of A and B1 is:\",A_B1_MRCA.Name)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Testing relatedness in python using our PhyloNode object\n",
    "\n",
    "Now let's test the relative relatedness of some focal node A to two other nodes B and C using our class. This time for compactness I'll write the code as a separate function:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "def more_related(A,B,C):\n",
    "    \"\"\"Return the node that is more closely related to A (either B or C). \n",
    "    A -- a reference PhyloNode object\n",
    "    B -- a PhyloNode object to test for relatedness to A\n",
    "    C -- a PhyloNode object to test for relatedness to A\n",
    "    Returns None if both are equally related\"\"\"\n",
    "    AB_MRCA = A.getMRCA(B)\n",
    "    AC_MRCA = A.getMRCA(C)\n",
    "    if AB_MRCA == AC_MRCA:\n",
    "        return \n",
    "    if AB_MRCA in AC_MRCA.getAncestors():\n",
    "        return C\n",
    "    if AC_MRCA in AB_MRCA.getAncestors():\n",
    "        return B"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The node closest to B1 is: B2\n"
     ]
    }
   ],
   "source": [
    "closest_to_B1 = more_related(B1,B2,A)\n",
    "print(\"The node closest to B1 is:\", closest_to_B1.Name)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [],
   "source": [
    "from random import choice,random\n",
    "from copy import deepcopy\n",
    "\n",
    "class PhyloNode():\n",
    "    \"\"\"A node on a phylogenetic tree\"\"\"\n",
    "\n",
    "    def __init__(self,children=None,parent=None,\\\n",
    "      name = None):\n",
    "      \"\"\"Initiate a node on a phylogenetic tree\n",
    "      children -- a list of PhyloNode objects\n",
    "        descending immediately from this node\n",
    "      name -- a string for the name of the node\n",
    "      parent -- a single PhyloNode object for the parent\n",
    "      \"\"\"\n",
    "      self.Name = name\n",
    "      self.Children = []\n",
    "      if children:\n",
    "        self.Children.extend(children)\n",
    "      self.Parent = parent\n",
    "      self.Extinct = False\n",
    "\n",
    "    def isTip(self):\n",
    "      \"\"\"Return True if the node is a tip\"\"\"\n",
    "      if not self.Children: #capture None or []\n",
    "        return True\n",
    "      else:\n",
    "        return False\n",
    "\n",
    "    def isRoot(self):\n",
    "      \"\"\"Return True if the node is the root of the whole tree\"\"\"\n",
    "      if not self.Parent:\n",
    "        return True\n",
    "      else:\n",
    "        return False\n",
    "\n",
    "    def getDescendants(self):\n",
    "        \"\"\"Return a list of PhyloNodes descending from the current node\"\"\"\n",
    "\n",
    "        if self.isTip():\n",
    "            print(self.Name,\" is a tip ... returning []\")\n",
    "            return []\n",
    "\n",
    "        descendants = self.Children or []\n",
    "        for c in self.Children:\n",
    "            #The set of descendants is described\n",
    "            #by the descendants of all the nodes\n",
    "            #immediate children.\n",
    "            if not c.isTip():\n",
    "                child_descendants = c.getDescendants()\n",
    "                descendants.extend([c for c in child_descendants if c not in descendants])\n",
    "\n",
    "            #Side note: this will fail on enormous trees\n",
    "            #due to the recursion limit. Not normally a problem though.\n",
    "        return descendants\n",
    "\n",
    "    def getAncestors(self):\n",
    "        \"\"\"Return the ancestors of the given node\"\"\"\n",
    "        if self.isRoot():\n",
    "            return None\n",
    "\n",
    "        ancestors = [self.Parent]\n",
    "        parents_ancestors = self.Parent.getAncestors()\n",
    "        if parents_ancestors:\n",
    "            ancestors.extend(parents_ancestors)\n",
    "        return ancestors\n",
    "\n",
    "    def getRoot(self):\n",
    "        \"\"\"Return the root node\"\"\"\n",
    "        curr_node = self\n",
    "        while not curr_node.isRoot():\n",
    "            curr_node = curr_node.Parent\n",
    "        return curr_node\n",
    "\n",
    "    def addChild(self,child):\n",
    "        \"\"\"Attach a child node\"\"\"\n",
    "        if child not in self.Children:\n",
    "            self.Children.append(child)\n",
    "        child.Parent = self\n",
    " \n",
    "    def addParent(self,parent):\n",
    "        \"\"\"Attach a parent node\"\"\"\n",
    "        self.Parent = parent\n",
    "        parent.Children.append(self)\n",
    "    \n",
    "    def getMRCA(self,other):\n",
    "        \"\"\"Return PhyloNode for the most recent common ancestor with other\n",
    "        other -- another PhyloNode object in the same tree\n",
    "        \"\"\"\n",
    "        most_recent_common_ancestor = None\n",
    "        #Cache the ancestors of other since\n",
    "        #we'll refer to it often\n",
    "        other_ancestors = other.getAncestors()\n",
    "        self_ancestors = self.getAncestors()\n",
    "        #First check for the trivial case\n",
    "        #where one node is root (but be sure they're on the same tree)\n",
    "        if self.isRoot() and self in other_ancestors:\n",
    "            return self\n",
    "\n",
    "        if other.isRoot() and other in self_ancestors:\n",
    "            return other\n",
    "\n",
    "        for a in self_ancestors:\n",
    "            #Note these will be in order of relatedness\n",
    "            if a in other_ancestors:\n",
    "                #End the loop the first time this happens\n",
    "                #since we want the most\n",
    "                #recent common ancestor\n",
    "                most_recent_common_ancestor = a\n",
    "                break\n",
    "\n",
    "        if not most_recent_common_ancestor:\n",
    "            raise ValueError(\"No common ancestor found for \",self.Name,\" and \",other.Name,\\\n",
    "            \". Are they on the same tree?\")\n",
    "\n",
    "        return most_recent_common_ancestor\n",
    "    \n",
    "    def speciate(self):\n",
    "        \"\"\"Add two children descending from this node\"\"\"\n",
    "        if self.Children:\n",
    "            raise ValueError(\"Internal nodes can't speciate\")\n",
    "        if self.Extinct:\n",
    "            raise ValueError(\"Extinct nodes can't speciate\")\n",
    "\n",
    "        child1_name = self.Name + \"A\"\n",
    "        child1=PhyloNode(name=child1_name)\n",
    "        self.addChild(child1)\n",
    "        child2_name = self.Name + \"B\"\n",
    "        child2=PhyloNode(name=child2_name)\n",
    "        self.addChild(child2)\n",
    "\n",
    "\n",
    "    def update(self,speciation_chance=0.25,\\\n",
    "        extinction_chance=0.25):\n",
    "        \"\"\"Update the node by speciation or extinction\"\"\"\n",
    "        if not self.isTip():\n",
    "            print(\"Not updating node {name} - it's not a tip\".format(name=self.Name))\n",
    "            return None\n",
    "\n",
    "        if random() < extinction_chance:\n",
    "            print(self.Name,\" goes extinct!\")\n",
    "            self.Extinct = True\n",
    "\n",
    "        if self.Extinct:\n",
    "            print(\"Not updating node {name} - it's extinct\".format(name=self.Name))\n",
    "            return None\n",
    "        print(\"Updating node:{name}\".format(name=self.Name))\n",
    "\n",
    "        if random() < speciation_chance:\n",
    "            #Speciate\n",
    "            print(\"Node {name} speciates!\".format(name=self.Name))\n",
    "            self.speciate()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exercises\n",
    "\n",
    "**Exercise 1** (Quick). Baum *et al.* [2] review tree interpretation. Consider the following tree from Fig. 1 in Baum *et al.*: (fish,(frog,(lizard,(mouse,human))));. Manually build this tree using PhyloNode objects.\n",
    "\n",
    "**Exercise 2** (Quick). Sketch the Baum *et al.* tree from Exercise 1 above. On that tree, is the frog more closely related to the fish or to the human? Write down your answer, then use the more_related function to test your intuition. Finally, consult the Baum *et al* article (it's very short) to see if you got it right.\n",
    "\n",
    "**Exercise 3**. Add a getRoot method to the PhyloNode class that can be called from any node and finds then returns the root of the tree.\n",
    "*Hint*: all nodes on the tree have the root of the tree as one of their ancestors.\n",
    "\n",
    "**Exercise 4**. Currently nodes can only be referenced by the node object itself. Write a function called getNodeByName that takes as input a node name (as a string), and then iterates over all nodes, and returns the node that has that name.\n",
    "*Hint*: all nodes on a tree are descendants of the root node. So if you've written the getRoot method in Exercise 3, you can get the root, then use getDescendants to find all the other nodes on the tree (in order to search them for the name you're interested in)\n",
    "*Hint 2*: you should consider how you want to handle the case that more than one node has the name you're looking for. This is especially likely for unnamed nodes if the user passes in None or the empty string '' to your method as the node name. Some options include raising a ValueError.\n",
    "\n",
    "**Exercise 5**. [*Sister taxa*](https://en.wikipedia.org/wiki/Sister_group) or *sister groups* are defined as taxa that are each other's closest relatives on the tree. Add a method getSister that finds the sister taxa of a given node.\n",
    "\n",
    "**Exercise 6**. While some trees, called *cladograms* have uninformative branch lengths, a true phylogeny allows each edge to vary in length to represent different amounts of evolution. Extend the PhyloNode class to allow for PhyloNode objects to have edges of variable length associated with them.\n",
    "\n",
    "*Hint*: you'll likely want to add a self.BranchLength property to the PhyloNode object. Be sure that users can set the branch length when initializing objects and when adding child nodes with the addChild method.\n",
    "\n",
    "**Exercise 7**.  The length of the path separating any two tips on a tree with meaningful branch lengths (see *Exercise 6*) is called the *tip-to-tip distance*. Add a getDistance method that takes as input two tip nodes on the tree, and uses the branch length information from Exercise 6 to calculate the distance between them.\n",
    "\n",
    "*Hint*: the distance between two nodes, N1 and N2 is the sum of the distance from N1 to the most recent common ancestor (MRCA) of N1 and N2, plus the distance from that MRCA to N2.\n",
    "\n",
    "**Exercise 8**. When groups of organisms are given names, it is expected that those organisms form a monophyletic group. A [monophyletic group](https://en.wikipedia.org/wiki/Monophyly) is defined as the group formed by some node on the tree, plus all of it's descendants (if it has any). Collections of organisms that are not monophyletic are generally not recognized as valid families, orders, classes, etc. Add an isMonophyletic method to the PhyloNode class that takes as input a list of nodes, and returns True if the listed nodes form a monophyletic group, and False otherwise."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## [Reading Responses & Feedback](https://docs.google.com/forms/d/e/1FAIpQLSeUQPI_JbyKcX1juAFLt5z1CLzC2vTqaCYySUAYCNElNwZqqQ/viewform?usp=pp_url&entry.2118603224=Alignment+and+Phylogenetics+-+Implementing+a+Birth-Death+model+of+Speciation+and+Extinction)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## References and Further Reading:\n",
    "\n",
    "[1] M. Aubert et al., [\"Pleistocene cave art from Sulawesi, Indonesia\"](https://www.nature.com/articles/nature13422), *Nature* volume 514, pages 223–227 (9 October 2014) \n",
    "\n",
    "[2] Baum et al., [\"The Tree-Thinking Challenge\"](https://digitalcommons.unl.edu/cgi/viewcontent.cgi?article=1104&context=bioscifacpub),*Science* volum 310, pages 979-980 (11 November 2005)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}