StefanGrünewald練習題答案Exercise1(Practice:Neighbor-Joining)（賈壯GiventhefiveDNAsequencesbelow,constructtheirNeighbor-Joining-treebasedontheirHammingDistance.首先，這些序列已經比對好了，多重序列比對算法很復雜，手算基本不可能，所以題目如果給定序列要求構建系統發生樹（進化樹，那么他給定的序列一定是比對好的。我們要做的第一步是計算HmmngHmmng距離用來衡量兩個序列相似程度，它被定義為un，umsmah個數，n表示序列長度，我們把序列間的距離放在一個矩陣中：Neighbor-Joining算法是一種迭代算法，在每一次迭代中有3Step1taxa（s1-s510對）Q-criterion值，選取最小的一對作為我們的Neighborpair，記為x*，y*。Q-criterion Q(x,y)d(x,yn2d(xzn2dyz，ntaxa 5

15

[d(s2,s1)d(s2,s3)d(s2,s4)d(s2,s5)]0.7 3

2.6 3

3.2同理我們計算其他組合的Q-criterion選取值最小的，即Q(s1,s41.333Step2Reduction，x*和y*taxauux*和y*d(u,x*) [d(x*,z)d(x*,y)d(y*,z)]2(n2)zX{x*,y*,u}

d(u,s1)

us1s4ud(u,z)1(d(x*,z)d(y*,z)d(x*,y*)

d(u,s2)1[d(s1,s2)d(s4,s2)d(s1,s4)]1(0.70.80.3) 2neighborpair（s2，s3），用新的結vd(vs20.4375d(vs30.3625，更新后的距離矩陣為：33topologys5，u和v000uv還原為原始的結點，因為我們已經計算了它和原始結點的關系，所以最Exercise2（王桂敏Proof:firstly,whenn=3,wecanconstructabinarytreewithonlyonestructure,andthereare2interiorverticesand4edges.Thisisconsistentwiththestatements.Then,weassumethestatementsarerightforn=x.whenn=x+1,inotherwords,weaddonetaxontothetree,wewillhaveonemoreinteriorverticeandothertwoedges.Oneedgeisincidentwiththenewtaxonandanotherisgeneratedwhentheoldedgeisdividedintotwobythenewinteriorvertice.So,thestatementsarealsoright.Exercise3（王桂敏WedefineatreeisaconnectedgraphwithoutaWhenthenumberofverticesexceedsthenumberofedgesby1,thetreemusthavenocycle.Iftherearecyclesinaconnectedgraph,thenumberofedgeswon’tbelessthanthenumberof(PS:這是運籌學書上的定理，其實仔細想想顯而易見，如果覺得這樣不夠有說服力的話，我們可以用類似于2中的方法來證明。老師的PPT里就是這么做的。見下文)Whenthereare2edgesand3vertices,weknowtheconnectedgraphmustbeaFormoreedgesandvertices,whenweaddoneedgeandoneverticetothetree,wecouldn’t