پيدا كردن موتيف در شبكه هاي وزن دار برهم كنش پروتئين-پروتئين

چكيده انگليسي :

Finding Motifs in Weighted Protein Protein Interaction Networks Mahsa Imani m imaniaraghinezhad@ec iut ac ir Date of Submission 2011 04 26 Department of Electrical and Computer Engineering Isfahan University of Technology Isfahan 84156 83111 Iran Degree M Sc Language FarsiSupervisor Niloofar Gheissari n gheissari@cc iut ac ir pe Mahdi Sadeghi m sadeghi@ibb ut ac irAbstractBiological networks which are generally wide complicated networks contain important information Regarding to their remarkable growth in order to extract their information different works are done onthem Among the most important is to find network motifs Motif is defined as the patterns of interactionsthat are observed in the given network more frequently than random networks Studies have shown thatthese patterns are functionally significant So far many algorithms have been proposed for findingsubgraphs with high frequency in unweighted networks but they suffer from two essential limitations First most of the proposed methods are capable of finding motifs in unweighted networks Regarding tonetworks growth in recent decade studying other characteristics such as the nature of the coupling betweenedges weights which is beyond the topological characteristics of networks is of great importance Studyingweighted networks instead of unweighted networks let us examine the coupling between edges weights One of the main reasons for the lack of such studies is that considering edge weight poses novelcomputational challenges Another limitation of the most current motif finding techniques is that they onlyconsider induced subgraphs in counting subgraphs Counting the non induced occurrences of the networkmotifs is not only challenging but also quite desirable as available protein protein interaction networks arefar from complete and error free The reported interactions by these networks include many falseinteractions and miss many others An occurrence of a specific network motif in one network may includeadditional edges in its occurrence in another network and vice versa One of the problems which hinders thepattern analysis of graphs is that they are neither vectorial in nature nor easily transformed into vectors Inthis thesis a novel method is proposed to overcome the two shortcomings of the previous methods Unlikethe previous methods that use isomorphism exact matching in order to assign the found subgraphs intosimilar groups the proposed method use inexact graph matching Using inexact graph matching in availableprotein protein interaction networks that have high error is quite desirable The proposed method introducesconsensus motifs in which each edge weight shows the expected probability of its presence in the consensusmotif It takes advantages of symmetrical polynomial in order to construct spectral features of subgraphs Then it analyses and matches the resulting feature vectors by clustering instead of classification used inother methods The experimental results shows that including weights in finding motifs cause to finddifferent motifs and antimotifs in contrast to those found by other methods Also it shows not only thenature of the coupling between weights is not universal but also the coupling is related to the function ofthe network Keywords weighted protein protein interaction networks weighted motif inexact graph matching non induced subgraph subgraph spectral feathers clustering

ايماني، مهسا

پيدا كردن موتيف در شبكه هاي وزن دار برهم كنش پروتئين-پروتئين

انطباق غير دقيق گراف , زير گراف غير القايي , خوشه بندي