### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Integ Bio Discrete Math IBMS 1300

ETSU

GPA 3.61

### View Full Document

## 9

## 0

## Popular in Course

## Popular in Human Dev And Family Sciences

This 36 page Class Notes was uploaded by Sadye Toy on Sunday October 11, 2015. The Class Notes belongs to IBMS 1300 at East Tennessee State University taught by Staff in Fall. Since its upload, it has received 9 views. For similar materials see /class/221383/ibms-1300-east-tennessee-state-university in Human Dev And Family Sciences at East Tennessee State University.

## Reviews for Integ Bio Discrete Math

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 10/11/15

Evolution Module 61 Phylogenetic Trees Bob Gardner and Lev Yampolski Integrated Biology and Discrete Math IBMS 1300 Fall 2008 INDUCTION Note The natural numbers N is the familiar set N 1 2 3 From the formal de nition of N we have the following The Principle of Mathematical Induction Let S C N have the properties i1 S ii ForallnENianSthenn1ES ThenSN Note We will use mathematical induction to prove the valid ity of certain formulae The proof technique will be to con rm the formula for N 1 step and then show that assum ing the validity of the formula for N 71 implies its validity for N n 1 You might Visualize this like knocking down dominoes If you know that you have knocked down the rst domino and that ii Whenever a domino falls it knocks down the next domino then you can conclude that all of the dominoes fall Example Prove that for all n E N we have N 1352N 1Z21 1N2 11 Solution First for N l 2321 121 1112 11 and the formula holds Second assume the formula holds for N n 221 1 112 11 We now show that the formula holds for N n l n1 n 221 1 221 1 211 1 1 11 11 n2 2n l by the induction hpothesis n22nlnl2 Hence by the Principle of Mathematical lnduction the for mula N 221 1 N2 11 holds for all N E N I Exercise 611 In the computation of de nite integrals using the de nition and regular partitions you encountered the formulae 2 n 7101 1 n 2 7101 12n 1 n 3 7101 1 E k E k E k k1 2 k1 6 k1 lt 2 gt Use the Principle of Mathematical Induction to prove each of these Exercise 612 In computing the derivative of f 73 n E N by de nition you used the Binomial Theorem which states that N N b N N ibi a1 20 for all N E N Where Use the Principle of Mathematical Induction to prove the Bi nomial Theorem Note An alternate form of the Principle of Mathematical Induction is the following The Strong Principle of Mathematical Induction Let S C N have the properties i1 S ii ForallnESif12nCSthenn1ES ThenSN Note Going back to the domino analogy we would say that if you have knocked down the rst domino and ii whenever the rst 71 dominoes fall the n 1St domino falls then you can conclude that all of the dominoes fall TREES Note In section 65 of Symbiosis I Inbreeding we intro duced the idea of a graph and used a method of counting paths to de ne and calculate an inbreeding coef cient In this section we turn the application of a graph theoretic object called a tree to the study of relationships between species or other biological units Note Recall that a tree is an acyclic connected graph That is a connected graph which contains no cycle Note If we delete an edge from any tree then the result ing graph consists of two disjoint pieces ie two connected components This observation combined with the Principal of Mathematical Induction allows us to prove an important theorern concerning trees Theorem 611 A tree with n yertices has n 1 edges Proof We prove the result holds for all n E N by using induction First a tree with N 1 vertex contains N 1 0 edges and a graph with N 2 yertices has N 1 1 edge Suppose the result holds for N 1N 2N 71 Consider a tree T with N n 1 yertices Let my be an edge of T If we delete edge 13y from T then we get two disjoint connected graphs T1 and T2 Since T is an acyclic graph then so are graphs T1 and T2 That is T1 and T2 are trees Let N1 be the number of yertices of T1 and let N2 be the number of yertices of T2 Notice that N1 lt n 1 N2 lt n 1 and N1 N2 N 71 1 So by the induction hypothesis tree T1 and T2 have N1 1 and N2 1 edges respectively Now the edge set of T is the edge set of T1 combined with the edge set of T2 and the edge m y So T has N1 1N2 11N1N2 1N 1edges Therefore the result holds for N n 1 and by the Strong Principle of Mathematical Induction the result holds for all N E N I Theorem 612 In a tree any two vertices are connected by a unique path Proof Since trees are by de nition connected graphs we know that there exists at least one path between any two vertices We show uniqueness through proof by contradiction in which we assume that the theorem is false and derive a contradiction leading us to conclude that the theorem is in fact true So we start by assuming that there is more than one path between some two vertices Say there are two paths between vertices u and 2 Let the paths be P1 U6101 2U2quot39 n 1Un 1 nv and P2 Meir162v e 12 Since the two paths are different there is some edge e 13y of P1 that is not an edge of P2 Now the graph P1 U P2 e is connected for any vertex in this graph there is either a path to vertex u or a path to vertex v and since P2 is a path between u and 2 then there is a path between any two vertices of this graph So in particular there is a path in P1 U P2 e from a to y say path P But then PUc contans a cycle which is present in the original graph However since the original 8 graph is a tree it cannot contain a cycle Therefore under the assumption of the existence of two paths between some pair of vertices we have derived a contradiction Hence there rnust be only one path between any two vertices of a tree y V1 V VI 7l x V1 Vm1 I l Note In fact the converse of Theorem 611 is also true assuming a connected graph Theorem 613 A connected graph With n vertices and n 1 edges is a tree Exercise 613 Use the Strong Principle of Mathematical Induction and Theorem 612 to prove Theorem 613 HINT If T is a tree on N n1 vertices and you delete one vertex of T and hence you delete all the edges incident to that vertex then What is left Note Combining Theorems 611 and 613 we get a classi cation of graphs Which are trees Theorem 614 A connected graph With 2 vertices and e edges is a tree if and only if v e 1 De nition The degree of a vertex of a graph is the number of edges incident to it That is the number of edges of which it is an element Theorem 615 The sum of the degrees of the yertices of any graph is twice the number of edges Proof Every edge of a graph has two yertices as elements So if we add up the sums of the degrees of the yertices of a graph then we count each edge twice and the sum is twice the number of edges 2 degreev the number of edges of G v is a vertex of G Theorem 616 A tree on two or more yertices has at least two yertices of degree one Proof Let T be a tree with n yertices Then T has n 1 edges by Theorem 611 and the sum of the degrees of the yertices of the tree by Theorem 615 is Z degreev 2n 1 2n 2 UET If the degree of each vertex is two or more then the sum of the degrees of the vertices is at least 271 since there are n vertices It follows that at least two of the vertices must be of degree one I Note In biological applications of trees we are particularly interested in vertices of degree one these Will often represent the biological units of interest HYDROCARBON MOLECULES Recall A hydrocarbon molecule consists of only carbon and hydrogen atoms A carbon atom has four chemical bonds and a hydrogen atom has one chemical bond A hydrocarbon is said to be saturated if it has the maximum number of hydro gen atoms for the given number of carbon atoms hence there are no carbon double bonds and no cycles of carbon atoms These hydrocarbons are called alkanes So a saturated hydro carbon can be represented by a graph in Which the carbon atoms are degree four yertices the hydrogen atoms are degree one yertices and the edges represent chemical bonds Several of these ideas can be found in Bogart Example Here are three examples of saturated hydrocar bons t1t Methane Ethane Propane Example In a saturated hydrocarbon with 71 carbon atoms7 there are 271 2 hydrogen atoms Proof The hydrocarbon can be represented by a tree Let h be the number of hydrogen atoms Then the tree has n h vertices and by Theorem 611 it has n h 1 edges We know the degree of each vertex which represents a carbon atom is four and the degree of each vertex which represents a hydrogen atom is one So the total sum of the degrees is 471 h Also7 by Theorem 615 the sum of the degrees is twice the number of edges Therefore 4n h 201 h 1 From this equation7 we get h 2n 2 I Note Two different saturated hydrocarbons can have the same chemical formula but different physical structures that is the trees representing them can be different Such molecules are called isomers of each other For example C4H10 yields HHHH I HHHH Butane Isobutane Exercise 614 Draw the trees which represent all possible saturated hydrocarbons C5H12 Note Since two carbon atoms can form a double bond it is of interest to consider graphs which have repeated edges Such a graph is called a multigmph and graphs without repeated edges are often called simple graphs 15 Example Ethylene is CQH4 and can be represented as HC H H H 2 Exercise 615 A hydrocarbon with at least one carbon double bond and no cycle is called an alkene Show that an alkene with exactly one double carbon bond and 71 carbon atoms has 271 hydrogen atoms Exercise 616 A hydrocarbon with at least one carbon triple bond and no cycle is called an alkyne Show that an alkyne with exactly one triple carbon bond and 71 carbon atoms has 271 2 hydrogen atoms Exercise 617 A hydrocarbon containing one or more cycles of carbon atoms called a carbon ring is called a cy cloalkane Show that a saturated cycloalkane with one carbon ring and 71 carbon atoms has 271 hydrogen atoms Exercise 618 Draw a graphical representation of a ben zene molecule7 CgHg Is this a saturated hydrocarbon 16 COUNTING TREES Note We now consider trees which have biological appli cations We are interested in representing evolutionary trees graphically Here is an evolutionary tree and the correspond ing graph Human Human Chimp Chimp Gorilla R Gorilla R Orangutan Orangutan Gibbon Gibbon Notice that each of the vertices of degree one play a special role Five of them represent species and one of them labeled R is the root of the tree Each of the other vertices represents an episode of speciation and is hence a vertex of degree three think of it as one species in two species out Since we expect speciation to occur in this bifurcating way we restrict our study to trees with these properties De nition A tree which consists of only degree one and degree three vertices is a blfurcatlng tree If each of the degree one vertices is given a distinct label then the tree is labeled If one of the degree one vertices is declared the root then the tree is rooted Note For evolutionary trees we are primarily interested in rooted bifurcating labeled trees With a nod to the botanical sciences the degree one vertices except for the root are called leaves A rooted bifurcating tree with 71 leaves is called an nspecles tree We Wish to count the number of different n species trees Theorem 617 There are I rooted bifurcat 2n 2n 2 ing labeled n species trees where n 2 2 Each such tree has 271 1 edges Note First for n 2 there is exactly one such tree s1 s2 ROOT and the theorem holds Now suppose we wanted to add a third species 33 Since the root and the species vertices must remain degree one and the internal vertices must remain degree three the only way to add a new species is to subdivide an existing edge by introducing a new vertex and then adding a new edge incident to the new vertex with the new species as the other end of the new edge Since the 2 species tree has three edges this can be done in three ways ROOT ROOT ROOT 2 3 3 I SO there are three 3 species trees and M 2lt3gt72ltlt3gt 2 Similarly7 to add a fourth species7 there are ve ways to do it since each of the 3 species trees has 5 edges for each of the 3 species trees Hence there are 135 15 4 species trees 24 3 1 arid 2424 2 5 Exercise 619 Show algebraically that 2 3 20 Lemma 618 Let T be an n species tree Let T1 and T2 be 71 1 species trees each created from T by subdividing an edge and adding a new edge and a labeled vertex say the new vertex is labeled SW1 in both T1 and T2 Then if the edge of T which is subdivided to create T1 is different from the edge of T used to create T2 then T1 and T2 are different Proof Let 61 U1 m be the edge of T which is subdivided to create T1 and let 62 Mg m be the edge of T which is subdivided to create T2 Consider the path Pu1 frorn 1L1 to the root and the path PU1 from m to the root One of these paths is shorter than the other by exactly one edge either Pu1 PU1 61711 or PU1 Pu1 61 v1 Without loss of generality suppose Pu1 is shorter This illustrates the fact that a rooted tree with labeled leaves has a natural orientation toward the root77 and away from the root In a similar way suppose a path from 1L2 to the root is shorter than a path from 02 to the root Since T is a tree there is a unique path from m to 02 and the path must include edges 61 and 62 since there is a unique path from m to m Now we show that trees T1 and T2 are different by finding the lengths of the path between two vertices of T1 which is different from the length of the path of the same two vertices in T2 In T1 a path from SW1 to 21 v1 consists only of the vertices Sn17 W7 and 111 where 11 is the new vertex which subdivides edge 61 But in T27 a path from Sn1 to 111 must include vertices Sn17 v7 m7 and 111 it must also include U1 but we do not know that U1 and 1L2 are different So in T2 the path from Sn1 to 111 is longer than the path in T1 from Sn1 to 211 Therefore T1 and T2 are different I Sn l V v i 1 v2 1 2 v1 1 7 gtl 11 112 lll 112 111 V V V ROOT ROOT ROOT Note The lemma shows that whenever we create an n1 species tree from an n species tree7 we get different trees when we subdivide different edges We will use induction to count the number of n species trees But how do we know that starting with an n species tree and creating two nk2 species trees by adding k new species in different places77 produces different n k species trees the lemma only guarantees a difference when k 1 This is where the labeling plays an 22 important role If we assume the two 71 k species trees are the same then we can derive a contradiction Lemma 619 Suppose T1 and T2 are two different 71 1 species trees generated from n species tree T as described in Lemma 618 Then any n k species tree created from T1 is different from any n k species tree created from T2 Proof Suppose not Suppose T1 is an n k species tree created from T1 and T2 is an n k species tree created from T2 Then consider the n 1 species trees induced by the rst 71 1 labeled yertices and the root in T1 and T2 These induced trees77 can be formed by taking the union of all of the paths from the labeled yertices to the root These 71 1 species trees are exactly T1 and T2 However T1 and T2 are different by Lemma 618 Since these subtrees of Ti and T2 are different then T and T2 are different Note This concept of same and different trees is better dealt with mathematically by introducing an isomorphism same shape An isomorphism between two graphs is a one to one and onto mapping between the vertex sets of the graphs which preserves the edge sets of the graphs For ex ample7 the following two graphs are isomorphic The isomorphism 7T is the function such that 7T0 a7 7T1 b7 7T2 c7 7T3 d7 and 7T4 6 Of course7 both graphs are a 5 cycle Two isomorphic graphs have the same properties lf two trees are isomorphic7 say7 then the lengths of paths between corresponding vertices must be the same The correspondence is created by the mapping 7 Lemma 6110 Any n species tree can be generated from a 2 species tree by a unique sequence of n 2 steps of adding new labeled vertices species by subdividing edges Proof We consider What happens by reversing the process of adding labeled vertices Consider an n species tree 71 gt 2 With species as labeled vertices Sl SQ Sn Remove vertex 3 and the edge containing it since 3 is degree one there is only one edge incident to it say edge v Sn Since v is of degree three in the n species tree then there are two other vertices adjacent to if say u and 2 Replace edges u 0 and v v With edge u v This process is called pruning a tree It has resulted in the removal of a leaf We then have created an n 1 species tree With species 31 SQ Sn1 Continue this process of pruning species until only species 31 and SQ are left The reversal of the steps in this process then creates the original n species tree from the 2 species tree Also by Lemma 619 there is only one sequence of steps Which produces the original n species tree from the 2 species tree I Note With the help of Lemmas 618 619 and 6110 we are now ready to count the number of n species trees 2 3 Theorem 617 There are M 271 201 2 ing labeled n species trees where n 2 2 Each such tree has rooted bifurcat 2n 1 edges Proof We have already seen that these formulae hold for N 2 and N 3 Now suppose they hold for N n An 2n 3 271 201 2 n species trees Consider N n 1 We create all n 1 n species tree has 271 1 edges and there are species trees by adding a new species to an n species tree Since there are 271 1 edges in an n species tree there are 271 1 different ways to produce an n 1 species tree from a given n species tree By the induction hypothesis there are 1 X 3 X 5 X X 271 3 n species trees and so we can create 271 1 1x3x5xX2n 3X2n 1m 2n 1 3 i 2N 3 2ltn1gt2n 1 2 2N2N 2 n1 species trees By Lemma 619 the trees are all different and by Lemma 6110 we have all such trees The n species tree has 271 1 edges and we have subdivided some edge into two edges and added a new edge for a net gain of two edges 26 So the n 1 species tree has 2n 1 2 2n 1 2n 1 1 2N 1 edges Therefore by the Principle of Mathematical Induction the theorem follows Note Some of the rst interest in graphs concerned counting trees and was addressed by Arthur Cayley in the mid 1800s A common approach to counting involves generating functions in which the number of objects of a given size is computed in terms of the number of objects of a given size is computed in terms of the number of objects of smaller sizes The Fibonacci sequence ltfngt is an elementary example of such an idea f1 1 f2 1 and fn fn1 fn2 for n 2 3 The technique of proof presented above is due to Cavilla Sforza and Edwards 3 Note The presence of the factorial in the number of n species trees means that there is a tremendous number of such trees even when n is fairly small Consider the following table from Felsenstein page 24 Table 611 The number of rooted 72 species trees for vari ous 71 From Felsenstein of Species 71 of Trees 1 1 2 1 3 3 4 15 5 105 5 945 7 10395 8 135135 9 2027025 10 34459425 20 m 820 X 1021 30 m 495 x 1038 40 m 101 X 1057 50 m 275 x 1076 We see from this table that if we want to construct a phyloge netic tree for just a few species say 10 then it is impractical to try to search through all possible trees for 10 species there are over 34 million trees to nd the one Which best ts given data Hence some type of algorithm is needed to help simplify the problem This will be explored shortly 28 OTHER TREES Note Most methods of inferring phylogenies infer unrooted trees77 Felsenstein page 24 That is it is desired to find a tree which best describes evolutionary relationships but without an idea towards a common ancestor With much of the phylogenetic work interest lies in extant species and the revelation of relationships based on molecular datainot so much on family trees77 which relate extant and extinct species De nition An unmoted bifurcatmg labeled tree is a tree in which every vertex is of either degree three or degree one The degree one vertices are given distinct labels If there are 71 degree one vertices the tree is called an unmoted nspecz es tree Note There is no signi cant difference between an unrooted n species tree and a rooted n 1 species tree We can simply th think of the root of an n 1 species tree as the 71 species Conversely any unrooted n species tree can be related to an n 1 species tree by declaring one of the species as the root Since there are 2n 1 1 2nD 2n 1 2 1gtlt3gtlt5gtltgtlt2n 13 01 2 5 1X3X5xx2n 5 n 1 species trees then this is the number of unrooted n species trees Exercise 6110 Give a direct proof based on mathemati cal induction for the number of unrooted n species trees You may assume that Lemma 618 619 and 6110 hold for un rooted trees Note There is one subtle conceptual difference between rooted and unrooted trees We mentioned above the idea in a rooted tree of directions Namely we can think of a path that goes from a vertex towards the root or a path that goes from a vertex away from the root77 and hence towards a leaf Since unrooted trees do not have a root these ideas are meaningless in the unrooted tree setting Note An additional and very dif cult question concerns the number of tree shapes That is we are interested in the number of different nomsomorphz39c unlabeled trees The unlabeled rooted 2 species tree and 3 species trees are unique There are two unlabeled rooted 4 trees Exercise 6111 Give a path length argument as to why the above two graphs are different Exercise 6112 There are three unlabeled rooted 5 species trees What are they There are six such 6 species trees What are they Note lt is not currently known how many unlabeled n species trees there are see Felsenstein7 page 30 Several 31 values have been calculated and are presented in the following table Table 612 The number of different unlabeled rooted 72 species trees for various 72 From Felsenstein of Species 72 of Trees 1 1 2 1 8 1 4 2 5 8 6 6 7 11 8 28 9 46 10 98 20 298547 80 m 141 x 109 40 z 810 x 1012 50 m 515 X 1016 Note We can also consider unlabeled unrooted n species trees There are unique examples for n E 2 3 4 5 gt lt Note Some of the numbers of unlabeled unrooted n species trees are given in the following table Table 613 The number of different unlabeled unrooted 72 species trees for various 71 From Felsenstein of Species 71 of Trees 1 1 2 1 3 1 4 1 5 1 6 2 7 2 8 4 9 6 m n 20 12444 30 252461 x 107 mLMxlml A o Exercise 6113 Find all labeled unrooted n species trees for n E 6 7 8 Note As a nal comment on counting trees we Observe that the number of distinct trees on n vertices making no assumptions of degrees or labelings is unknown However the number of labeled trees on n vertices that is all of the vertices are labeled is nn2 REFERENCES 1 J A Bondy and U S R Murty Graph Theory with Ap plications New York North Holland 1979 2 K P Bogart Introductory Gombinatories Boston Pit man 1983 3 L L Cavilla Sforza and A W F Edwards Analysis of Human Evolution in Genetics Today Proceedings of the XI International Congress of Genetics The Hague The Netherlands September 1963 Vol 3 ed S J Geerts Oxford Pergamon 1965 4 J Felsenstein Inferring Phylogenies Sunderland MA Sinauer Associates 2004

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "I made $350 in just two days after posting my first study guide."

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.