Skip to main content
SUPERVISOR
Zeinab Maleki,Naser Ghadiri modaress
زینب مالکی (استاد مشاور) ناصر قدیری مدرس (استاد راهنما)
 
STUDENT
Amirhossein Atashkar
امیرحسین آتشکار

FACULTY - DEPARTMENT

دانشکده مهندسی برق و کامپیوتر
DEGREE
Master of Science (MSc)
YEAR
1395

TITLE

Protein-Protein Interaction(PPI) network clustering based on multi-layer graph
The Bioinformatics Research Field is a new science that seeks to address biological issues in cellular and molecular fields using computers and bioinformatics databases. One of the areas of bioinformatics research is the identification and detection of protein clusters. Protein clusters are a group of proteins that, with each other's interaction, carry out a specific activity in living creatures. As a result, the design and implementation ofan algorithm that can carry out this high-precision clustering on proteins is considered by researchers in this field. So far, most of the proposed algorithms for clustering detect and extract protein clusters from a single source ofinformation. Since the Protein-Protein Interaction (PPI) networks have a large error, the approach of integrating different data sources makes the identified clusters more accurate. So, some clustering methods of PPI networks use the approach of integrating different data sources. Most of these algorithms first integrate the data sources together, and then run existing clustering algorithms for single-layer networks on the integrated network. Although this approach makes clustering more accurate than the use of only one data source, the loss of some important information during data integration does not result in good clustering. One way to use different data sources is to use multi-layer graphs. Unfortunately, the citation method for the clustering of PPI networks based on multi-layer graphs has not been introduced. In this research, a method is presented that uses multi-layer graph theory to cluster PPI networks with higher accuracy. In this way, different data sources, each of which is a layer of a multi-layer graph. All layers are initially integrated and a single-layer graph is created. Then, in the next step and in the next clustering process, in addition to the single-layer integrated graph, the information from each layer is also used separately to reduce the amount of information that is lost. In the proposed method, the multi-layer graph is made of three PPI networks. Also, the results obtained from the clustering algorithm are compared with the clusters of the four gold standard data sets. Comparison results show that in the proposed method, the value of F-measure is higher than other methods. Also, in the Precision and Recall value, the results are improved. Key Words:Clustering, Protein complexes, Protein-protein interaction networks, Graph theory,Multi-layer graphs
زه‌ی تحقیقاتی بیوانفورماتیک، علم جدیدی است که در آن سعی می‌شود تا با استفاده از رایانه‌ها و بانک‌های اطلاعاتی زیستی، به مسائل بیولوژیکی در زمینه‌های سلولی و مولکولی پاسخ‌داد. یکی از زمینه‌های تحقیقاتی بیوانفورماتیک، تشخیص و شناسایی خوشه‌های پروتئینی است. خوشه‌های پروتئینی، گروهی از پروتئین‌ها هستند که با همکاری یک‌دیگر، فعالیت خاصی را در سلول موجودات زنده انجام می‌دهند. در نتیجه، طراحی و پیاده‌سازی الگوریتمی که بتواند این خوشه‌بندی را با دقت بالا بر روی پروتئین‌ها انجام دهد، مورد توجه محققان این حوزه قرار گرفته‌است. تاکنون بیشتر الگوریتم‌های معرفی شده به‌منظور خوشه‌بندی، خوشه‌های پروتئینی را تنها از یک منبع اطلاعاتی شناسایی و استخراج می‌کنند. از آن‌جایی که داده‌های شبکه‌های تعاملی پروتئین-پروتئینی دارای خطای زیادی هستند، رویکرد ترکیب منابع مختلف داده‌ای باعث می‌شود تا خوشه‌های شناسایی شده، دقت بالاتری را داشته‌باشند. بدین‌منظور برخی از روش‌های خوشه‌بندی شبکه‌های پروتئینی، از رویکرد ترکیب منابع مختلف داده‌ای استفاده می‌کنند. بیشتر این الگوریتم‌ها، ابتدا منابع داده‌ای را با یک‌دیگر ترکیب کرده و در ادامه، الگوریتم‌های خوشه‌بندی موجود برای شبکه‌های تک‌لایه‌ای را بر روی شبکه‌ی ترکیب‌شده اجرا می‌کنند. اگرچه این رویکرد باعث می‌شود تا دقت خوشه‌بندی نسبت به حالت استفاده از تنها یک منبع داده‌ای، بالاتر برود اما از دست‌رفتن برخی از اطلاعات مهم حین ترکیب داده‌ها، خوشه‌بندی مطلوبی را نتیجه نمی‌دهد. یکی از روش‌های استفاده از منابع داده‌ای مختلف، استفاده از گراف‌های چندلایه می‌باشد. متأسفانه تاکنون روش قابل استنادی به‌منظور خوشه‌بندی شبکه‌های تعاملی پروتئین-پروتئین مبتنی بر گراف چند‌لایه معرفی نشده‌است. در این پژوهش، روشی ارائه شده‌است تا با استفاده از نظریه‌ی گراف‌های چندلایه، شبکه‌های تعاملی پروتئینی را با دقت بالاتری خوشه‌بندی می‌کند. در این روش، منابع مختلف داده‌ای، هر کدام یک لایه از گراف چندلایه‌ را تشکیل می‌دهند. تمامی لایه‌ها در ابتدا با یک‌دیگر ترکیب شده و یک گراف تک‌لایه ساخته می‌شود. سپس در ادامه و در مراحل بعدی خوشه‌بندی، علاوه بر گراف ترکیب‌شده‌ی تک‌لایه، از اطلاعات هر لایه نیز به‌صورت جداگانه استفاده می‌شود تا میزان از دست‌رفتن اطلاعات، کاهش‌یابد. در روش پیشنهادی، گراف چندلایه از سه مجموعه‌داده‌ای ساخته می‌شود. همچنین نتایج به‌دست‌آمده از الگوریتم خوشه‌بندی، با خوشه‌های چهار مجموعه‌داده‌ی مرجع استاندارد طلایی مقایسه‌شد. نتایج مقایسه نشان‌داد که در روش پیشنهادی، معیار F از سایر روش‌ها بالاتر است. همچنین در مقادیر دقت و فراخوانی نیز بهبود نتایج حاصل‌شد. کلمات کلیدی:?? خوشه‌بندی، خوشه‌های پروتئینی، شبکه‌های تعاملی پروتئین-پروتئین، نظریه گراف، گراف‌های چندلایه

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