{"id":{"repo_id":"uwo","oai_identifier":"oai:uwo.scholaris.ca:20.500.14721/35471"},"canonical_url":"https://search.dev.ndltd.org/etd/uwo/oai:uwo.scholaris.ca:20.500.14721/35471","repository":{"repo_id":"uwo","name":"Western University","base_url":"https://uwo.scholaris.ca/server/oai/request"},"display":{"title":"Protein-Protein Interaction Network Alignment","abstract":"Proteins are some of the building blocks of organisms. They usually perform their functions by interacting with each other and forming protein complexes. A protein -protein interaction network is a graph that consists of proteins as vertices and their interactions as edges. Protein-protein interaction network alignment is very important in identifying protein complexes and predicting protein functions. Many algorithms based on graph theory have been developed to improve the accuracy of alignment, but due to the sparsity of protein-protein interactions, the result is far from satisfactory. We propose to improve the network alignment through adding protein interactions to existing PPI networks. In order to assess the improvement, we devise four groups of experiments and compare their results. The quality of PPI network alignment is assessed through the number of known protein complexes that are discovered. Significant improvement is obtained, up to $70%$ additional complexes being discovered after adding interactions. Other consequences are observed as well. Out of the two programs we compare, AlignMCL and MaWISH, the former performs significantly better whereas the latter is more stable. Further, adding predicted PPIs is not as efficient as adding PPIs from existing databases. Finally, we show that smaller but more reliable sets of interactions perform better than larger PPI sets.","abstract_html":"Proteins are some of the building blocks of organisms. They usually perform their functions by interacting with each other and forming protein complexes. A protein -protein interaction network is a graph that consists of proteins as vertices and their interactions as edges. Protein-protein interaction network alignment is very important in identifying protein complexes and predicting protein functions. Many algorithms based on graph theory have been developed to improve the accuracy of alignment, but due to the sparsity of protein-protein interactions, the result is far from satisfactory. We propose to improve the network alignment through adding protein interactions to existing PPI networks. In order to assess the improvement, we devise four groups of experiments and compare their results. The quality of PPI network alignment is assessed through the number of known protein complexes that are discovered. Significant improvement is obtained, up to $70%$ additional complexes being discovered after adding interactions. Other consequences are observed as well. Out of the two programs we compare, AlignMCL and MaWISH, the former performs significantly better whereas the latter is more stable. Further, adding predicted PPIs is not as efficient as adding PPIs from existing databases. Finally, we show that smaller but more reliable sets of interactions perform better than larger PPI sets.","abstract_has_math":true,"creators":["Qian, Yu"],"institution":"The University of Western Ontario","degree_name":"M Sc","degree_level":null,"degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":[],"advisors":["Lucian Ilie"],"committee_chairs":[],"committee_members":[],"year":2014,"date_issued":"2014-12-16","date_published":"2014-12-16","updated_at":"2026-07-27T21:56:14Z","subjects":["protein-protein interaction","network alignment","PPI prediction"],"languages":["en_ca"],"rights":[],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/20.500.14721/35471","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Lucian Ilie"]},{"key":"dc:creator","label":"Author","values":["Qian, Yu"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2025-07-10T20:38:04Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2025-07-10T20:38:04Z"]},{"key":"dc:date.issued","label":"Date","values":["2014-12-16"]},{"key":"dc:publisher","label":"Institution","values":["The University of Western Ontario"]},{"key":"dc:type","label":"Dc Type","values":["thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_name","label":"Degree Name","values":["M Sc"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["protein-protein interaction","network alignment","PPI prediction"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["en_ca"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://hdl.handle.net/20.500.14721/35471"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["The thesis cover page in the PDF document includes references to Western University’s previous institutional repository platform, known as Scholarship@Western, and links to that platform (beginning with ir.lib.uwo.ca). In citing or referring to this thesis, use the DOI or handle from this page instead. Sample citation: Author name, \"Thesis title.\" (Year). Western University Open Repository. https://doi.org/10.71858/123456."]},{"key":"dc:description.abstract","label":"Abstract","values":["Proteins are some of the building blocks of organisms. They usually perform their functions by interacting with each other and forming protein complexes. A protein -protein interaction network is a graph that consists of proteins as vertices and their interactions as edges. Protein-protein interaction network alignment is very important in identifying protein complexes and predicting protein functions. Many algorithms based on graph theory have been developed to improve the accuracy of alignment, but due to the sparsity of protein-protein interactions, the result is far from satisfactory. We propose to improve the network alignment through adding protein interactions to existing PPI networks. In order to assess the improvement, we devise four groups of experiments and compare their results. The quality of PPI network alignment is assessed through the number of known protein complexes that are discovered. Significant improvement is obtained, up to $70%$ additional complexes being discovered after adding interactions. Other consequences are observed as well. Out of the two programs we compare, AlignMCL and MaWISH, the former performs significantly better whereas the latter is more stable. Further, adding predicted PPIs is not as efficient as adding PPIs from existing databases. Finally, we show that smaller but more reliable sets of interactions perform better than larger PPI sets."]},{"key":"dc:title","label":"Title","values":["Protein-Protein Interaction Network Alignment"]}]}],"canonical_facts":{"dc:contributor.advisor":["Lucian Ilie"],"dc:creator":["Qian, Yu"],"dc:date.accessioned":["2025-07-10T20:38:04Z"],"dc:date.available":["2025-07-10T20:38:04Z"],"dc:date.issued":["2014-12-16"],"dc:description":["The thesis cover page in the PDF document includes references to Western University’s previous institutional repository platform, known as Scholarship@Western, and links to that platform (beginning with ir.lib.uwo.ca). In citing or referring to this thesis, use the DOI or handle from this page instead. Sample citation: Author name, \"Thesis title.\" (Year). Western University Open Repository. https://doi.org/10.71858/123456."],"dc:description.abstract":["Proteins are some of the building blocks of organisms. They usually perform their functions by interacting with each other and forming protein complexes. A protein -protein interaction network is a graph that consists of proteins as vertices and their interactions as edges. Protein-protein interaction network alignment is very important in identifying protein complexes and predicting protein functions. Many algorithms based on graph theory have been developed to improve the accuracy of alignment, but due to the sparsity of protein-protein interactions, the result is far from satisfactory. We propose to improve the network alignment through adding protein interactions to existing PPI networks. In order to assess the improvement, we devise four groups of experiments and compare their results. The quality of PPI network alignment is assessed through the number of known protein complexes that are discovered. Significant improvement is obtained, up to $70%$ additional complexes being discovered after adding interactions. Other consequences are observed as well. Out of the two programs we compare, AlignMCL and MaWISH, the former performs significantly better whereas the latter is more stable. Further, adding predicted PPIs is not as efficient as adding PPIs from existing databases. Finally, we show that smaller but more reliable sets of interactions perform better than larger PPI sets."],"dc:identifier.uri":["https://hdl.handle.net/20.500.14721/35471"],"dc:language.iso":["en_ca"],"dc:publisher":["The University of Western Ontario"],"dc:subject":["protein-protein interaction","network alignment","PPI prediction"],"dc:title":["Protein-Protein Interaction Network Alignment"],"dc:type":["thesis"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_name":["M Sc"]},"updated_at":"2026-07-27T21:56:14Z"}