Title: Expanding on existing methods for querying pathways in a protein-protein interaction network
Team members: Bhavik Gandhi, Michael Kane, Ashutosh Ranjan
Abstract: Our goal is to understand coloring techniques in protein-protein interaction pathways and possibly improve upon the random coloring scheme used in existing methods. Existing methods like QNet and QPath extend sequence comparison to the realm of measuring similarity between protein-protein interactions. But protein-protein interaction comparison involves comparing graphs which is a NP Complete problem, so to reduce the complexity, a random coloring scheme is used at the cost of reduced accuracy. Our aim is to explore possibly better coloring schemes than simple random coloring.
Plan of Action: Implement the available technique for protein-protein interaction pathway comparison. Then explore coloring schemes which are not random and chose the most suitable one for the problem and compare the result with the current implementation in terms of accuracy and time complexity. The data sets of yeast and fly protein interaction networks will be downloaded from the Database of Interacting Proteins.
Planned workload distribution: As of right now, all three members will be working on implementing the existing technique and researching the coloring possibilities.
List of papers read/plan to read:
“QNet: A Tool for Querying Protein Interaction Networks” by Banu Dost et al
“QPath: a method for querying pathways in a protein-protein interaction network” by Tomer Shlomi et al
“Color-coding” by Noga Alon et al
“Efficient Algorihms in detecting signaling pathways in Protein Protein Interaction Networks” by Jacob Scott, Trey Idekker et al
“Algorithm Engineering for Color Coding with Applications to Signaling Pathway Detection” by Falk Huffner et al
“Torque: T0pology free querying of Protein Interaction Networks” by Sharon Bruckner et al
“Consistent Alignment of Metabolic Pathways without Abstraction” by Ferhat Ay et al
