Skip to Main Content
 

Global Search Box

 
 
 
 

Files

File List


22188.pdf (1.39 MB)

ETD Abstract Container

Abstract Header

Mutually Exclusive Weighted Graph Matching Algorithm for Protein-Protein Interaction Network Alignment

Dunham, Brandan
http://rave.ohiolink.edu/etdc/view?acc_num=ucin1470741019

Abstract Details

2016, MS, University of Cincinnati, Engineering and Applied Science: Computer Science.
Motivation: Understanding and analyzing proteins interacting within a species is a topic of interest in various biological studies. These interactions can be aligned as a full network, allowing research to view the system of interactions that occur globally. Given this global alignment, one common area of research is comparing the protein interactions produced by di?erent species to determine similarity. Results: In this paper, we analyze current alignment methodologies for both a constrained and an unconstrained version of the protein-protein interaction network alignment problem. We also provide a new algorithm, Mutual Exclusion Matching, which scores higher and ?nds larger alignments than most other algorithms. Finally, we analyze all algorithms tested in a variety of biological and topological measures, showing that Mutual Exclusion produces some of the best alignments found throughout the course of the study, including ?nding larger connected components, conserving a larger number of edges, and ?nding some of the highest biologically scoring alignments when compared to other algorithms. Code necessary for running Mutual Exclusion Matching, as well as some example datasets, can be found at: https://sourceforge.net/projects/mutual-exclusion-matching/
Yizong Cheng, Ph.D. (Committee Chair)
Jaroslaw Meller, Ph.D. (Committee Member)
Anca Ralescu, Ph.D. (Committee Member)
85 p.
Computer Science
protein interaction; weighted graph matching; Mutual Exclusion Matching; subisomorphism; graph alignment

Recommended Citations

Citations

  • Dunham, B. (2016). Mutually Exclusive Weighted Graph Matching Algorithm for Protein-Protein Interaction Network Alignment [Master's thesis, University of Cincinnati]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=ucin1470741019

    APA Style (7th edition)

  • Dunham, Brandan. Mutually Exclusive Weighted Graph Matching Algorithm for Protein-Protein Interaction Network Alignment. 2016. University of Cincinnati, Master's thesis. OhioLINK Electronic Theses and Dissertations Center, http://rave.ohiolink.edu/etdc/view?acc_num=ucin1470741019.

    MLA Style (8th edition)

  • Dunham, Brandan. "Mutually Exclusive Weighted Graph Matching Algorithm for Protein-Protein Interaction Network Alignment." Master's thesis, University of Cincinnati, 2016. http://rave.ohiolink.edu/etdc/view?acc_num=ucin1470741019

    Chicago Manual of Style (17th edition)

ucin1470741019
432
© 2016, some rights reserved.Creative Commons License Mutually Exclusive Weighted Graph Matching Algorithm for Protein-Protein Interaction Network Alignment by Brandan Dunham is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License. Based on a work at etd.ohiolink.edu.
This open access ETD is published by University of Cincinnati and OhioLINK.