Skip to main content
SUPERVISOR
Mehdi Sadeghi,Nilofar Ghisari
مهدی صادقی (استاد راهنما) نیلوفر قیصری (استاد راهنما)
 
STUDENT
Mahsa Imani
مهسا ایمانی

FACULTY - DEPARTMENT

دانشکده مهندسی برق و کامپیوتر
DEGREE
Master of Science (MSc)
YEAR
1387
Biological 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 on them. Among the most important is to find network motifs. Motif is defined as the patterns of interactions that are observed in the given network more frequently than random networks. Studies have shown that these patterns are functionally significant. So far many algorithms have been proposed for finding subgraphs 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 to networks’ growth in recent decade, studying other characteristics such as the nature of the coupling between edges’ weights which is beyond the topological characteristics of networks, is of great importance. Studying weighted 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 novel computational challenges. Another limitation of the most current motif finding techniques is that they only consider induced subgraphs in counting subgraphs. Counting the non-induced occurrences of the network motifs is not only challenging but also quite desirable as available protein-protein interaction networks are far from complete and error free. The reported interactions by these networks include many false interactions and miss many others. An occurrence of a specific network motif in one network may include additional edges in its occurrence in another network and vice versa. One of the problems which hinders the pattern analysis of graphs is that they are neither vectorial in nature nor easily transformed into vectors. In this thesis a novel method is proposed to overcome the two shortcomings of the previous methods. Unlike the previous methods that use isomorphism (exact matching) in order to assign the found subgraphs into similar groups, the proposed method use inexact graph matching. Using inexact graph matching in available protein-protein interaction networks that have high error is quite desirable. The proposed method introduces consensus motifs in which each edge weight shows the expected probability of its presence in the consensus motif. 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 left; MARGIN: 0cm 0cm 0pt; unicode-bidi: embed; DIRECTION: ltr" dir=ltr align=left Keywords: weighted protein-protein interaction networks, weighted motif, inexact graph matching, non-induced subgraph, subgraph spectral feathers, clustering.
شبکه های زیست شناسی، که عموماً شبکه هاِیی پیچیده و وسیع هستند، حاوی اطلاعات مهمی می باشند. امروزه نظر به پیشرفتِ قابل ملاحظه آنها ، عملیاتی بر روی این گونه شبکه ها برای استخراجِ اطلاعاتی که هر کدام از آنها دربردارند اِعمال می شود. از میان مهم ترین آنها پیدا کردن موتیف های شبکه است. موتیف به صورت الگوهایی از ارتباطات تعریف می شود که در شبکه با فراوانی بیشتری نسبت به حالت تصادفی مشاهده می شود. تحقیقات انجام شده نشان می دهند که چنین ساختارهایی می توانند از لحاظ فعالیت در شبکه دارای اهمیت باشند. تاکنون، الگوریتم های مختلفی برای پیدا کردن زیرگراف های با فراوانی بالا در شبکه های بدون وزن ارائه شده که دو محدودیت اساسی دارند. اول آنکه تقریبا تمام این روش ها فقط قادر به پیدا کردن موتیف در شبکه های بدون وزن هستند. با توجه به رشد شبکه ها در طول دهه اخیر، بررسی خصوصیات دیگری نظیر ناهمگونی یال ها که ورای خصوصیات توپولوژیکی آنها است، نیز حائز اهمیت می باشد. بررسی شبکه های وزن دار به جای شبکه های بی وزن اجازه می دهد ناهمگونی یال ها در شبکه ها نیز مورد بررسی قرار گیرد. یکی از دلایل اصلی فقدان چنین مطالعاتی آن است که در نظر گرفتن وزن یال ها چالش محاسباتی جدیدی را ایجاد می کند. محدودیت دیگر روش های موجود آن است که در شمارش زیرگراف ها فقط زیرگراف های القایی در نظر گرفته شده است. در نظر گرفتن زیرگراف های غیر القایی یک موتیف شبکه در شبکه های برهم کنش پروتئین، مسئله ای چالش برانگیز وکاملا مطلوب است زیرا این شبکه ها تا کامل شدن و عاری از خطا بودن فاصله بسیار دارند. برهم کنش های گزارش شده توسط این شبکه ها شامل برهمکنش هایی می شوند که به طور اشتباه تشخیص داده شدند و نیز بسیاری از برهمکنش ها تشخیص داده نشده اند. بنابراین وقوع یک موتیف شبکه خاص دریک شبکه ممکن است شامل یال های اضافه در وقوعش در شبکه دیگری باشد و برعکس. یکی از دلایلی که تحلیل الگوهای گراف ها را دشوارتر می کند این است که آنها ذاتا به شکل بردار نیستند و به سادگی نیز قابل تبدیل به بردار نیستند. در این پایان نامه روش جدیدی برای حل دو مشکل مطرح شده در روش های قبل پیشنهاد داده شده است که بر خلاف روش های قبلی ، که هنگام نسبت دادن زیرگراف های یافت شده به گروه های مشابه به بررسی یک ریختی زیرگراف ها (انطباق دقیق) می پردازند، از تطبیق غیر دقیق گراف استفاده می کند. تطبیق غیر دقیق زیرگراف ها در شبکه های برهمکنش موجود که دارای میزان زیادی خطا هستند کاملا مطلوب است. روش پیشنهادی موتیف هایی وزن دار را معرفی می کند که وزن هر یال نشان دهنده امید حضور آن یال در موتیف اجماع حاصل است. برای این منظور با استفاده از چندجمله ای های متقارن ویژگی های طیفی زیرگراف ها بدست آورده می شود و سپس به انطباق وتحلیل بردارهای ویژگی حاصل با استفاده از خوشه بندی به جای طبقه بندی زیرگراف ها می پردازد. کلمات کلیدی: ، شبکه های وزن دار برهم کنش پروتئین، موتیف وزن دار، انطباق غیر دقیق گراف، زیرگراف غیر القایی، ویژگی های طیفی گراف، خوشه بندی

ارتقاء امنیت وب با وف بومی