zbMATH — the first resource for mathematics

Algorithms for topology-free and alignment network queries. (English) Zbl 1362.05123
Summary: In this article we address two pattern matching problems which have important applications to bioinformatics. First we address the topology-free network query problem: Given a set of labels \(L\), a multiset \(P\) of labels from \(L\), a graph \(H=(V_H,E_H)\) and a function \(\mathrm{Label}_H:V_H\to 2^L\), we need to find a subtree \(S\) of \(H\) which is an occurrence of \(P\). We provide a parameterized algorithm with parameter \(k=|P|\) that runs in time \(O^\ast(2^k)\) and whose space complexity is polynomial. We also consider three variants of this problem. Then we address the alignment network query problem: Given two labeled graphs \(P\) and \(H\), we need to find a subgraph \(S\) of \(H\) whose alignment with \(P\) is the best among all such subgraphs. We present two algorithms for cases in which \(P\) and \(H\) belong to certain families of DAGs. Their running times are polynomial and they are less restrictive than algorithms that are available today for alignment network queries. Topology-free and alignment network queries provide means to study the function and evolution of biological networks, and today, with the increasing amount of knowledge regarding biological networks, they are extremely relevant.
Reviewer: Reviewer (Berlin)

05C85 Graph algorithms (graph-theoretic aspects)
68W40 Analysis of algorithms
92C42 Systems biology, networks
Full Text: DOI
[1] Alon, N.; Yuster, R.; Zwick, U., Color coding, J. Assoc. Comput. Mach., 42, 844-856, (1995) · Zbl 0885.68116
[2] Ambalath, A. M.; Balasundaram, R.; Chintan, R. H.; Venkata, K.; Neeldhara, M.; Geevarghese, P.; Ramanujan, M. S., On the kernelization complexity of colorful motifs, (Proc. 5th International Symp. on Parameterized and Exact Computation, (2010)), 14-25 · Zbl 1309.68143
[3] Banks, E.; Nabieva, E.; Peterson, R.; Singh, M., Netgrep: fast network schema searches in interactomes, Genome Biol., 9, R138, (2008)
[4] Betzler, N.; Bevern, R.; Fellows, M. R.; Komusiewicz, C.; Niedermeier, R., Parameterized algorithmics for finding connected motifs in biological networks, IEEE/ACM Trans. Comput. Biol. Bioinform., 8, 1296-1308, (2011)
[5] Betzler, N.; Fellows, M. R.; Komusiewicz, C.; Niedermeier, R., Parameterized algorithms and hardness results for some graph motif problems, (Proc. 19th Annual Symp. on Combinatorial Pattern Matching, (2008)), 31-43 · Zbl 1143.68501
[6] Björklund, A.; Husfeldt, T.; Kaski, P.; Koivisto, M., Narrow sieves for parameterized paths and packings, (2010), CoRR · Zbl 1370.68321
[7] Björklund, A.; Kaski, P.; Kowalik, L., Probably optimal graph motifs, (Proc. 36th International Symp. on Theoretical Aspects of Computer Science, (2013)), 20-31 · Zbl 1354.68108
[8] Blin, G.; Sikora, F.; Vialette, S., Querying graphs in protein-protein interactions networks using feedback vertex set, IEEE/ACM Trans. Comput. Biol. Bioinform., 7, 628-635, (2010)
[9] Bruckner, S.; Hüffner, F.; Karp, R. M.; Shamir, R.; Sharan, R., Topology-free querying of protein interaction networks, J. Comput. Biol., 17, 237-252, (2010)
[10] Caspi, R.; Altman, T.; Dale, J. M.; Dreher, K.; Fulcher, C. A.; Gilham, F.; Kaipa, P.; Karthikeyan, A. S.; Kothari, A.; Krummenacker, M.; Latendresse, M.; Mueller, L. A.; Paley, S.; Popescu, L.; Pujar, A.; Shearer, A. G.; Zhang, P.; Karp, P. D., The metacyc database of metabolic pathways and enzymes and the biocyc collection of pathway/genome databases, Nucleic Acids Res., 38, 473-479, (2010)
[11] Chazelle, B., A minimum spanning tree algorithm with inverse-ackermann type complexity, J. Assoc. Comput. Mach., 47, 1028-1047, (2000) · Zbl 1094.68606
[12] Cheng, Q.; Harrison, R. W.; Zelikovsky, A., Homomorphisms of multisource trees into networks with applications to metabolic pathways, (Proc. 7th IEEE International Conf. on Bioinform. and Bioengineering, (2007)), 350-357
[13] DeMillo, R. A.; Lipton, R. J., A probabilistic remark on algebraic program testing, Inf. Process. Lett., 7, 193-195, (1978) · Zbl 0397.68011
[14] Dondi, R.; Fertin, G.; Vialette, S., Complexity issues in vertex-colored graph pattern matching, J. Discrete Algorithms, 9, 82-99, (2011) · Zbl 1222.05053
[15] Dondi, R.; Fertin, G.; Vialette, S., Finding approximate and constrained motifs in graphs, Theor. Comput. Sci., 438, 10-21, (2013) · Zbl 1297.05081
[16] Edmonds, J.; Karp, R. M., Theoretical improvements in algorithmic efficiency for network flow problems, J. Assoc. Comput. Mach., 19, 248-264, (1972) · Zbl 0318.90024
[17] Fellows, M. R.; Fertin, G.; Hermelin, D.; Vialette, S., Upper and lower bounds for finding connected motifs in vertex-colored graphs, J. Comput. Syst. Sci., 77, 799-811, (2011) · Zbl 1210.68060
[18] Fredman, M. L.; Tarjan, R. E., Fibonacci heaps and their uses in improved network optimization algorithms, J. Assoc. Comput. Mach., 34, 596-615, (1987)
[19] Garey, M. R.; Johnson, D. S., Computers and intractability: A guide to the theory of NP-completeness, (1979), W.H. Freeman New York · Zbl 0411.68039
[20] Guillemot, S.; Sikora, F., Finding and counting vertex-colored subtrees, Algorithmica, 65, 828-844, (2013) · Zbl 1263.05029
[21] Harvey, D.; Roche, D. S., An in-place truncated Fourier transform and applications to polynomial multiplication, (Proc. 35th International Symp. on Symbolic and Algebraic Comput, (2010)), 325-329 · Zbl 1321.65197
[22] Hüffner, F.; Wernicke, S.; Zichner, T., Algorithm engineering for color-coding with applications to signaling pathway detection, Algorithmica, 52, 114-132, (2008) · Zbl 1170.68048
[23] Koutis, I., Faster algebraic algorithms for path and packing problems, (Proc. 35th International Colloquium on Automata, Languages and Programming, (2008)), 575-586 · Zbl 1153.68562
[24] Koutis, I., Constrained multilinear detection for faster functional motif discovery, (2012), CoRR · Zbl 1248.68583
[25] Lacroix, V.; Fernandes, C. G.; Sagot, M. F., Motif search in graphs: application to metabolic networks, IEEE/ACM Trans. Comput. Biol. Bioinform., 3, 360-368, (2006)
[26] LaPaugh, A. S.; Rivest, R. L., The subgraph homeomorphism problem, J. Comput. Syst. Sci., 20, 133-149, (1980) · Zbl 0429.68060
[27] Lozano, A.; Pinter, R. Y.; Rokhlenko, O.; Valiente, G.; Ziv-Ukelson, M., Seeded tree alignment, IEEE/ACM Trans. Comput. Biol. Bioinform., 5, 503-513, (2008)
[28] Mano, A.; Tuller, T.; Béjà, O.; Pinter, R. Y., Comparative classification of species and the study of pathway evolution based on the alignment of metabolic pathways, BMC Bioinform., 11, S38, (2010)
[29] Mucha, M.; Sankowski, P., Maximum matchings via Gaussian elimination, (Proc. 45th IEEE Symp. on Foundations of Computer Science, (2004)), 248-255
[30] Pinter, R. Y.; Rokhlenko, O.; Tsur, D.; Ziv-Ukelson, M., Approximate labelled subtree homeomorphism, J. Discrete Algorithms, 6, 480-496, (2008) · Zbl 1160.90680
[31] Pinter, R. Y.; Rokhlenko, O.; Yeger-Lotem, E.; Ziv-Ukelson, M., Alignment of metabolic pathways, Bioinformatics, 21, 3401-3408, (2005)
[32] Schwartz, J. T., Fast probabilistic algorithms for verification of polynomial identities, J. Assoc. Comput. Mach., 27, 701-717, (1980) · Zbl 0452.68050
[33] Scott, J.; Ideker, T.; Karp, R. M.; Sharan, R., Efficient algorithms for detecting signaling pathways in protein interaction networks, J. Comput. Biol., 13, 133-144, (2006)
[34] Shamir, R.; Tsur, D., Faster subtree isomorphism, J. Algorithms, 33, 267-280, (1999) · Zbl 0949.68122
[35] Sharan, R.; Dost, B.; Shlomi, T.; Gupta, N.; Ruppin, E.; Bafna, V., Qnet: a tool for querying protein interaction networks, J. Comput. Biol., 15, 913-925, (2008)
[36] Shlomi, T.; Segal, D.; Ruppin, E.; Sharan, R., Qpath: a method for querying pathways in a protein-protein interaction networks, BMC Bioinform., 7, 199, (2006)
[37] Smoot, M.; Ono, K.; Ruscheinski, J.; Wang, P. L.; Ideker, T., Cytoscape 2.8: new features for data integration and network visualization, Bioinformatics, 27, 431-432, (2011)
[38] Tholey, T., A dynamic data structure for maintaining disjoint paths information in digraphs, (Proc. 14th International Symp. on Algorithms and Comput., (2003)), 565-574 · Zbl 1205.68133
[39] Tohsato, Y.; Matsuda, H.; Hashimoto, A., A multiple alignment algorithm for metabolic pathway analysis using enzyme hierarchy, (Proc. 8th International Conf. on Intelligent Syst. for Molecular Biol, (2000)), 376-383
[40] Vingron, M.; Waterman, M. S., Sequence alignment and penalty choice, review of concepts, case studies and implications, J. Mol. Biol., 235, 1-12, (1994)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.