2015聯(lián)賽一等獎-數(shù)學建模

題目DNA DNA是物種進化的載體，隨著DNA的不同可以隨之翻譯出不同的蛋白質(zhì)DNA于此就可以對DNA序列進行分類。ATGCDNA分析這八個物種因為堿基權(quán)重的不同造成的差異模型二其次利用代數(shù)中同態(tài)的思想和物理學中的“粗?；彼枷?，根據(jù)四DNAA，G，C，TDNA八個物種的DNA序列轉(zhuǎn)化為特征序列，采用壓縮矩陣的方法，將DNA序列轉(zhuǎn)化為以0、1數(shù)字組成的特征序列，由特征序列的同態(tài)的到DNA序列的三元組，由三元組中得出的頻率構(gòu)成24維向量。可以根據(jù)得到的24維向量計算DNA序列的相似性，這里采用計算24維向量的歐式距離對八個物種DNA有些不符合。于是建立模型三，提出一種新的將DNA序列和蛋白質(zhì)序列轉(zhuǎn)換成結(jié)構(gòu)矩陣的方法，即通過一維把DNA序列轉(zhuǎn)化為時間序列，即把數(shù)字1,2,3,4分別分配給組成DNA序列的核普酸A、T、G、C，用時間序列的結(jié)構(gòu)矩陣來描述DNA序列的結(jié)構(gòu)特征，并根據(jù)結(jié)構(gòu)矩陣的一些性質(zhì)定義了結(jié)構(gòu)矩陣的DNA模型以8個不同物種的-球蛋白的第一個外顯子驗證了該模型的適用性，：DNA序權(quán) 壓縮矩 特征序三元歐式距時間序結(jié)構(gòu)矩陣相似度題目的背

一、問題的重隨著DNA及蛋白質(zhì)技術(shù)的進步，以獲得海量的生物序列數(shù)據(jù)，對解讀生物序列數(shù)據(jù)中所含的各種信息，尤其是DNA序列中的遺傳及調(diào)控信息、蛋白析得到廣泛的應(yīng)用，每當獲得一個新的DNA序列，人們總是希望通過相似性比測未知序列的功能。顯然，如果新序列與已知的某種DNA序列具有同源性，將顯得尤為重要了。通過比較不同物種的DNA序列，得出其相似性，從而可以推題目的信e，C)和胸腺嘧啶(thymine，T)。DNA物種進化的載體，然而隨著DNA的不同我的數(shù)量與堿基之間位置關(guān)系。研究DNA序列的結(jié)構(gòu)及序列中隱藏的規(guī)律，成為生物信息學的重要研究課題。外顯子是最后出現(xiàn)在成熟RNA中的序列,又稱表達序列。既存在于最初的轉(zhuǎn)錄產(chǎn)物中，也存在于成RNA分子中的核苷酸序列。術(shù)語外顯子也指編碼相應(yīng)RNA外顯子的DNA中的區(qū)域。簡言之，外顯 在表達過程中能編碼蛋白質(zhì)的核苷酸序列表1中八個 題目的要求⑴根據(jù)表1提供的八個物種的外顯子從中構(gòu)建特征建立數(shù)學模型發(fā)現(xiàn)問題一

二、問題的分DNA序列分類是一個復(fù)雜的統(tǒng)計分析問題，數(shù)據(jù)量大，影響因素多，無法直DNA序列中提取出有效的特征。于是首先建立模型一分析堿基之間的數(shù)量關(guān)系，A.C.D.TDNADNA模型一雖然也能對物種進行差異性分析，但是不能描述DNA結(jié)構(gòu)的差采用”粗?；彼枷?，根據(jù)DNA序列中四種核苷酸A、G、C和T的化學結(jié)構(gòu)分類，提出DNA序列的特征序列的概念。一個DNA序列的特征序列是一組(0,1)序列，它們中的每一個都是這個DNA序列的一個簡約表示，而且用它們2×2矩陣來表示序列。進一步，計算這種壓，縮矩陣的最大特征值并把它作為DNA序列的一種不變量?；谶@些DNA序列的不變量分析了Human，Goat，Gallus，Opossum，Lemur，Mouse，Rabbit，Rat等八個物種的外顯子序列的相似性和非相似性；另外試圖通過比較特，問題二利用問題一的差異性分析物種進行分類后發(fā)現(xiàn)，分類結(jié)果與的認識有一定的差距。于是建立另一個對DNA結(jié)構(gòu)更深入分析的模型。即利用矩陣表示DNA序列結(jié)構(gòu)，提出結(jié)構(gòu)矩陣，以結(jié)構(gòu)矩陣為基礎(chǔ)建立DNA序DNADNA三、模型假假設(shè)所給的DN段中沒有發(fā)生突變與缺失并且能夠充分的反應(yīng)物種所4種堿基A、C、G、T4種堿基A、C、G、TDNADNADNA序列分類時,從堿基層次上進行分類,而不是從氨基酸層次上分類。四、符號說gjDNAjG：DNAmX:特征序列X（0,1）ijkN：DNAFR：表示(R，Y)-特征序FM：表示(M，K)FW：表示（W，S)Ui：24juijMS:一個nsij：矩陣中第ijsi：nDNAiMTM iMS1s1s1的結(jié)構(gòu)矩iMSMSMHMMHM MHMMHM矩陣的譜半 Sd(M1,M2): S

1矩陣與

2S2||Ms1||2MS1||Ms2||2：矩陣MS2五嘌呤一嘧啶：C=G,A=TA=U1ACGTA、T2（A、T）C、G個氫鍵供體（C,G）來稀疏矩陣的一種壓縮方式，也叫三元組表。假設(shè)以順序結(jié)構(gòu)來表示三元組表（tripletable），則得到稀疏矩陣富人一種壓縮方式，即三元二范數(shù)：矩陣A2范數(shù)就是AAAnn，λi，i1，2，……，n。稱ρ(A)=max{|λi|,i=1,2,……n}為A的譜半徑。即矩陣A的譜半徑等于矩陣A的六、模型的建立及求堿基含量的權(quán)重差異性比較分要分析DNA序列之間差異，都知道DNA差異表現(xiàn)在堿基之間的差異之上，首先就應(yīng)該分析A.T.G.C在DNA序列中所占不同的權(quán)重，進而可以從DNA模型一權(quán)重差異性比較的建計算物種DNA的序列中堿基的豐富度，用程序計算各個堿基的數(shù)并計算所占的，程序見后面附件2。ACACGT量ACGT

堿基含 堿基

模型一的比較結(jié)看出GACGAT（60%）由于在DNA序列中，雖然堿基的含量可以描述它的某些特征，但還不能全利用DNA序列的壓縮矩陣，可以對DNA序列進行差異性比較。其做法是：DNADNA序列差異性比較分由于在DNA序列中，雖然堿基的含量可以描述它的某些特征，但還不能全利用DNA序列的壓縮矩陣，可以對DNA序列進行差異性比較。其做法是：DNA模型二壓縮矩陣的建DNA序列的特征序同化學結(jié)構(gòu)或物化性質(zhì)的殘基或氨基酸看作是一樣的，并用0或l表示，這樣從四種核苷酸基的化學結(jié)構(gòu)入手，將它們分類，然后在DNA序列和一即單環(huán)嘧啶和雙環(huán)嘌呤。記R為嘌嶺，Y為嘧啶；即R={A，G}和Y={C，T}同樣的可以將這四個核酸基分為酮基和氨基兩類：即M={A，C}和K={G,T}。從DNA雙螺旋結(jié)構(gòu)的構(gòu)成還可以把四個核酸基分為弱氫鍵和強氫鍵兩組：即W={A，T}這樣的操作下，DNA序列就變?yōu)榱?0,1)序列．在這種變換下，有很多DNA序列對應(yīng)這一個(0，1)序列，這樣DNA序列自身的某些信息將會丟失，然而這種變 更容易對DNA序列比較和分析．更進一步，通過比較這些(0，1)序 可能顯示出嘌呤和嘧啶分類的生物功能。對于同一個DNA序列，設(shè)G=g1g2是一個DNA序列．根據(jù)上面的分類，定義三個字上的同i(G)i(g1)i(g2i=1，2，3)，(g)

1ifgjj 0ifgj(g)

1ifgjj 0ifgj(g)

1ifgjj 0ifgj這樣從一個DNA序列得到三個(0,1)序列分別稱它們?yōu)檫@個DNA序列的(R，DNA1．1DNA

S)-特征序列i(Gi(g1)i(g2）i=1，2，3)，如果gjR則1(gj)=1，果gjY，則1gj=0，如果gjM則2gj=l，如果gjK,則2gj=0；如果gjW，則3gj=1，如果gjS，則3gj=0．由上述的定義，對于DNA序列的每一個基gj，有一個(01)三元組1gj，2gj，3gj和T→0，0，1)，由這些對應(yīng)可以立即得到定理中的結(jié)論。如(R,Y)-特征序列：（3）101101010001100000111111111000100100100100001011110111101110101110011100110110111100001110111010011001001111111111100100100100110000011110111101111101110111100110100111100001110111 1 1 0 1 0001111111111100101001001001000110001111010111001100111001101101111000001101110110101001110010011111111101100010010011000001111011110110101100111010111100111100001100111011000010011101001111111101000101001000000010111101111011101011111111001101101111000011101110110010100011001101001111110001001000000100010111011111011100001101111001101101111000011101111011010100010001101111111110001011001001000010111101111011101011111111001101101111000011101011010100011001101001111111001001001101100010111111111011100001101101001101 0 1 0 1 1DNA引起一些序列的信息丟失，但上面定理告訴，只需要兩條特征序列就能將DNA序列的全部信息來即在一個特征序列中丟失的那部分信息一定包DNA征序列就可以了。構(gòu)造特征序列的壓縮矩陣并用它來比較DNA序列的異性。特征序列的壓縮矩在進行物種的進化分析時，一般的做法是把這些物種的同一個位點上的同一種 進行比較并做同源性分析以此來判斷這些物種之間的同源關(guān)系在這一節(jié)， 取八個不同的物種的β-球蛋白的第一個外顯子它們被認為是非常保守的序列，即進化很慢的序列。表1列出了這八個序列。先寫出它們的特征序列，然后搜索每一個特征序列中三元組出現(xiàn)的個數(shù)，并利用這些個數(shù)進行比較．在這里運用C語言進行計算八個物種的特征序列，（詳見附件3），它們的特征序列見表2（附件4），其中第一行為它們的(R，Y)-特征序列，第二行為(M，K)-特征序列，第三行為(W，S)-特征序列。用特征序列8種可能出現(xiàn)的三元組即000，001，00，011，100，101，110，111，建立一個2×2x2立方體矩陣，矩陣的元素表示每種三元組出現(xiàn)的頻率，即fX=100mX/(N-2)mX表示在特征序列X中(0,1)三元組巧ijk

NDNA用FR、FMFW來表示(R，Y)-，(M，K)-和（W，S)-特征序列的立方體矩陣。FX2×2FXFX FXfXFX=（fX），XR，MW 0 1 表3-5列出了這八個物種的β-球蛋白的第一個外顯子序列的特征序列的壓縮矩陣表示。每一個表中2×2的矩陣的表頭表示三元組(i,j,k)第一個分量ijk3-5，能看到011(YRR)110(RRY)顯示了很小的類似地，在(M，K)-特征序列中，出現(xiàn)最多的三元組是000(KKK)(除了goat101(MKM)111(MMM)兩個三元組。在(W,S)一特征序列中，010(SWS)111(WWW)分別是出現(xiàn)最多和出現(xiàn)最少的三元組；000(SSS)是變化最大的三元組，而三元組001(SSW)，011(SWW)和100(WSS)顯示出的變化非常小。于是列出三個特征序列中三元組ijk3-5（454），3.（R，Y）ijk001101000011010600110107100110101001101090900110100181001101009001101070191下面用矩陣的不變量來顯示這八個DNA序列的某些信息。對于矩陣的多信息包含在它的最大特征值中。這里，DNA6越大，反之則越小。觀察表6能得到這八個DNA序列的一些共同特性。fMfM(GoatGallus 在表6中的每一行有較大的值的矩陣是FR,FM,FW從這個結(jié)果能 列中出現(xiàn)最多的核酸基是G。表6的程序見附件6.DNAFFFFFF FFFFFF 利用特征序列的壓縮矩陣比較DNA序利用表3-5中三元組出現(xiàn)的頻率值，構(gòu)造一個24維向量，它是由在三個特越相似。有兩種方法計算矩陣的差異性：計算兩個向量的歐氏距離，如兩個向量的歐氏距離較小就認為這它們差異較小。用U1和U2表示兩個24維U1u1u1u1)和U2u2，u2，…，u

)．它們的距離定義為d(U1 ii1iiU2)=(24(u1u2)2)2。在表7中 列出了所有八個物種的β-球蛋247：表7.八個序列的差異性表（24維向量的歐氏距離 OpossumLemur 17.435617.320516.248115.748 11.40188.7749614.3875模型二的較大。從表看出物種Gallus是八個物種中與其它物種差異最大的一個物種，因為它對應(yīng)的值比較大。從這一點猜測（W,S）-特征序列可能隱含著哺乳動Mouse-Rat，Lemur-Rabbit和Mouse-Rabbit對的值都比較小，說明它們之間差異很小。猜測，這也許是某些相近物種引起的。但是有些物種的差異性與問題二1結(jié)構(gòu)矩陣的模型分由問題一得，Human-Rabbit，Human-Mouse，Mouse-Rat，Lemur-Rabbit和Mouse-Rabbit對的值都比較小，即差異性較小。所以將Human,Rabbit,Mouse,Rat,LemurGoat,Gallus,OpossumMouse-Rat和Mouse-Rabbit對的相似性對來說并不奇怪，然而Human-Rabbit，Human-Mouse和Lemur-Rabbit對的差異性卻與的直觀有相由于由問題一得出的問題二的結(jié)果與的直觀有些距離，因此提出一種DNADNADNADNAnDAnDNA不變量來描述結(jié)構(gòu)矩陣或DNADNA序列。進而對DNA原始序列進行相似性比較選用了8個不等長的DA8DNA8個不同物種的盡球蛋白的第一個外顯子DNA序列DNA結(jié)構(gòu)矩陣模型的建DNA序列的時序要分析DNA序列就要將它通過某種規(guī)則成一維或者離散的時間序列，表示為實數(shù)或復(fù)數(shù)值，這種方法稱為DNA時序化，即把DNA序列轉(zhuǎn)化為時把DNA序列可看成字符集N={A,C,G,T}上的一個詞。首先給DNA序列，然后把DNA序列看成一個具有t個元素的有限全序集合，它等同于{t}={1,2，···，t},給出一 22（t=

tAtTtGt任何長度的DNA序列對應(yīng)的一維時間序列，如Human的-球蛋白 AGTTGGTGGTGAGGCCCTGGGCAG：Human:1233234 344323334 312213。（DNA序列的結(jié)構(gòu)矩陣S=

作si1ns1s2，···，sn的結(jié)構(gòu)矩陣Ms是一個n sisM=（s），s= s

-

s 計算機構(gòu)矩陣的c6結(jié)構(gòu)矩陣的性性質(zhì)1：結(jié)構(gòu)矩陣M=（s）為稱矩陣，即MT=-M (MMH 2：M(MMH s1MTMHM MHMM2M（M）MMH，故M=（s）||

||=(MHM

s 3DNAs1s2，···smDNA時間序列s1s2，···sksk1，···snmDNAA=（aij），B=(bijaijbij4：每一個nDNAn證明：由于n維生物時間序列的數(shù)值排序總數(shù)為Cn11Cn2 1n(+C1（n-1）！,而稱矩陣A=（a），a=1、0或-1這樣矩陣總數(shù)為 ，

1n( 因為Cn11！+Cn2 +

（n-1）！

n1!

n

+····

，只需要證明 +

1n(

1n(即可。也就是n+(n-1)+····+n! n1!n n=1

+····+n!=n+(n- +n!=nn1!n n[(n-1)+(n-1)(n- +（n-1n(1n(

，下面證明n+n(n- +n1 成立，由于n+n[(n-1)+(n-1)(n-2)+····+（n-1）！]n+ 1只需要nn

1n( 1n(n

1n(- 1n(n1n(

因為

1且n2，只需要n3n1-n)2n3n1(x設(shè)函數(shù) =3x1-2x,對該函數(shù)(x因為ln3>1,3x1ln3-2 (x

1n(3x1ln3-2 (x 成立即Cn11！+Cn2 +C1（n-1）！

又設(shè)s1，s1，····，s1與s2，s2 ，s2，是不同的時間序列，那么他們 結(jié)構(gòu)矩陣是M=（s1）， =（s2）則存在ij使 （s1s1）（s2s2）=（s1s1）（s2s2）所以（s10）（s2=-1） （s1=-1）（s20）即

n維生物時間序列，唯一地確定一個n結(jié)構(gòu)矩陣相似ii定義1：設(shè)兩個n維生物（DNA）時間序列s1s1s2s2的結(jié)構(gòu)矩陣分iiM=（s1

=（s2），則 =（s1）

=（s2）的相似度定義

S

S i,i,jn|ss 2 d(Ms1,Ms2)=2n(n1)||Ms1Ms2||F=2n(n 1）d(MM 2）d(M1,M2)=d(M2,M1 1 s2 1 3 3 s s s3）d(M,M)d(M1 s2 1 3 3 s s s4）d(M1M2s1s1s2s2 ii定義2:設(shè)兩個m、nDNA時間序列s1s1s2s2的結(jié)構(gòu)矩陣分別iiM=（s1） =（s2 S 則M=（s1）與 =（s2）的相似度定義 S (MHM (MH(MHM (MHM s11(|||1

||M

||2|)

1[| 1）d(MM 2）d(M1,M2)=d(M2,M1 1 s2 1 3 3 s s s3）d(M,M)d(M1 s2 1 3 3 s s sd(M1M2s1s1s2s2 DNA序列相似3nDNAn因此利用DNA序列對應(yīng)的結(jié)構(gòu)矩陣不變量（如結(jié)構(gòu)矩陣的特征值、范數(shù)、譜半徑），用這些不變量來描述結(jié)構(gòu)矩陣或DNA序列，即用這些不變量來定量表示DNADNA1DNA序列相似性比較，定義2適合比較不等長的DNA序列相似性比較，因為選用了8個不等長的DNA序列，但是數(shù)據(jù)太大不便計算，所以選取每個物種308DNA18DNA這里采用對下表進行計算a=[...]%輸入矩陣b=[...]%輸入矩陣c=a-f=max(eig(e))%求e的譜半徑g=sqrt(f)%求e的二范數(shù)h=size(a)%a矩陣的維數(shù)m=2.^(-1)*h.^(-1)*i.^(-1)*g%等長的DNAt00000000（文中的數(shù)據(jù)都是以10-3為單位結(jié)8人和關(guān)系比較遠與兔關(guān)系較近距兔最遠的是鼠類(負鼠老鼠大較近的親緣關(guān)系。這符合根據(jù)形態(tài)特征對物種分類構(gòu)建的進化關(guān)系和其他方法得到的結(jié)果。由表格得到原雞的與其他物種的親緣關(guān)系都較遠，故吧原雞歸為一類。另外，雖然人與鼠類形態(tài)特征相差甚遠，但國際人類組研究小組公布老鼠與現(xiàn)代智人組有驚人的相似之處，因此在這里得到的人、狐猴與鼠類比較相近的結(jié)果也符合實際。因此把八個物種的DNA分為3類第一類：human（人）Lemur（狐猴）Mouse（老鼠）Opossum（負鼠）Rat（大第二類：Goat（）Rabbit（兔子）。八、模型改優(yōu)點：問題一模型一權(quán)方法簡單，直觀。模型二引入了DNA序列比較了序列的差異性，盡管結(jié)果還不太令人滿意，但從比較結(jié)果中可以看出30DNADNA定性作用的堿基。將模型立不同維數(shù)的矩陣進行更全面的分析。模型三中DNA2DNA九、參考資[1]、但，數(shù)學建模與數(shù)學實驗（第三版），:高等教育[2]徐國祥，統(tǒng) 與決策（第四版）， 財經(jīng)大學[3] 高等教育[4]，DNA序列與數(shù)學分析簡介，數(shù)學（）,1994.46-[6]全，信使RNA三維遺傳信息的研究，中國科學基金，1998,32-[7]，基于知識發(fā)現(xiàn)的生物信息學，生物工程進展，2000,27-[8]，新，，之，隱型用于蛋白質(zhì)序列分析，生物[9]，，蛋白質(zhì)分子結(jié)構(gòu)，DNA2000，289-賀平安，DNA，，基于結(jié)構(gòu)矩陣的DNA的相似性模型，數(shù)學的實踐與認識，4023，2010十、附1：DNA1)Human人類GoatOpossumGallusLemur狐猴Mouse老鼠RabbitRat大鼠附件2：用計算的堿基個數(shù)的編寫程sort_str1=sort(str1)j=1;fori=1:length(sort_str1)-ifstrcmp(sort_str1(i),sort_str1(i+1))~=1j=j+1;str2(j)=str2(j+1) fori=str_num=strfind(sort_str1,str2(i))count(i)=length(str_num);3：用CDNA#definex15#defineyvoidcharToInt(char*p)//charDNA{ints[x][y]={0};/intinti=0,j=0;{{casecasecasecase}{{printf("%d}}}void{}3：C（2）100000111100110110010010110010011000110011100000001110000111000010011000000000010011100001101001001100100100101100100110011110010010000011100001110000100110000000100100111000011010000011100011001001001011011100110111011110100001011000011000001111011000000001001110000110100000111000110010010010110110101101111001101000001110001100000110110000000110110111000111001001100001001000100100101100101100011110101000000011100000100010101110000000010100110000011010000001111001100100100101100100100010100011000000111100001111110100110000000000100111000011001000001101000111000100101100100100011100111000000011100001100000110110000000000100111000011 0 0 1 1 0 0 0 1 0 1 0 0 0 1 0 0 1 0 1 1 0 0 0 0 0 0 0 1 0 11111001001001010100101001011010100001110100001010000011001011001001111101100100101000001000010100101010010100 0 010000011010000011001011101001101101100100101000001000010110010010110101101010010110110100110101100110100101110010010011010010101001001010000011000101100100101001010010100101100100101101000000101000001100111101000001110100000001100001000010110101110010101001010010111001011010100101010100000110010011011010111011001000010000110000101100110010010101011001010110101001010101100010100001110010110000011011011001001010000010000100110010011010100101010010110101000010101000010100000110010111010011011011001001010000010000110010010011101011001010110001101011101000010100001110010110001011111011000001010000010000104（4.（M，K）ijk001101070011010160011010180011010900110109400110101 （5.（W，S)ijk0011010182001101011001101018200110104000110100011010001101019100110100用求壓縮矩陣特征值a X- - -Lamda 6DNACcharDNA[100];intintDNA_matrix[100][100];intmain(){inti,j,n=for(i=1;i<=n;{}for(i=0;i<=n;{{caseDNA_t[i]=case'B':DNA_t[i]=case'C':DNA_t[i]=case'D':DNA_t[i]=}}for(i=1;i<=n;{for(j=1;j<=n;{if(DNA_t[i]>{DNA_matrix[i][j]=}elseif(DNA_t[i]<{DNA_matrix[i][j]=-}{DNA_matrix[i][j]=}}}for(i=1;i<=n;{for(j=1;j<=n;{}}return}123323 3443 3334 3122112123323432341243323324211331232343424121232342341232433433334113312322343423324222344232333411133312311232341242324432423433243233334131123234342326，0-0------0----0--000---10-1-000-0-10--0-1--1110-01101-1110101010-10100101110-10-0------0----0--000---11110111101111110111111111110110-1-000-0-10--0-1--1110-010-1-000-0-10--0-1--1110-010-1-000-0-10--0-1--1110-01101-1110101010-10100101110-111110111101111110111111111110110-1-000-0-10--0-1--1110-01101-1110101010-10100101110-10-0------0----0--000---1101-1110101010-10100101110-110-1-000-0-10--0-1--1110-01101-1110101010-10100101110-111110111101111110111111111110110-1-000-0-10--0-1--1110-01101-1110101010-10100101110-10-0------0----0--000---1101-1110101010-10100101110-11101-1110101010-10100101110-10-0------0----0--000---1101-1110101010-10100101110-10-0------0----0--000---0-0------0----0--000---10-1-000-0-10--0-1--1110-01101-1110101010-10100101110-111110111101111110111111111110110-1-000-0-10--0-1--1110-00----0---0----0--000-00-10--0-1-00-100-0-1--111-11-110010-1-110111-101001011011-110010-1-110111-101001011011-10--0-1-00-100-0-1--111-11-110010-1-110111-101001011011-1111110101111011011111111111100----0---0----0--000-00-11111101011110110111111111111010--0-1-00-100-0-1--111-11-10--0-1-00-100-0-1--111-11-110010-1-110111-101001011011-0----0---0----0--000-00-11111110101111011011111111111110--0-1-00-100-0-1--111-11-10--0-1-00-100-0-1--111-11-11111101011110110111111111111010--0-1-00-100-0-1--111-11-110010-1-110111-101001011011-0----0---0----0--000-00-110010-1-110111-101001011011-110010-1-110111-101001011011-0----0---0----0--000-00-110010-1-110111-101001011011-0----0---0----0--000-00-0----0---0----0--000-00-110010-1-110111-101001011011-0----0---0----0--000-00-0----0---0----0--000-00-1111110101111011011111111111100-1-1-1-1-0-1-1-1-1-1-0-1-0-00-1-1-1-1-1-1-1-1-1-10--01-0-0-1--111---0---0-110-101-10-10100101100-10--01-11101110110111111111110110011010--01-0-0-1--111---0---0-110-101-10-10100101100-10--01-0---0-----0--000--------11101110110111111111110110011010--01-0-0-1--111---0---0-110-101-10-10100101100-10--01-11101110110111111111110110011010--01-0-0-1--111---0---0-110-101-10-10100101100-10--01-0---0-----0--000--------110-101-10-10100101100-10--01-110-101-10-10100101100-10--01-0---0-----0--000--------110-101-10-10100101100-10--01-0---0-----0--000--------0---0-----0--000--------110-101-10-10100101100-10--01-110-101-10-10100101100-10--01-11101110110111111111110110011010--01-0-0-1--111---0---0-110-101-10-10100101100-10--01-111011101101111111111101100110111101110110111111111110110011110-101-10-10100101100-10--01-10--01-0-0-1--111---0---0-1110111011011111111111011001100-----0---0----0--000-0-10--0-1-0--10--0-1--111-1-110010-1-100110-101001011010110010-1-100110-10100101101010--0-1-0--10--0-1--111-1-110010-1-100110-1010010110101111110101111011011111111110110----0---0----0--000-0-11111101011110110111111111101110--0-1-0--10--0-1--111-1-110010-1-100110-101001011010110010-1-100110-1010010110100----0---0----0--000-0-11111101011110110111111111101110--0-1-0--10--0-1--111-1-110010-1-100110-10100101101011111101011110110111111111101110--0-1-0--10--0-1--111-1-110010-1-100110-1010010110100----0---0----0--000-0-110010-1-100110-101001011010110010-1-100110-1010010110100----0---0----0--000-0-110010-1-100110-1010010110100----0---0----0--000-0-0----0---0----0--000-0-110010-1-100110-1010010110101111110101111011011111111110110----0---0----0--000-0-110010-1-100110-1010010110100--0-1--1--1--1-0--1--1--0-1-0-00-1--1-10-1-000-0-10--0-1--1110-01101-1110101010-10100101110-10-0------0----0--000---11110111101111110111111111110110-1-000-0-10--0-1--1110-010-1-000-0-10--0-1--1110-010-1-000-0-10--0-1--1110-011101-11110-1101010-110100101110-11110111011110111111011111111110110--000-0-10--0---1110-0110-1110101010-1000101110-10-------0------000---110-1110101010-1000101110-110--000-0-10--0---1110-0110-1110101010-1000101110-1111011110111111011111111110110--000-0-10--0---1110-0110-1110101010-1000101110-10-------0------000---110-1110101010-1000101110-1110-1110101010-1000101110-10-------0------000---110-1110101010-1000101110-10-------0------000---0-------0------000---10--000-0-10--0---1110-0110-1110101010-1000101110-1111011110111111011111111110110--000-0-10--0---1110-00--1--1--1-0--1--0-1--0-1--1-0-00--1-10--00--1-0-1-0-10-0-1-110-1100110-1-101-10110-10101101-1100110-1-101-10110-10101101-10--00--1-0-1-0-10-0-1-110-10--00--1-0-1-0-10-0-1-110-1100110-1-101-10110-10101101-1111111010011101111101111111100-----0---0---0----0-00--11111110100111011111011111111011111110100111011111011111111010--00--1-0-1-0-10-0-1-110-1100110-1-101-10110-10101101-0-----0---0---0----0-00--11111110100111011111011111111010--00--1-0-1-0-10-0-1-110-1100110-1-101-10110-10101101-0-----0---0---0----0-00--10--00--1-0-1-0-10-0-1-110-1100110-1-101-10110-10101101-111111101001110111110111111110 110-1-100-1-11-1-10-11-10-110-1-10-11-111-10-110011-1-1-111-110-10101101-0-1-1-1-1-1--0-1-1-1-0--1-0--1-1--0-00-1-1-110011-1-1-111-110-10101101-0-1-1-1-1-1--0-1-1-1-0--1-0--1-1--0-00-1-1-0-1-1-1-1-1--0-1-1-1-0--1-0--1-1--0-00-1-1-11011-1-1-11