成果練習(xí)題答案stefangrünewald

StefanGrünewald練習(xí)題答案Exercise1(Practice:Neighbor-Joining)（賈壯GiventhefiveDNAsequencesbelow,constructtheirNeighbor-Joining-treebasedontheirHammingDistance.首先，這些序列已經(jīng)比對(duì)好了，多重序列比對(duì)算法很復(fù)雜，手算基本不可能，所以題目如果給定序列要求構(gòu)建系統(tǒng)發(fā)生樹(shù)（進(jìn)化樹(shù)，那么他給定的序列一定是比對(duì)好的。我們要做的第一步是計(jì)算HmmngHmmng距離用來(lái)衡量?jī)蓚€(gè)序列相似程度，它被定義為un，umsmah個(gè)數(shù)，n表示序列長(zhǎng)度，我們把序列間的距離放在一個(gè)矩陣中：Neighbor-Joining算法是一種迭代算法，在每一次迭代中有3Step1taxa（s1-s510對(duì)）Q-criterion值，選取最小的一對(duì)作為我們的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同理我們計(jì)算其他組合的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），用新的結(jié)vd(vs20.4375d(vs30.3625，更新后的距離矩陣為：33topologys5，u和v000uv還原為原始的結(jié)點(diǎn)，因?yàn)槲覀円呀?jīng)計(jì)算了它和原始結(jié)點(diǎn)的關(guān)系，所以最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:這是運(yùn)籌學(xué)書(shū)上的定理，其實(shí)仔細(xì)想想顯而易見(jiàn)，如果覺(jué)得這樣不夠有說(shuō)服力的話(huà)，我們可以用類(lèi)似于2中的方法來(lái)證明。老師的PPT里就是這么做的。見(jiàn)下文)Whenthereare2edgesand3vertices,weknowtheconnectedgraphmustbeaFormoreedgesandvertices,whenweaddoneedgeandoneverticetothetree,wecouldn’t