Name
Abstract | ||
|---|---|---|
Network alignments are extensively used for comparing, exploring, and predicting biological networks. Existing alignment tools are mostly based on isomorphic and homeomorphic embedding and require solving a problem that is NP-complete even when searching a match for a tree in acyclic networks. On the other hand, if the mapping of different nodes from the query network (pattern) into the same node from the text network is allowed, then trees can be optimally mapped into arbitrary networks in polynomial time.In this paper we present the first polynomial-time algorithm for finding the best matching pair consisting of a subtree in a given tree pattern and a subgraph in a given text (represented by an arbitrary network) when both insertions and deletions of degree-2 vertices are allowed on any path. Our dynamic programming algorithm is an order of magnitude faster than the previous network alignment algorithm when deletions are forbidden. The algorithm has been also generalized to pattern networks with cycles: with a modest increase in runtime it can handle patterns with the limited vertex feedback set.We have applied our algorithm to matching metabolic pathways of four organisms (E. coli, S. cerevisiae, B. subtilis and T. thermophilus species) and found a reasonably large set of statistically significant alignments. We show advantages of allowing pattern vertex deletions and give an example validating biological relevance of the pathway alignment. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1109/BIBM.2008.75 | BIBM |
Keywords | Field | DocType |
query network,s. cerevisiae species,pattern network,t. thermophilus species,trees (mathematics),b. subtilis species,network patterns,acyclic network,microorganisms,homomorphism,limited vertex feedback set,arbitrary network,metabolic networks,metabolic pathways,previous network alignmentalgorithm,polynomial-time algorithm,text network,dynamic programming algorithm,homeomorphism,graph theory,fast alignments,biological networks,network alignment,bioinformatics,biological network,e. coli species,metabolic network alignments,tree pattern,metabolic pathway,polynomial time,metabolic network,statistical significance | Polynomial,Computer science,Theoretical computer science,Artificial intelligence,Graph theory,Dynamic programming,Embedding,Vertex (geometry),Biological network,Tree (data structure),Homomorphism,Bioinformatics,Machine learning | Conference |
ISSN | ISBN | Citations |
2156-1125 | 978-0-7695-3452-7 | 7 |
PageRank | References | Authors |
0.70 | 7 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Qiong Cheng | 1 | 7 | 0.70 |
| Piotr Berman | 2 | 1754 | 192.48 |
| Robert Harrison | 3 | 51 | 4.58 |
| Alexander Zelikovsky | 4 | 1691 | 244.62 |