運籌學方法、模型在生物信息學、系統(tǒng)生物學研究中的重要作用

1、1,章祥蓀,復雜網絡的社團結構分析Community structure in complex networks,http://zhangroup.aporc.org中國科學院 數學與系統(tǒng)科學研究院全國復雜網絡會議，蘇州大學， 2010，10, 17,Bio-molecular networks （生物分子網）,許多生物問題, 特別是人類的疾病, 在分子層面上都可歸于 “systems problems” --

2、 Leroy Hood 許多生物問題可以表達成生物分子網絡（bio-molecular networks）的問題。生物分子網絡包括：蛋白質相互作用網（ protein interaction networks）, 新陳代謝網（metabolic networks），基因調控網（ gene regulatory networks）, e.t.; 他們都有共同的性質 更為有趣的是，許多這樣的網是“復雜”網絡,2,3,,,復

3、雜網絡的典型代表:生物分子網絡之一 ---- 蛋白質相互作用網 （Scale-free),酵母細胞中的蛋白質相互作用網絡 (A.-L. Barabási, NATURE REVIEWS GENETICS, 2004),Jeong, 2000, Nature,包括太古代（ Archae），細菌（ Becterium), 真核生物（Eukaryote）在內的43個物種的 新陳代謝網（ Metabolic network ）都

4、是 Scale-free的。,4,Protein-protein interaction networks,Rui-Sheng Wang, Yong Wang, Ling-Yun Wu, Xiang-Sun Zhang, Luonan Chen.Analysis on multi-domain cooperation for predicting protein-protein interactions.BMC Bioinforma

5、tics, 8:391, 2007 Shihua Zhang, Xue-Mei Ning and Xiang-Sun Zhang.Identification of functional modules in a PPI network by clique percolation clustering.Computational biology and chemistry, 30(6), 445-451, 2006. Luo

6、nan Chen, Ling-Yun Wu, Yong Wang and Xiang-Sun Zhang.Inferring Protein Interactions from Experimental Data by Association Probabilistic Method.Proteins: Structure, Function, and Bioinformatics, Vol. 62, pp. 833-837, 20

7、06. Xiang-Sun Zhang, Rui-Sheng Wang, Ling-Yun Wu, Shihua Zhang and Luonan Chen.Inferring Protein-Protein Interactions by Combinatorial Models.IFMBE Proceedings, Vol.14, 2006, 183--186, Springer Berlin Heidelberg.,5,M

8、etabolic and signaling networks,Zhenping Li, Rui-Sheng Wang, Xiang-Sun Zhang and Luonan Chen. Detecting drug targets with minimum side effects in metabolic networks. IET Systems Biology, 3(6), 523-533, 2009 Zhenping

9、Li, Rui-Sheng Wang, Xiang-Sun Zhang.Mass Flow Model and Essentiality of Enzymes in Metabolic Networks.Lecture Notes in Operations Research, 9, pp. 182-190, World Publishing Corporation, Lijiang, 2008. Jin G, Zhou X,

10、Wang H, Zhao H, Cui K, Zhang XS, Chen L, Hazen SL, Li K, Wong ST The Knowledge-Integrated Network Biomarkers Discovery for Major Adverse Cardiac Events. J Proteome Res 7(9): 4013-4021,2008,6,Luonan Chen,

11、 Rui-Sheng Wang, Xiang-Sun Zhang.Biomolecular Networks: Methods and Applications in Systems Biology.John Wiley & Sons, Hoboken, New Jersey. July, 2009.,Book about Biomolecular networks,7,可分成564 個模塊，由 950 個顯著的塊間相互作用

12、相連接。,Yeast functional linkage network,DNA damage module,SCIENCE Vol 306(26) 2004,,復雜網絡的動態(tài)性質研究 復雜網絡的靜態(tài)結構研究小世界(Small world) ，尺度無關（Scale free)，聚類特性 (Clustering) 的確切數學模型。 社團結構 (Community Structure) …………,9,10,復雜網絡的

13、模塊化性質,復雜網絡中存在模塊或者社區(qū)結構 (Module or Community structure) 模塊或者社區(qū)定義為網絡中內部連接稠密，與外部連接稀疏的節(jié)點的集合 (Filippo Radicchi et. al. PNAS, Vol.101, No.9, 2658-2663, 2004). 數學表述: 其中V是子圖，K是頂點的度。即子圖 V 是模塊的條件是模塊內頂點的內部連邊的度值之和大于模塊內頂點的外

14、部連邊的度值之和。 PNAS ---- Proc. Natl. Acad. Sci. USA 美國科學院院刊,11,模塊劃分的重要性,許多復雜網絡共有的性質。研究模塊結構有助于研究整個網絡的結構和功能,圣塔菲研究所的科學家合作網：模塊代表從事相似領域研究的科學家集合,數學生態(tài)學,統(tǒng)計物理,12,Martin Rosvall, Carl T. Bergstrom, PNAS, vol. 105, no.4. 1118-1123,

15、 2007,自然科學論文引用網絡：6128期刊, 約600萬次引用，,劃分為88個模塊和3024條模塊間的連接，刻畫了學科之間的聯(lián)系,13,一個社會網絡的例子,1970年美國大學里的一個空手道俱樂部關系網絡：節(jié)點是其34名成員，邊是他們兩年間的友誼關系，邊數為78。俱樂部里的矛盾導致其分裂為兩個小的俱樂部。問題是能否用網絡的模塊結構來重現(xiàn)這個過程？它是模塊探測研究中的經典例子。,W. W. Zachary, An informati

16、on flow model for conflict and fission in small groups, Journal of Anthropological Research 33, 452-473 1977,Girvan, M, Newman, M., Proc. Natl. Acad. Sci, 2002Ravasz, E, Somera, A, Mongru, D, O

17、ltvai, Z, Barabasi, A., Science, 2002Radicchi, F, Castellano, C, Cecconi, F., Proc. Natl. Acad. Sci, 2004Guimera, R, Mossa, S, Turtschi, A., Proc. Natl. Acad. Sci, 2005Guimera, R, Amaral, L., Nature,

18、 2005Newman, M., Proc. Natl. Acad. Sci, 2006Rosvall, M, Bergstrom, C., Proc. Natl. Acad. Sci,

19、2007Fortunato, S, Barthelemy, M., Proc. Natl. Acad. Sci, 2007Weinan, E, Li, T, Vanden-Eijnden, E., Proc. Natl. Acad. Sci, 2008 Rosvall, M, Bergstrom, C., Proc. Natl. Acad. Sci,

20、 2008 Peter J. Mucha, et al., Science 2010 Yong-Yeol Ahn, James P. Bagrow & Sune Lehmann，Nature, 2010,生物信息學與最優(yōu)化方法,14,Importance of the to

21、pic,社團結構探索方法概述,A large number of methods have been developed for detecting communities, which can be generally categorized into local and global methods. Local methods （局部方法） for community detection identify a subset o

22、f nodes as a community according to certain local connection conditions, independently from the structure of the rest of the network. Such methods include clique overlap-based hierarchical clustering, clique percolati

23、on method, and sub-graph fitness method. Global methods （全局方法）for community detection optimize certain global quantitative functions encoding the quality of the overall partition of the network, such as information t

24、heoretical method, Potts model, and optimization of modularity measures.,15,16,,Shihua Zhang, Rui-Sheng Wang, and Xiang-Sun Zhang. Identification of overlapping community structure in complex networks using fuzzy c-mea

25、ns Clustering. Physica A, 2007, 374, 483–490.,Rui-Sheng Wang, Shihua Zhang, Yong Wang, Xiang-Sun Zhang, Luonan Chen. Clustering complex networks and biological networks by nonnegative matrix factorization with various s

26、imilarity measures. Neurocomputing, 2007,Shihua Zhang, Rui-Sheng Wang and Xiang-Sun Zhang. Uncovering fuzzy community structure in complex networks. Physical Review E, 76, 046103, 2007,我們小組在研究這一問題的早期發(fā)展了一些基于圖論和矩陣譜分解的模塊

27、探測算法 (local method),17,衡量網絡模塊化的指標Q值,設網絡為 N=（V，E）, Pk = { (V1, E1), …, (Vk, Ek)} 為一個分劃。L(Vi, Vj) =|Eij|, i in Vi, j in Vj.Newman 和 Girvan (Physical Review E, 2004) 提出一種衡量網絡社區(qū)結構的指標 Q 值,18,指標Q的問題 (Resolution limit)For

28、tunato and Barthélemy, PNAS, 2007,利用Q 劃分網絡的計算步驟: 目前很大一部分模塊探測的方法集中于利用各種啟發(fā)式算法來極大化Q值 ，例如模擬退火、遺傳算法等(Newman, PNAS, 2006; Guimera, Nature, 2005). Resolution limit 現(xiàn)象,19,極端例子：ring of cliques,,Fortunato &

29、Barthelemy, Proc. Natl. Acad. Sci. USA 104 (1), 36-41 (2007),20,提出新的模塊化指標D值,模塊化密度函數 D:,Zhenping Li, Shihua Zhang, Rui-Sheng Wang, Xiang-Sun Zhang, Luonan Chen, Quantitative function for community detection. Physical Re

30、view E, 77, 036109, 2008,21,D值克服了Q值存在的 resolution limit 問題,22,結果,Q值,D值,劃分正確的頂點的比例,錯分現(xiàn)象---Misidentification,用Q或D作優(yōu)化可能得到不滿足定義的模塊,Q partitions the network into three communities (two Kn and one K5) when n>=16 (respectiv

31、ely, n>=21), in which K5 is a sub-graph violating all reasonable community definition.,Xiang-Sun Zhang, Rui-Sheng Wang, Yong Wang, Ji-Guang Wang, Yu-Qing Qiu, Lin Wang, and Luonan Chen. Modularity optimization in co

32、mmunity detection of complex networks. Europhysics Letters (EPL), 87, 2009. 被評為 EPL 2009 best paper,23,24,該文的主要貢獻是用離散凸規(guī)劃的概念對兩個重要問題進行解析分析,Q 值和D 值的最優(yōu)化模型都是非線性整數規(guī)劃目標函數的凸性和凹性無法解析得到對兩個具有特殊結構的網絡進行分析引入離散凸規(guī)劃（變量是離散的，可以嵌入一個連

33、續(xù)的凸規(guī)劃）的概念進行分析, 得到解析解,所有對modularity進行研究的論文(指上面所列的的PNAS,Nature,Sience文章)都是試題論證的,即沒有解析的證明.為了徹底分析resolution limit和 Misidentification 現(xiàn)象，我們對兩類典型網絡建立了優(yōu)化模型,引入了離散凸分析技術,得到了兩類問題的解析解.,生物信息學與最優(yōu)化方法,25,,這兩個例子出現(xiàn)在PNAS中幾乎所有討論網絡模塊探測的論文里

34、,基于特殊結構的凸分析,ad hoc network,ring of dense lumps,Finding 1 對,生物信息學與最優(yōu)化方法,28,Finding 2,Finding 3,解析解表明，對這兩個經典的算例，Q和D都有Resolution limit和Misidentification的現(xiàn)象產生，所以Q 和D均只是近似的定量評估函數。 網絡社團劃分的問題可以用一個優(yōu)化問題來精確 描述，我們證明

35、了這一模型是NP-hard的。 我們相信用優(yōu)化理論可以徹底解決網絡社團劃分 的問題。網絡科學是運籌學的下一個熱點。,29,直接得到團環(huán)網絡的社團結構數值解,30,直接得到ad hoc網絡的社團結構數值解,31,,32,33,為了徹底解決這些問題,提出一個新的 OR 模型和相應的算法，這一算法不會產生resolution limit 和 mis-identification 現(xiàn)象關鍵思路：模塊分劃質量函數的定義要包含社團

36、定義。,Xiang-Sun Zhang, Zhenping Li, Rui-Sheng Wang, Yong Wang. A combinatorial model and algorithm for globally searching community structure in complex networksJournal of Combinatorial Optimization (JCO), 2010.,DOI: 1

37、0.1007/s10878-010-9356-0,A new OR model,Problem definition: Given a network, the community identification problem is to partition the network into as many non-overlapping sub-networks as possible such that each sub-

38、network satisfies a given community definition. 給定一個網絡和一個社團的定義，社團結構識別的問題就是將整個網絡分成盡可能多的滿足社團定義的子網絡。,34,以上文字定義可以用一個整數線性規(guī)劃來描述,我們證明了這個模型是 NP-hard .,35,A qualified min-cut (QMC) algorithm,A heuristic principle is given t

39、o find a feasible partition with the largest number of communities.It is realized by a min-cut operation: A min-cut operation is called qualified if the two resulting sub-networks satisfy the module definition. T

40、he community identification problem can be solved based on a series of qualified min-cut operations.,36,Experiment results (artificial networks),Rings of cliques,Uneven ad-hoc network,37,Experiment results (real networks

41、),Football team network,Jazz musician network,38,學術性的，實用性的問題遠遠沒有解決,Yong-Yeol Ahn, James P. Bagrow & Sune Lehmann，Nature, 2010 Link communities reveal multiscale complexity in networks,39,致謝,This wor

42、k is cooperated with Dr. 李珍萍，Dr. 王瑞省，Dr. 王勇，Dr. 張世華， Dr. 王吉光，Dr. 張俊華This work is supported by 國家自然科學重點基金10631070 973項目2066CB503905 國家自然科學基金項目60873205,40,ThanksWelcome to