A large number of experimental biological network data of different types are becoming available due to advanced experimental techniques. Network alignment is considered to be one of the most common methods to analyze and compare biological networks to understand evolution, biological mechanisms, and the complexity of diseases. Kuchaiev, Milenkovic, Memisevic, Hayes, & Przulj (2010) recently proposed a topological method of network alignment based on graphlet degree signatures, called GRAAL, which can be used to align any kind of networks not just biological ones. Several global network alignment algorithms also have been designed based on GRAAL, such as MI-GRAAL, H-GRAAL, and C-GRAAL. However, the alignment of large networks necessitates the improvement of GRAAL algorithm in terms of both accuracy and computational efficiency.
In this paper, I present three kinds of modifications based on GRAAL, including modification on P value, modification on graphlet selection and modification on vector calculation. I applied the three modifications on several biological datasets. The results have shown that these modifications perform comparable to GRAAL, and the algorithm efficiency can be improved up to 90% without losing much accuracy.
","abstract_html":"<p>A large number of experimental biological network data of different types are becoming available due to advanced experimental techniques. Network alignment is considered to be one of the most common methods to analyze and compare biological networks to understand evolution, biological mechanisms, and the complexity of diseases. Kuchaiev, Milenkovic, Memisevic, Hayes, & Przulj (2010) recently proposed a topological method of network alignment based on graphlet degree signatures, called GRAAL, which can be used to align any kind of networks not just biological ones. Several global network alignment algorithms also have been designed based on GRAAL, such as MI-GRAAL, H-GRAAL, and C-GRAAL. However, the alignment of large networks necessitates the improvement of GRAAL algorithm in terms of both accuracy and computational efficiency.</p> <p>In this paper, I present three kinds of modifications based on GRAAL, including modification on P value, modification on graphlet selection and modification on vector calculation. I applied the three modifications on several biological datasets. The results have shown that these modifications perform comparable to GRAAL, and the algorithm efficiency can be improved up to 90% without losing much accuracy.</p>","abstract_has_math":false,"creators":["Jin, Shengai"],"institution":null,"degree_name":"Master of Science (MS)","degree_level":"Masters Thesis","degree_discipline":"Computing","degree_department":null,"school":null,"contributors":["Jonathan Sun","Chaoyang Zhang","Shaoen Wu"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2013,"date_issued":"2013-05-01T07:00:00Z","date_published":"2013-05-01T07:00:00Z","updated_at":"2026-07-24T05:45:06Z","subjects":[],"languages":[],"rights":[],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://aquila.usm.edu/masters_theses/536","outbound_label":"Repository record","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Jonathan Sun","Chaoyang Zhang","Shaoen Wu"]},{"key":"dc:creator","label":"Author","values":["Jin, Shengai"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.available","label":"Dc Date Available","values":["2018-11-15T08:00:00Z"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computing"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Masters Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Master of Science (MS)"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://aquila.usm.edu/masters_theses/536"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["A large number of experimental biological network data of different types are becoming available due to advanced experimental techniques. Network alignment is considered to be one of the most common methods to analyze and compare biological networks to understand evolution, biological mechanisms, and the complexity of diseases. Kuchaiev, Milenkovic, Memisevic, Hayes, & Przulj (2010) recently proposed a topological method of network alignment based on graphlet degree signatures, called GRAAL, which can be used to align any kind of networks not just biological ones. Several global network alignment algorithms also have been designed based on GRAAL, such as MI-GRAAL, H-GRAAL, and C-GRAAL. However, the alignment of large networks necessitates the improvement of GRAAL algorithm in terms of both accuracy and computational efficiency.
In this paper, I present three kinds of modifications based on GRAAL, including modification on P value, modification on graphlet selection and modification on vector calculation. I applied the three modifications on several biological datasets. The results have shown that these modifications perform comparable to GRAAL, and the algorithm efficiency can be improved up to 90% without losing much accuracy.
"]},{"key":"dc:title","label":"Title","values":["Topological Network Alignment Based on Graphlet Degree Signature"]}]}],"canonical_facts":{"dc:contributor":["Jonathan Sun","Chaoyang Zhang","Shaoen Wu"],"dc:creator":["Jin, Shengai"],"dc:date.available":["2018-11-15T08:00:00Z"],"dc:description.abstract":["A large number of experimental biological network data of different types are becoming available due to advanced experimental techniques. Network alignment is considered to be one of the most common methods to analyze and compare biological networks to understand evolution, biological mechanisms, and the complexity of diseases. Kuchaiev, Milenkovic, Memisevic, Hayes, & Przulj (2010) recently proposed a topological method of network alignment based on graphlet degree signatures, called GRAAL, which can be used to align any kind of networks not just biological ones. Several global network alignment algorithms also have been designed based on GRAAL, such as MI-GRAAL, H-GRAAL, and C-GRAAL. However, the alignment of large networks necessitates the improvement of GRAAL algorithm in terms of both accuracy and computational efficiency.
In this paper, I present three kinds of modifications based on GRAAL, including modification on P value, modification on graphlet selection and modification on vector calculation. I applied the three modifications on several biological datasets. The results have shown that these modifications perform comparable to GRAAL, and the algorithm efficiency can be improved up to 90% without losing much accuracy.
"],"dc:identifier":["https://aquila.usm.edu/masters_theses/536"],"dc:title":["Topological Network Alignment Based on Graphlet Degree Signature"],"thesis:degree_discipline":["Computing"],"thesis:degree_level":["Masters Thesis"],"thesis:degree_name":["Master of Science (MS)"]},"updated_at":"2026-07-24T05:45:06Z"}