##### Index

1 Maximum Clique1.1 Surveys / Theory

1.1.1 Bounds

1.2 Stochastic Local Search algorithms

1.3 Applications

1.4 Exact methods

1.4.1 Bron-Kerbosch and variants

1.4.2 Other exact methods

1.5 Continuous formulations

1.6 Instances

1.6.1 DIMACS

2 Generalisations

2.1 Quasi-Cliques

2.1.1 Stochastic Local Search algorithms

2.1.2 Applications

2.2 Weighted Maximum Clique

2.2.1 Surveys / Theory

2.2.2 Stochastic Local Search algorithms

2.2.3 Applications

2.2.4 Exact methods

2.2.5 Continuous formulations

# Bibliography

Download the complete bibliography in BibTeX format, or the single BibTeX entries below. A paper can belong to different categories. In each category papers are sorted from the most recent to the oldest. This commented bibliography (252 references for the time being) does not aim at being complete and is currently under construction.

Applications are labeled with the research field name or the research topic.

References to algorithms for the Maximum Independent set (or Maximum Stable Set) are also reported. The Maximum Independent Set is the same problem as the Maximum Clique on the complementary graph, and algorithms can be easily applied to both problems by switching a logical condition in the code. The Maximum Clique literature has been recently richer than the Maximum Independent Set literature and most of the algorithms have been proposed as Maximum Clique solvers.

## 1 Maximum Clique

### 1.1 Surveys / Theory

```
@article{WuH:2015,
author = {Qinghua Wu and Jin{-}Kao Hao},
title = {A review on algorithms for maximum clique problems},
journal = {European Journal of Operational Research},
volume = {242},
number = {3},
pages = {693--709},
year = {2015},
doi = {10.1016/j.ejor.2014.09.064},
}
```

```
@article{AkbariAJ:2012,
author = {Akbari, S. and Aryapoor, M. and Jamaali, M.},
title = {Chromatic number and clique number of subgraphs of regular graph of matrix algebras},
journal = {Linear Algebra and Its Applications},
volume = {436},
number = {7},
pages = {2419-2424},
year = {2012},
doi = {10.1016/j.laa.2011.09.020},
}
```

```
@article{BiyikogluL:2012,
author = {B{\i}y{\i}ko{\ug}lu, T{\"u}rker and Leydold, Josef},
title = {Graphs of given order and size and minimum algebraic connectivity},
journal = {Linear Algebra and Its Applications},
volume = {436},
number = {7},
pages = {2067-2077},
year = {2012},
doi = {10.1016/j.laa.2011.09.026},
}
```

```
@article{OrtizV:2012,
author = {Ortiz, Carmen and Villanueva, M{\'o}nica},
title = {Maximal independent sets in caterpillar graphs},
journal = {Discrete Applied Mathematics},
volume = {160},
number = {3},
pages = {259-266},
year = {2012},
doi = {10.1016/j.dam.2011.10.024},
}
```

```
@article{Szabo:2011,
author = {S{\'a}ndor Szab{\'o}},
title = {Parallel algorithms for finding cliques in a graph},
journal = {Journal of Physics: Conference Series},
volume = {268},
number = {1},
pages = {012030},
year = {2011},
doi = {10.1088/1742-6596/268/1/012030},
}
```

```
@incollection{TomitaAM:2011,
author = {Etsuji Tomita, Tatsuya Akutsu and Tsutomu Matsunaga},
title = {Efficient Algorithms for Finding Maximum and Maximal Cliques: Effective Tools for Bioinformatics},
booktitle = {Biomedical Engineering, Trends in Electronics, Communications and Software},
pages = {625-640},
editor = {Anthony N. Laskovski},
publisher = {InTech},
year = {2011},
url = {http://www.intechopen.com/books/biomedical-engineering-trends-in-electronics-communications-and-software/efficient-algorithms-for-finding-maximum-and-maximal-cliques-effective-tools-for-bioinformatics},
}
```

```
@incollection{EppsteinLS:2010,
author = {Eppstein, David and L{\"o}ffler, Marteen and Strash, Darren},
title = {Listing All Maximal Cliques in Sparse Graphs in Near-Optimal Time},
volume = {6506},
booktitle = {Algorithms and Computation},
series = {Lecture Notes in Computer Science},
pages = {403--414},
editor = {Cheong, Otfried and Chwa, Kyung-Yong and Park, Kunsoo},
publisher = {Springer Berlin / Heidelberg},
year = {2010},
doi = {10.1007/978-3-642-17517-6_36},
}
```

**Note:**Survey on relevant problems in bioinformatics and biochemistry that can be formalised as graph problems and solved with clique-detection models.

Clique-detection models include prescribing (a) a maximal clique, (b) a maximum clique, (c) a maximum weighted clique, or (d) all maximal cliques in a graph. The particular types of biochemistry and genomics problems that can be represented by a clique-detection model include integration of genome mapping data, nonoverlapping local alignments, matching and comparing molecular structures, and protein docking.

```
@article{ButenkoW:2006,
author = {Butenko, Sergiy and Wilhelm, Wilbert E.},
title = {Clique-detection models in computational biochemistry and genomics},
journal = {European Journal of Operational Research},
volume = {173},
number = {1},
pages = {1--17},
year = {2006},
doi = {10.1016/j.ejor.2005.05.026},
}
```

```
@inproceedings{Storch:2006,
author = {Storch, Tobias},
title = {How randomized search heuristics find maximum cliques in planar graphs},
volume = {1},
booktitle = {GECCO 2006 - Genetic and Evolutionary Computation Conference},
pages = {567--574},
publisher = {ACM},
year = {2006},
address = {New York, NY, USA},
}
```

**Note:**Theoretical work on worst case complexity of generating all maximal cliques with a depth-first search algorithm. The exact algorithm has a pruning methods that are similar to the Bron-Kerbosh algorithm (BronK:1973), and a different, more compact, representation of the enumerated maximal cliques. The algorithm has \(O(3^{n/3})\) worst-case time complexity for enumerating all maximal cliques (which is optimal).

```
@article{TomitaTT:2006,
author = {Tomita, Etsuji and Tanaka, Akira and Takahashi, Haruhisa},
title = {The worst-case time complexity for generating all maximal cliques and computational experiments},
journal = {Theoretical Computer Science},
volume = {363},
number = {1},
pages = {28--42},
publisher = {Elsevier},
year = {2006},
doi = {10.1016/j.tcs.2006.06.015},
}
```

**Note:**Most recent complete survey on the maximum clique formulations, generalisations, algorithms and applications.

```
@article{BomzeBPP:1999,
author = {Bomze, Immanuel M. and Budinich, Marco and Pardalos, Panos M. and Pelillo, Marcello},
title = {The maximum clique problem},
journal = {Handbook of Combinatorial Optimization (Supplement Volume A)},
volume = {4},
pages = {1--74},
editor = {Du, D.-Z. and Pardalos, Panos M.},
publisher = {Kluwer Academic Publishers},
city = {Boston, MA},
year = {1999},
url = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.56.6221},
}
```

The first part of the paper presents a collection of new proof systems based on a new errorcorrecting code called the long code. We provide a proof system which has amortized free bit complexity of \(2 + \epsilon\), implying that approximating Max Clique within \(N^{\frac{1}{3}-\epsilon}\), and approximating the Chromatic Number within \(N^{\frac{1}{5}-\epsilon}\), are hard assuming NP \(\neq\) coRP, for any \(\epsilon > 0\). We also derive the first explicit and reasonable constant hardness factors for Min Vertex Cover, Max2SAT, and Max Cut, and improve the hardness factor for Max3SAT. We note that our non-approximability factors for MaxSNP problems are appreciably close to the values known to be achievable by polynomial time algorithms. Finally we note a general approach to the derivation of strong non-approximability results under which the problem reduces to the construction of certain ‘‘gadgets.”

The increasing strength of non-approximability results obtained via the PCP connection motivates us to ask how far this can go, and whether PCPs are inherent in any way. The second part of the paper addresses this. The main result is a ‘‘reversal” of the FGLSS connection: where the latter had shown how to translate proof systems for NP into NP-hardness of approximation results for Max Clique, we show how any NP-hardness of approximation result for Max Clique yields a proof system for NP. Roughly our result says that for any constant \(f\) if Max Clique is NP-hard to approximate within N^{1/(1+f)} then \(NP \subseteq \overline{\text{FPCP}}\left[log, f \right]\), the latter being the class of languages possessing proofs of logarithmic randomness and amortized free bit complexity \(f\). This suggests that PCPs are inherent to obtaining non-approximability results. Furthermore the tight relation suggests that reducing the amortized free bit complexity is necessary for improving the non-approximability results for Max Clique.

The third part of our paper initiates a systematic investigation of the properties of PCP and FPCP as a function of the various parameters: randomness, query complexity, free bit complexity, amortized free bit complexity, proof size, etc. We are particularly interested in ‘‘triviality” results, which indicate which classes are not powerful enough to capture NP. We also distill the role of randomized reductions in this are

```
@article{BellareGS:1998,
author = {Bellare, Mihir and Goldreich, Oded and Sudan, Madhu},
title = {Free bits, PCPs, and nonapproximability - towards tight results},
journal = {SIAM Journal on Computing},
volume = {27},
number = {3},
pages = {804--915},
year = {1998},
doi = {10.1137/S0097539796302531},
}
```

```
@inproceedings{Hastad:1996,
author = {H{\aa}stad, Johan},
title = {Clique is hard to approximate within $n^{1-\epsilon}$},
booktitle = {Proceedings of 37th Ann. IEEE Symp. on Foundations of Computer Science},
pages = {627--636},
publisher = {IEEE Computer Society},
year = {1996},
doi = {10.1109/SFCS.1996.548522},
}
```

```
@article{PardalosX:1994,
author = {Pardalos, Panos M. and Xue, Jue},
title = {The maximum clique problem},
journal = {Journal of Global Optimization},
volume = {4},
number = {3},
pages = {301--328},
year = {1994},
doi = {10.1007/BF01098364},
}
```

**Note:**Classic book on NP-completeness.

```
@book{GareyJ:1979,
author = {Garey, Michael R. and Johnson, David S.},
title = {Computers and Intractability: A Guide to the Theory of NP-completeness},
publisher = {Freeman&Co., San Francisco},
year = {1979},
}
```

```
@techreport{Matula:1976,
author = {Matula, David W.},
title = {The Largest Clique Size in a Random Graph},
number = {CS 7608},
institution = {Department of Computer Science, Southern Methodist University},
year = {1976},
url = {http://lyle.smu.edu/~matula/Tech-Report76.pdf},
}
```

**Note:**Exact algorithm very popular in computational chemistry and other application domains. Variants with special pivoting rules are among the best performing exact algorithms for the problem. Being complete, it can be applied only to very small instances or to larger instances with small degeneracy number (see EppsteinS:2011).

```
@article{BronK:1973,
author = {Bron, Coen and Kerbosch, Joep},
title = {Algorithm 457: finding all cliques of an undirected graph},
journal = {Communications of ACM},
volume = {16},
number = {9},
pages = {575--577},
publisher = {ACM},
year = {1973},
month = sep,
address = {New York, NY, USA},
doi = {10.1145/362342.362367},
}
```

**Note:**Historical paper in which Karp presents 21 NP-complete decision problems and reductions among them.

```
@incollection{Karp:1972,
author = {Karp, Richard M.},
title = {Reducibility Among Combinatorial Problems},
booktitle = {Complexity of Computer Computations},
pages = {85--103},
editor = {Miller, R. E. and Thatcher, J. W.},
publisher = {Plenum Press},
year = {1972},
url = {http://www.cs.berkeley.edu/~luca/cs172/karp.pdf},
}
```

#### 1.1.1 Bounds

```
@article{DukanovicR:2007,
author = {Dukanovic, Igor and Rendl, Franz},
title = {Semidefinite programming relaxations for graph coloring and maximal clique problems},
journal = {Mathematical Programming},
volume = {109},
pages = {345-365},
publisher = {Springer Berlin / Heidelberg},
year = {2007},
doi = {10.1007/s10107-006-0026-z},
}
```

```
@article{Pena:2008,
author = {Javier Pe{\~n}a and Juan Vera and Luis F. Zuluaga},
title = {Computing the Stability Number of a Graph Via Linear and Semidefinite Programming},
journal = {SIAM Journal on Optimization},
volume = {18},
number = {1},
pages = {87--105},
publisher = {SIAM},
year = {2007},
doi = {10.1137/05064401X},
}
```

```
@article{GvozdenovicL:2005,
author = {Gvozdenovi{\'c}, Neboj{\vs}a and Laurent, Monique},
title = {Semidefinite bounds for the stability number of a graph via sums of squares of polynomials},
journal = {Integer Programming and Combinatorial Optimization},
pages = {285--294},
publisher = {Springer},
year = {2005},
doi = {10.1007/11496915_11},
}
```

```
@article{deKlerkP:2002,
author = {Etienne de Klerk and Dmitrii V. Pasechnik},
title = {Approximation of the Stability Number of a Graph via Copositive Programming},
journal = {SIAM Journal on Optimization},
volume = {12},
number = {4},
pages = {875--892},
publisher = {SIAM},
year = {2002},
doi = {10.1137/S1052623401383248},
}
```

```
@inproceedings{Khot:2001,
author = {Khot, Subhash},
title = {Improved inapproximability results for maxclique, chromatic number and approximate graph coloring},
booktitle = {Foundations of Computer Science, 2001. Proceedings. 42nd IEEE Symposium on},
pages = {600--609},
year = {2001},
doi = {10.1109/SFCS.2001.959936},
}
```

```
@article{Schrijver:1979,
author = {Schrijver, Alexander},
title = {A comparison of the Delsarte and Lov{\'a}sz bounds},
journal = {Information Theory, IEEE Transactions on},
volume = {25},
number = {4},
pages = {425--429},
publisher = {IEEE},
year = {1979},
doi = {10.1109/TIT.1979.1056072},
}
```

### 1.2 Stochastic Local Search algorithms

```
@article{JinH:2015,
author = {Yan Jin and Jin{-}Kao Hao},
title = {General swap-based multiple neighborhood tabu search for the maximum independent set problem},
journal = {Engineering Applications of Artificial Intelligence},
volume = {37},
pages = {20--33},
year = {2015},
doi = {10.1016/j.engappai.2014.08.007},
}
```

**Note:**In depth analysis of the dynamics of reactive tabu search focussing on the maximum clique problem (BattitiM:2010), and quadratic assignment problem. It also presents an analysis of the DIMACS instances and the first optimal solution with 1100 nodes for MANN_a81.

```
@article{MasciaPBS:2014,
author = {Franco Mascia and Paola Pellegrini and Mauro Birattari and Thomas St{\"u}tzle},
title = {An Analysis of Parameter Adaptation in Reactive Tabu Search},
journal = {International Transactions in Operational Research},
volume = {21},
number = {1},
pages = {127--152},
year = {2014},
month = jan,
doi = {10.1111/itor.12043},
}
```

```
@article{BenlicH:2013,
author = {Una Benlic and Jin{-}Kao Hao},
title = {Breakout Local Search for maximum clique problems},
journal = {Computers and Operations Research},
volume = {40},
number = {1},
pages = {192--206},
year = {2013},
doi = {10.1016/j.cor.2012.06.002},
}
```

```
@article{WuH:2013,
author = {Qinghua Wu and Jin{-}Kao Hao},
title = {An adaptive multistart tabu search approach to solve the maximum clique problem},
journal = {Journal of Combinatorial Optimization},
volume = {26},
number = {1},
pages = {86--108},
year = {2013},
doi = {10.1007/s10878-011-9437-8},
}
```

```
@article{ZhouYSYW:2012,
author = {Zhou, Ben-Da and Yao, Hong-Liang and Shi, Ming-Hua and Yue, Qin and Wang, Hao},
title = {An new immune genetic algorithm based on uniform design sampling},
journal = {Knowledge and Information Systems},
pages = {1-15},
year = {2012},
doi = {10.1007/s10115-011-0476-3},
}
```

```
@article{JavidiM:2011,
author = {Javidi, Mohammad M. and Mehrabi, Saeed},
title = {On evolutionary algorithms for large cliques in random graphs},
journal = {International Journal of Applied Mathematics and Statistics},
volume = {22},
number = {SUPPL. 11},
pages = {53-60},
year = {2011},
url = {http://ceser.in/ceserp/index.php/ijamas/article/view/259/137},
}
```

**Note:**Parallel meta-heuristic with state-of-the-art results on DIMACS and BHOSLIB instances. Components are a greedy reactive tabu search component (BattitiM:2010), a penalty-based dynamic local search (PullanH:2006), and a focussed meta-heuristic that focusses on cliques having nodes with a specific degree.

```
@article{PullanMB:2011,
author = {Pullan, Wayne and Mascia, Franco and Brunato, Mauro},
title = {Cooperating local search for the maximum clique problem},
journal = {Journal of Heuristics},
volume = {17},
number = {2},
pages = {181--199},
publisher = {Springer},
year = {2011},
month = apr,
doi = {10.1007/s10732-010-9131-5},
}
```

**Note:**Latest implementation of the original reactive tabu search for the maximum clique problem (BattitiP:2001). It is a parameter free algorithm which is state-of-the-art results on DIMACS instances.

```
@article{BattitiM:2010,
author = {Battiti, Roberto and Mascia, Franco},
title = {Reactive and dynamic local search for max-clique: Engineering effective building blocks},
journal = {Computers and Operations Research},
volume = {37},
number = {3},
pages = {534--542},
publisher = {Elsevier Science Ltd.},
year = {2010},
month = mar,
address = {Oxford, UK, UK},
doi = {10.1016/j.cor.2009.02.013},
}
```

```
@inproceedings{DangM:2010,
author = {Dang, Duc-Cuong and Moukrim, Aziz},
title = {Subgraph extraction and memetic algorithm for the maximum clique problem},
booktitle = {ICEC 2010 - Proceedings of the International Conference on Evolutionary Computation},
pages = {77-84},
publisher = {INSTICC},
year = {2010},
url = {http://hal.archives-ouvertes.fr/hal-00575910/en/},
}
```

```
@inproceedings{RajawatHM:2010,
author = {Rajawat, Shalini and Hemrajani, Naveen and Menghani, Ekta},
title = {Solving maximal clique problem through genetic algorithm},
volume = {1324},
booktitle = {AIP Conference Proceedings},
pages = {235-238},
editor = {Patel, R. B. and Singh, B. P.},
publisher = {American Institute of Physics},
year = {2010},
doi = {10.1063/1.3526202},
}
```

```
@inproceedings{RenW:2010,
author = {Ren, Shijun and Wang, Yadong},
title = {An improved ACO metaheuristic for solving the MCP},
volume = {1},
booktitle = {Proceedings - 2010 6th International Conference on Natural Computation, ICNC 2010},
pages = {106-111},
year = {2010},
doi = {10.1109/ICNC.2010.5583351},
}
```

```
@inproceedings{BuiNR:2009,
author = {Bui, Thang N. and Nguyen, ThanhVu and Rizzo Jr., Joseph R.},
title = {Parallel shared memory strategies for ant-based optimization algorithms},
booktitle = {Proceedings of the 11th Annual Genetic and Evolutionary Computation Conference, GECCO-2009},
pages = {1--8},
publisher = {ACM},
year = {2009},
address = {New York, NY, USA},
doi = {10.1145/1569901.1569903},
}
```

**Note:**Parameter free meta-heuristic. First optimal solution of size 80 for the DIMACS instance C2000.9.

```
@article{GrossoLP:2007,
author = {Grosso, Andrea and Locatelli, Marco and Pullan, Wayne},
title = {Simple ingredients leading to very efficient heuristics for the maximum clique problem},
journal = {Journal of Heuristics},
volume = {14},
number = {6},
pages = {587--612},
year = {2007},
month = oct,
doi = {10.1007/s10732-007-9055-x},
}
```

```
@article{YouniesW:2007,
author = {Younies, Hassan and Wesolowsky, George O.},
title = {Planar maximal covering location problem under block norm distance measure},
journal = {Journal of the Operational Research Society},
volume = {58},
number = {6},
pages = {740-750},
year = {2007},
doi = {10.1057/palgrave.jors.2602172},
}
```

```
@article{ZhangST:2007,
author = {Zhang, Qingfu and Sun, Jianyong and Tsang, Edward},
title = {Combinations of estimation of distribution algorithms and other techniques},
journal = {International Journal of Automation and Computing},
volume = {4},
number = {3},
pages = {273-280},
publisher = {Institute of Automation, Chinese Academy of Sciences, co-published with Springer-Verlag GmbH},
year = {2007},
doi = {10.1007/s11633-007-0273-3},
}
```

**Note:**Portfolio of meta-heuristics applied sequentially, with adaptive setting of the penalty delay parameter of (PullanH:2006).

```
@article{Pullan:2006,
author = {Pullan, Wayne},
title = {Phased local search for the maximum clique problem},
journal = {Journal of Combinatorial Optimization},
volume = {12},
number = {3},
pages = {303--323},
publisher = {Springer},
year = {2006},
doi = {10.1007/s10878-006-9635-y},
}
```

**Note:**Penalty based non-greedy meta-heuristic with state-of-the-art performance on the DIMACS benchmark set.

```
@article{PullanH:2006,
author = {Pullan, Wayne and Hoos, Holger H.},
title = {Dynamic local search for the maximum clique problem},
journal = {Journal of Artificial Intelligence Research},
volume = {25},
number = {1},
pages = {159--185},
publisher = {AI Access Foundation},
year = {2006},
doi = {10.1613/jair.1815},
}
```

```
@article{SinghG:2006,
author = {Singh, Alok and Gupta, Ashok Kumar},
title = {A hybrid heuristic for the maximum clique problem},
journal = {Journal of Heuristics},
volume = {12},
number = {1-2},
pages = {5-22},
year = {2006},
doi = {10.1007/s10732-006-3750-x},
}
```

**Note:**Study on the impact of pheromone trails on the solution process of a memetic algorithm for the maximum clique problem.

We illustrate the behavior of the two ACO instantiations on a representative benchmark instance and we study the impact of pheromone on the solution process. We consider two measures—the re-sampling and the dispersion ratio—for providing an insight into the performance at run time. We also study the benefit of integrating a local search procedure within the proposed ACO algorithm, and we show that this improves the solution process. Finally, we compare ACO performance with that of three other representative heuristic approaches, showing that the former obtains competitive results.

```
@article{SolnonF:2006,
author = {Solnon, Christine and Fenet, Serge},
title = {A study of aco capabilities for solving the maximum clique problem},
journal = {Journal of Heuristics},
volume = {12},
number = {3},
pages = {155--180},
publisher = {Springer},
year = {2006},
doi = {10.1007/s10732-006-4295-8},
}
```

```
@inproceedings{Storch:2006,
author = {Storch, Tobias},
title = {How randomized search heuristics find maximum cliques in planar graphs},
volume = {1},
booktitle = {GECCO 2006 - Genetic and Evolutionary Computation Conference},
pages = {567--574},
publisher = {ACM},
year = {2006},
address = {New York, NY, USA},
}
```

```
@article{KatayamaHN:2005,
author = {Katayama, Kengo and Hamamoto, Akihiro and Narihisa, Hiroyuki},
title = {An effective local search for the maximum clique problem},
journal = {Information Processing Letters},
volume = {95},
number = {5},
pages = {503--511},
publisher = {Elsevier},
year = {2005},
doi = {10.1016/j.ipl.2005.05.010},
}
```

```
@inproceedings{LiuYJFD:2005,
author = {Liu, Xiaoming and Yin, Jianwei and Jwo, Jung-Sing and Feng, Zhilin and Dong, Jinxiang},
title = {A DNA-Based Genetic Algorithm Implementation for Graph Coloring Problem},
volume = {3645},
booktitle = {Advances in Intelligent Computing},
series = {Lecture Notes in Computer Science},
pages = {99--108},
editor = {Huang, De-Shuang and Zhang, Xiao-Ping and Huang, Guang-Bin},
publisher = {Springer Berlin / Heidelberg},
year = {2005},
doi = {10.1007/11538356_11},
}
```

```
@inproceedings{SunLG:2005,
author = {Sun, C. Y. and Li, W. J. and Gao, X. Z.},
title = {A novel evolutionary algorithm for MCP using MEC},
volume = {2005},
booktitle = {SMCia/05 - Proceedings of the 2005 IEEE Mid-Summer Workshop on Soft Computing in Industrial Applications},
pages = {99--104},
year = {2005},
doi = {10.1109/SMCIA.2005.1466955},
}
```

```
@article{ZhangST:2005,
author = {Zhang, Qingfu and Sun, Jianyong and Tsang, Edward},
title = {An evolutionary algorithm with guided mutation for the maximum clique problem},
journal = {Evolutionary Computation, IEEE Transactions on},
volume = {9},
number = {2},
pages = {192--200},
publisher = {IEEE},
year = {2005},
doi = {10.1109/TEVC.2004.840835},
}
```

```
@article{GrossoLD:2004,
author = {Grosso, Andrea and Locatelli, Marco and Della~Croce, Federico},
title = {Combining Swaps and Node Weights in an Adaptive Greedy Approach for the Maximum Clique Problem},
journal = {Journal of Heuristics},
volume = {10},
number = {2},
pages = {135-152},
publisher = {Springer Netherlands},
year = {2004},
doi = {10.1023/B:HEUR.0000026264.51747.7f},
}
```

```
@article{HansenMU:2004,
author = {Hansen, Pierre and Mladenovi{\'c}, Nenad and Uro{\vs}evi{\'c}, Dragan},
title = {Variable neighborhood search for the maximum clique},
journal = {Discrete Applied Mathematics},
volume = {145},
number = {1},
pages = {117--125},
publisher = {Elsevier},
year = {2004},
doi = {10.1016/j.dam.2003.09.012},
}
```

```
@inproceedings{KatayamaHN:2004,
author = {Katayama, Kengo and Hamamoto, Akihiro and Narihisa, Hiroyuki},
title = {Solving the maximum clique problem by k-opt local search},
volume = {2},
booktitle = {Proceedings of the ACM Symposium on Applied Computing},
pages = {1021-1025},
publisher = {ACM},
year = {2004},
address = {New York, NY, USA},
doi = {10.1145/967900.968107},
}
```

```
@inproceedings{YoussefE:2004,
author = {Youssef, Sherin M. and Elliman, Dave G.},
title = {Reactive Prohibition-based Ant Colony Optimization (RPACO): A new parallel architecture for constrained clique sub-graphs},
booktitle = {Proceedings - International Conference on Tools with Artificial Intelligence, ICTAI},
pages = {63-70},
publisher = {IEEE},
year = {2004},
doi = {10.1109/ICTAI.2004.104},
}
```

```
@inproceedings{Regin:2003,
author = {Regin, Jean-Charles},
title = {Solving the maximum clique problem with constraint programming},
booktitle = {Fifth International Workshop on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CP-AI-OR'03), May 8-10, 2003, Montreal, Canada.},
pages = {166--179},
year = {2003},
url = {http://www.crt.umontreal.ca/cpaior/article-regin.pdf},
}
```

```
@incollection{Marchiori:2002,
author = {Marchiori, Elena},
title = {Genetic, Iterated and Multistart Local Search for the Maximum Clique Problem},
volume = {2279},
booktitle = {Applications of Evolutionary Computing},
series = {Lecture Notes in Computer Science},
pages = {112-121},
editor = {Cagnoni, Stefano and Gottlieb, Jens and Hart, Emma and Middendorf, Martin and Raidl, G{\"u}nther},
publisher = {Springer Berlin / Heidelberg},
year = {2002},
doi = {10.1007/3-540-46004-7_12},
}
```

**Note:**Original reactive tabu search for the maximum clique problem. BattitiM:2010, is the updated version with small implementation and algorithmic improvements, which is, on large instances, one order of magnitude faster.

```
@article{BattitiP:2001,
author = {Battiti, Roberto and Protasi, Marco},
title = {Reactive Local Search for the Maximum Clique Problem},
journal = {Algorithmica},
volume = {29},
number = {4},
pages = {610--637},
year = {2001},
month = apr,
doi = {10.1007/s004530010074},
}
```

```
@article{BomzeS:1999,
author = {Bomze, Immanuel M. and Stix, Volker},
title = {Genetic engineering via negative fitness:Evolutionary dynamics for global optimization},
journal = {Annals of Operations Research},
volume = {89},
pages = {297-318},
publisher = {Springer Netherlands},
year = {1999},
doi = {10.1023/A:1018935925761},
}
```

```
@article{SorianoG:1996,
author = {Soriano, Patrick and Gendreau, Michel},
title = {Diversification strategies in tabu search algorithms for the maximum clique problem},
journal = {Annals of Operations Research},
volume = {63},
pages = {189--207},
publisher = {Springer Netherlands},
year = {1996},
doi = {10.1007/BF02125454},
}
```

```
@inproceedings{BuiE:1995,
author = {Bui, Thang Nguyen and Eppley, Paul H.},
title = {A hybrid genetic algorithm for the maximum clique problem},
booktitle = {Proceedings of the 6th international conference on genetic algorithms},
pages = {478--484},
year = {1995},
address = {San Francisco, CA, USA},
}
```

```
@inproceedings{BackK:1994,
author = {B{\"a}ck, Thomas and Khuri, Sami},
title = {An evolutionary heuristic for the maximum independent set problem},
booktitle = {Evolutionary Computation, 1994. IEEE World Congress on Computational Intelligence., Proceedings of the First IEEE Conference on},
pages = {531--535},
year = {1994},
doi = {10.1109/ICEC.1994.350004},
}
```

As we scale up the problem size and test on ‘‘hard” benchmark instances, we notice a degraded performance in the algorithm caused by premature convergence to local minima. To alleviate this problem, a sequence of modi cations are implemented ranging from changes in input representation to systematic local search. The most recent version, called union GA, incorporates the features of union cross-over, greedy replacement, and diversity enhancement. It shows a marked speed-up in the number of iterations required to find a given solution, as well as some improvement in the clique size found.

We discuss issues related to the SIMD implementation of the genetic algorithms on a Thinking Machines CM-5, which was necessitated by the intrinsically high time complexity (O(n3)) of the serial algorithm for computing one iteration.

Our preliminary conclusions are: (1) a genetic algorithm needs to be heavily customized to work ‘‘well” for the clique problem; (2) a GA is computationally very expensive, and its use is only recommended if it is known to a nd larger cliques than other algorithms; (3) although our customization e ort is bringing forth continued improvements, there is no clear evidence, at this time, that a GA will have better success in circumventing local minima.

```
@techreport{CarterP:1993,
author = {Carter, Robert and Park, Kihong},
title = {How good are genetic algorithms at finding large cliques: an experimental study},
institution = {Boston University Computer Science Department},
year = {1993},
url = {http://dcommon.bu.edu/xmlui/bitstream/handle/2144/1469/1993-015-ga-clique.pdf?sequence=1},
}
```

```
@article{GendreauSS:1993,
author = {Gendreau, Michel and Soriano, Patrick and Salvail, Louis},
title = {Solving the maximum clique problem using a tabu search approach},
journal = {Annals of Operations Research},
volume = {41},
number = {4},
pages = {385--403},
publisher = {Springer},
year = {1993},
doi = {10.1007/BF02023002},
}
```

As for graph coloring, this method seems to be a very efficient heuristic procedure.

```
@article{FridenHW:1989,
author = {Friden, C. and Hertz, A. and Werra, D.},
title = {Stabulus: a technique for finding stable sets in large graphs with tabu search},
journal = {Computing},
volume = {42},
number = {1},
pages = {35--44},
publisher = {Springer},
year = {1989},
doi = {10.1007/BF02243141},
}
```

### 1.3 Applications

```
@article{CurtoDI:2012,
author = {Curto, Carina and Degeratu, Anda and Itskov, Vladimir},
title = {Flexible memory networks.},
journal = {Bulletin of Mathematical Biology},
volume = {74},
number = {3},
pages = {590-614},
year = {2012},
month = mar,
doi = {10.1007/s11538-011-9678-9},
}
```

```
@article{KimLRK:2012,
author = {Kim, Seung Kwan and Lee, Jee Hyung and Ryu, Keun Ho and Kim, Ungmo},
title = {A framework of spatial co-location pattern mining for ubiquitous GIS},
journal = {Multimedia Tools and Applications},
pages = {1-20},
year = {2012},
doi = {10.1007/s11042-012-1007-2},
}
```

```
@article{MaG:2012,
author = {Ma, Xiaoke and Gao, Lin},
title = {Predicting protein complexes in protein interaction networks using a core-attachment algorithm based on graph communicability},
journal = {Information Sciences},
volume = {189},
pages = {233-254},
year = {2012},
doi = {10.1016/j.ins.2011.11.033},
}
```

Recent studies suggest that polymorphisms in genes encoding enzymes involved in drug detoxification and metabolism may influence disease outcome in pediatric acute lymphoblastic leukemia (ALL). We sought to extend current knowledge by using standard and novel statistical methodology to examine polymorphic variants of genes and relapse risk, toxicity, and drug dose delivery in standard risk ALL.

Procedure

We genotyped and abstracted chemotherapy drug dose data from treatment roadmaps on 557 patients on the Children’s Cancer Group ALL study, CCG-1891. Fourteen common polymorphisms in genes involved in folate metabolism and/or phase I and II drug detoxification were evaluated individually and clique-finding methodology was employed for detection of significant gene-gene interactions.

Results

After controlling for known risk factors, polymorphisms in four genes: GSTP1*B (HR = 1.94, P = 0.047), MTHFR (HR = 1.61, P = 0.034), MTRR (HR = 1.95, P = 0.01), and TS (3R/4R, HR = 3.69, P = 0.007) were found to significantly increase relapse risk. One gene-gene pair, MTRR A/G and GSTM1 null genotype, significantly increased the risk of relapse after correction for multiple comparisons (P = 0.012). Multiple polymorphisms were associated with various toxicities and there was no significant difference in dose of chemotherapy delivered by genotypes.

Conclusions

These data suggest that various polymorphisms play a role in relapse risk and toxicity during childhood ALL therapy and that genotype does not play a role in adjustment of drug dose administered. Additionally, gene-gene interactions may increase the risk of relapse in childhood ALL and the clique method may have utility in further exploring these interactions. childhood ALL therapy. USA. sepe@email.chop.edu

```
@article{SepeMCKZLDLRA:2012,
author = {Sepe, Dana M. and McWilliams, Thomas and Chen, Jinbo and Kershenbaum, Aaron and Zhao, Huaqing and La, Mei and Devidas, Meenakshi and Lange, Beverly and Rebbeck, Timothy R. and Aplenc, Richard},
title = {Germline genetic variation and treatment response on CCG-1891.},
journal = {Pediatric Blood & Cancer},
volume = {58},
number = {5},
pages = {695-700},
year = {2012},
month = may,
doi = {10.1002/pbc.23192},
}
```

```
@article{SwamidassCBBC:2012,
author = {Swamidass, S. Joshua and Calhoun, Bradley T. and Bittker, Joshua A. and Bodycombe, Nicole E. and Clemons, Paul A.},
title = {Utility-aware screening with clique-oriented prioritization.},
journal = {Journal of Chemical Information and Modeling},
volume = {52},
number = {1},
pages = {29-37},
year = {2012},
month = jan,
doi = {10.1021/ci2003285},
}
```

This paper seeks to initiate a rigorous approach to the problem of finding overlapping communities, where ‘‘rigorous” means that we clearly state the following: (a) the object sought by our algorithm (b) the assumptions about the underlying network (c) the (worst-case) running time.

Our assumptions about the network lie between worst-case and average-case. An average case analysis would require a precise probabilistic model of the network, on which there is currently no consensus. However, some plausible assumptions about network parameters can be gleaned from a long body of work in the sociology community spanning five decades focusing on the study of individual communities and ego-centric networks. Thus our assumptions are somewhat ‘‘local” in nature. Nevertheless they suffice to permit a rigorous analysis of running time of algorithms that recover global structure.

Our algorithms use random sampling similar to that in property testing and algorithms for dense graphs. However, our networks are not necessarily dense graphs, not even in local neighborhoods.

Our algorithms explore a local-global relationship between ego-centric and socio-centric networks that we hope will provide a fruitful framework for future work both in computer science and sociology.

```
@article{AroraGSS:2011,
author = {Sanjeev Arora and Rong Ge and Sushant Sachdeva and Grant Schoenebeck},
title = {Finding Overlapping Communities in Social Networks: Toward a Rigorous Approach},
journal = {CoRR},
volume = {abs/1112.1831},
year = {2011},
url = {http://arxiv.org/abs/1112.1831},
}
```

Mapping protein primary sequences to their three dimensional folds referred to as the ’second genetic code’ remains an unsolved scientific problem. A crucial part of the problem concerns the geometrical specificity in side chain association leading to densely packed protein cores, a hallmark of correctly folded native structures. Thus, any model of packing within proteins should constitute an indispensable component of protein folding and design.

Results

In this study an attempt has been made to find, characterize and classify recurring patterns in the packing of side chain atoms within a protein which sustains its native fold. The interaction of side chain atoms within the protein core has been represented as a contact network based on the surface complementarity and overlap between associating side chain surfaces. Some network topologies definitely appear to be preferred and they have been termed ’packing motifs’, analogous to super secondary structures in proteins. Study of the distribution of these motifs reveals the ubiquitous presence of typical smaller graphs, which appear to get linked or coalesce to give larger graphs, reminiscent of the nucleation-condensation model in protein folding. One such frequently occurring motif, also envisaged as the unit of clustering, the three residue clique was invariably found in regions of dense packing. Finally, topological measures based on surface contact networks appeared to be effective in discriminating sequences native to a specific fold amongst a set of decoys.

Conclusions

Out of innumerable topological possibilities, only a finite number of specific packing motifs are actually realized in proteins. This small number of motifs could serve as a basis set in the construction of larger networks. Of these, the triplet clique exhibits distinct preference both in terms of composition and geometry. Physics, Bidhannagar, Kolkata, India.

```
@article{BasuBB:2011,
author = {Basu, Sankar and Bhattacharyya, Dhananjay and Banerjee, Rahul},
title = {Mapping the distribution of packing topologies within protein interiors shows predominant preference for specific packing motifs.},
journal = {BMC Bioinformatics},
volume = {12},
pages = {195},
year = {2011},
doi = {10.1186/1471-2105-12-195},
}
```

```
@article{ChenYLLLHCLHCKH:2011,
author = {Chen, Ming-Huang and Yang, Wu-Lung R. and Lin, Kuan-Ting and Liu, Chia-Hung and Liu, Yu-Wen and Huang, Kai-Wen and Chang, Peter Mu-Hsin and Lai, Jin-Mei and Hsu, Chun-Nan and Chao, Kun-Mao and Kao, Cheng-Yan and Huang, Chi-Ying F.},
title = {Gene expression-based chemical genomics identifies potential therapeutic drugs in hepatocellular carcinoma.},
journal = {Plos One},
volume = {6},
number = {11},
pages = {e27186},
year = {2011},
doi = {10.1371/journal.pone.0027186},
}
```

Measuring similarities between tree structured data is important for analysis of RNA secondary structures, phylogenetic trees, glycan structures, and vascular trees. The edit distance is one of the most widely used measures for comparison of tree structured data. However, it is known that computation of the edit distance for rooted unordered trees is NP-hard. Furthermore, there is almost no available software tool that can compute the exact edit distance for unordered trees.

Results

In this paper, we present a practical method for computing the edit distance between rooted unordered trees. In this method, the edit distance problem for unordered trees is transformed into the maximum clique problem and then efficient solvers for the maximum clique problem are applied. We applied the proposed method to similar structure search for glycan structures. The result suggests that our proposed method can efficiently compute the edit distance for moderate size unordered trees. It also suggests that the proposed method has the accuracy comparative to those by the edit distance for ordered trees and by an existing method for glycan search.

Conclusions

The proposed method is simple but useful for computation of the edit distance between unordered trees. The object code is available upon request. Japan. dfukagaw@mail.doshisha.ac.jp

```
@article{FukagawaTTTA:2011,
author = {Fukagawa, Daiji and Tamura, Takeyuki and Takasu, Atsuhiro and Tomita, Etsuji and Akutsu, Tatsuya},
title = {A clique-based method for the edit distance between unordered trees and its application to analysis of glycan structures.},
journal = {BMC Bioinformatics},
volume = {12 Suppl 1},
pages = {S13},
year = {2011},
doi = {10.1186/1471-2105-12-S1-S13},
}
```

```
@article{Ishikawa:2011,
author = {Ishikawa, Hiroshi},
title = {Transformation of general binary MRF minimization to the first-order case.},
journal = {IEEE Transactions On Pattern Analysis and Machine Intelligence},
volume = {33},
number = {6},
pages = {1234-49},
year = {2011},
month = jun,
doi = {10.1109/TPAMI.2010.91},
}
```

```
@article{JiaoHS:2011,
author = {Jiao, Qing-Ju and Huang, Yan and Shen, Hong-Bin},
title = {Large-scale mining co-expressed genes in Arabidopsis anther: from pair to group.},
journal = {Computational Biology and Chemistry},
volume = {35},
number = {2},
pages = {62-8},
year = {2011},
month = apr,
doi = {10.1016/j.compbiolchem.2011.01.003},
}
```

```
@article{Kawabata:2011,
author = {Kawabata, Takeshi},
title = {Build-up algorithm for atomic correspondence between chemical structures.},
journal = {Journal of Chemical Information and Modeling},
volume = {51},
number = {8},
pages = {1775-87},
year = {2011},
month = aug,
doi = {10.1021/ci2001023},
}
```

```
@article{LeeRMH:2011,
author = {Lee, Conrad and Reid, Fergal and McDaid, Aaron and Hurley, Neil},
title = {Seeding for pervasively overlapping communities},
journal = {Phys. Rev. E},
volume = {83},
number = {6},
pages = {066107},
publisher = {American Physical Society},
year = {2011},
doi = {10.1103/PhysRevE.83.066107},
}
```

Schizophrenia, bipolar disorder, and major depression are devastating mental diseases, each with distinctive yet overlapping epidemiologic characteristics. Microarray and proteomics data have revealed genes which expressed abnormally in patients. Several single nucleotide polymorphisms (SNPs) and mutations are associated with one or more of the three diseases. Nevertheless, there are few studies on the interactions among the disease-associated genes and proteins.

Results

This study, for the first time, incorporated microarray and protein-protein interaction (PPI) databases to construct the PPI network of abnormally expressed genes in postmortem brain samples of schizophrenia, bipolar disorder, and major depression patients. The samples were collected from Brodmann area (BA) 10 of the prefrontal cortex. Abnormally expressed disease genes were selected by t-tests comparing the disease and control samples. These genes were involved in housekeeping functions (e.g. translation, transcription, energy conversion, and metabolism), in brain specific functions (e.g. signal transduction, neuron cell differentiation, and cytoskeleton), or in stress responses (e.g. heat shocks and biotic stress).The diseases were interconnected through several "switchboard"-like nodes in the PPI network or shared abnormally expressed genes. A "core" functional module which consisted of a tightly knitted sub-network of clique-5 and -4s was also observed. These cliques were formed by 12 genes highly expressed in both disease and control samples.

Conclusions

Several previously unidentified disease marker genes and drug targets, such as SBNO2 (schizophrenia), SEC24C (bipolar disorder), and SRRT (major depression), were identified based on statistical and topological analyses of the PPI network. The shared or interconnecting marker genes may explain the shared symptoms of the studied diseases. Furthermore, the "switchboard" genes, such as APP, UBC, and YWHAZ, are proposed as potential targets for developing new treatments due to their functional and topological significance.

```
@article{LeeTYLKHLHK:2011,
author = {Lee, Sheng-An and Tsao, Theresa Tsun-Hui and Yang, Ko-Chun and Lin, Han and Kuo, Yu-Lun and Hsu, Chien-Hsiang and Lee, Wen-Kuei and Huang, Kuo-Chuan and Kao, Cheng-Yan},
title = {Construction and analysis of the protein-protein interaction networks for schizophrenia, bipolar disorder, and major depression.},
journal = {BMC Bioinformatics},
volume = {12 Suppl 13},
pages = {S20},
year = {2011},
month = nov,
doi = {10.1186/1471-2105-12-S13-S20},
}
```

```
@article{LiLSLHMWWLWZLY:2011,
author = {Li, Xia and Li, Chunquan and Shang, Desi and Li, Jing and Han, Junwei and Miao, Yingbo and Wang, Yan and Wang, Qianghu and Li, Wei and Wu, Chao and Zhang, Yunpeng and Li, Xiang and Yao, Qianlan},
title = {The implications of relationships between human diseases and metabolic subpathways.},
journal = {Plos One},
volume = {6},
number = {6},
pages = {e21131},
year = {2011},
doi = {10.1371/journal.pone.0021131},
}
```

```
@article{NunezVB:2011,
author = {Nunez, Pedro and Vazquez-Martin, Ricardo and Bandera, Antonio},
title = {Visual odometry based on structural matching of local invariant features using stereo camera sensor.},
journal = {Sensors},
volume = {11},
number = {7},
pages = {7262-84},
year = {2011},
doi = {10.3390/s110707262},
}
```

The MatrixMatchMaker algorithm was recently introduced to detect the similarity between phylogenetic trees and thus the coevolution between proteins. MMM finds the largest common submatrices between pairs of phylogenetic distance matrices, and has numerous advantages over existing methods of coevolution detection. However, these advantages came at the cost of a very long execution time.

Results

In this paper, we show that the problem of finding the maximum submatrix reduces to a multiple maximum clique subproblem on a graph of protein pairs. This allowed us to develop a new algorithm and program implementation, MMMvII, which achieved more than 600x speedup with comparable accuracy to the original MMM.

Conclusions

MMMvII will thus allow for more more extensive and intricate analyses of coevolution.

Availability

An implementation of the MMMvII algorithm is available at: http://www.uhnresearch.ca/labs/tillier/MMMWEBvII/MMMWEBvII.php. University of Toronto, Toronto, Canada. arod@eecg.toronto.edu.

```
@article{RodionovBRT:2011,
author = {Rodionov, Alex and Bezginov, Alexandr and Rose, Jonathan and Tillier, Elisabeth Rm},
title = {A new, fast algorithm for detecting protein coevolution using maximum compatible cliques.},
journal = {Algorithms for Molecular Biology},
volume = {6},
pages = {17},
year = {2011},
doi = {10.1186/1748-7188-6-17},
}
```

Microbial communities in their natural environments exhibit phenotypes that can directly cause particular diseases, convert biomass or wastewater to energy, or degrade various environmental contaminants. Understanding how these communities realize specific phenotypic traits (e.g., carbon fixation, hydrogen production) is critical for addressing health, bioremediation, or bioenergy problems.

Results

In this paper, we describe a graph-theoretical method for in silico prediction of the cellular subsystems that are related to the expression of a target phenotype. The proposed (alpha, beta)-motif finder approach allows for identification of these phenotype-related subsystems that, in addition to metabolic subsystems, could include their regulators, sensors, transporters, and even uncharacterized proteins. By comparing dozens of genome-scale networks of functionally associated proteins, our method efficiently identifies those statistically significant functional modules that are in at least alpha networks of phenotype-expressing organisms but appear in no more than beta networks of organisms that do not exhibit the target phenotype. It has been shown via various experiments that the enumerated modules are indeed related to phenotype-expression when tested with different target phenotypes like hydrogen production, motility, aerobic respiration, and acid-tolerance.

Conclusion

Thus, we have proposed a methodology that can identify potential statistically significant phenotype-related functional modules. The functional module is modeled as an (alpha, beta)-clique, where alpha and beta are two criteria introduced in this work. We also propose a novel network model, called the two-typed, divided network. The new network model and the criteria make the problem tractable even while very large networks are being compared. The code can be downloaded from http://www.freescience.org/cs/ABClique/ 27695, USA.

```
@article{SchmidtRPCSMS:2011,
author = {Schmidt, Matthew C. and Rocha, Andrea M. and Padmanabhan, Kanchana and Chen, Zhengzhang and Scott, Kathleen and Mihelcic, James R. and Samatova, Nagiza F.},
title = {Efficient alpha, beta-motif finder for identification of phenotype-related functional modules.},
journal = {BMC Bioinformatics},
volume = {12},
pages = {440},
year = {2011},
doi = {10.1186/1471-2105-12-440},
}
```

```
@article{SkippingtonR:2011,
author = {Skippington, Elizabeth and Ragan, Mark A.},
title = {Lateral genetic transfer and the construction of genetic exchange communities.},
journal = {Fems Microbiology Reviews},
volume = {35},
number = {5},
pages = {707-35},
year = {2011},
month = sep,
doi = {10.1111/j.1574-6976.2010.00261.x},
}
```

```
@article{WangC:2011,
author = {Wang, I-Lin and Chang, Chia-Yuan},
title = {Mathematical properties and bounds on haplotyping populations by pure parsimony.},
journal = {Mathematical Biosciences},
volume = {231},
number = {2},
pages = {120-5},
year = {2011},
month = jun,
doi = {10.1016/j.mbs.2011.02.008},
}
```

```
@article{WelsZHHC:2011,
author = {Wels, Michael and Zheng, Yefeng and Huber, Martin and Hornegger, Joachim and Comaniciu, Dorin},
title = {A discriminative model-constrained EM approach to 3D MRI brain tissue classification and intensity non-uniformity correction.},
journal = {Physics in Medicine and Biology},
volume = {56},
number = {11},
pages = {3269-300},
year = {2011},
month = jun,
doi = {10.1088/0031-9155/56/11/007},
}
```

```
@article{YanZW:2011,
author = {Yan, Yan and Zhang, Shenggui and Wu, Fang-Xiang},
title = {Applications of graph theory in protein structure identification.},
journal = {Proteome Science},
volume = {9 Suppl 1},
pages = {S17},
year = {2011},
doi = {10.1186/1477-5956-9-S1-S17},
}
```

```
@article{ZhangJMTZ:2011,
author = {Zhanli Zhang and Xin Jiang and Lili Ma and Shaoting Tang and Zhiming Zheng},
title = {Detecting communities in clustered networks based on group action on set},
journal = {Physica A: Statistical Mechanics and its Applications},
volume = {390},
number = {6},
pages = {1171--1181},
year = {2011},
doi = {10.1016/j.physa.2010.11.029},
}
```

```
@article{ZhangL:2011,
author = {Zhang, Hongyan and Liu, Xiyu},
title = {A CLIQUE algorithm using DNA computing techniques based on closed-circle DNA sequences.},
journal = {Bio Systems},
volume = {105},
number = {1},
pages = {73-82},
year = {2011},
month = jul,
doi = {10.1016/j.biosystems.2011.03.004},
}
```

```
@article{ZhengLYW:2011,
author = {Zheng, Xiaoqi and Liu, Taigang and Yang, Zhongnan and Wang, Jun},
title = {Large cliques in Arabidopsis gene coexpression network and motif discovery.},
journal = {Journal of Plant Physiology},
volume = {168},
number = {6},
pages = {611-8},
year = {2011},
month = apr,
doi = {10.1016/j.jplph.2010.09.010},
}
```

Most of the existing in silico phosphorylation site prediction systems use machine learning approach that requires preparing a good set of classification data in order to build the classification knowledge. Furthermore, phosphorylation is catalyzed by kinase enzymes and hence the kinase information of the phosphorylated sites has been used as major classification data in most of the existing systems. Since the number of kinase annotations in protein sequences is far less than that of the proteins being sequenced to date, the prediction systems that use the information found from the small clique of kinase annotated proteins can not be considered as completely perfect for predicting outside the clique. Hence the systems are certainly not generalized. In this paper, a novel generalized prediction system, PPRED (Phosphorylation PREDictor) is proposed that ignores the kinase information and only uses the evolutionary information of proteins for classifying phosphorylation sites.

Results

Experimental results based on cross validations and an independent benchmark reveal the significance of using the evolutionary information alone to classify phosphorylation sites from protein sequences. The prediction performance of the proposed system is better than those of the existing prediction systems that also do not incorporate kinase information. The system is also comparable to systems that incorporate kinase information in predicting such sites.

Conclusions

The approach presented in this paper provides an efficient way to identify phosphorylation sites in a given protein primary sequence that would be a valuable information for the molecular biologists working on protein phosphorylation sites and for bioinformaticians developing generalized prediction systems for the post translational modifications like phosphorylation or glycosylation. PPRED is publicly available at the URL http://www.cse.univdhaka.edu/ ashis/ppred/index.php. 1000, Bangladesh. ashis.csedu@gmail.com

```
@article{BiswasNS:2010,
author = {Biswas, Ashis Kumer and Noman, Nasimul and Sikder, Abdur Rahman},
title = {Machine learning approach to predict protein phosphorylation sites by incorporating evolutionary information.},
journal = {BMC Bioinformatics},
volume = {11},
pages = {273},
year = {2010},
doi = {10.1186/1471-2105-11-273},
}
```

```
@article{ChenY:2010,
author = {Chen, Rick C. S and Yang, Stephen J. H.},
title = {Applying DNA computation to intractable problems in social network analysis.},
journal = {Bio Systems},
volume = {101},
number = {3},
pages = {222-32},
year = {2010},
month = sep,
doi = {10.1016/j.biosystems.2010.05.006},
}
```

```
@article{CooperGBO:2010,
author = {Cooper, David L. and Gentle, James E. and Barreto, Ernest and Olds, James L.},
title = {Synchronized changes to relative neuron populations in postnatal human neocortical development.},
journal = {Cognitive Neurodynamics},
volume = {4},
number = {2},
pages = {151-63},
year = {2010},
month = jun,
doi = {10.1007/s11571-010-9103-3},
}
```

While protein secondary structure is well understood, representing the repetitive nature of tertiary packing in proteins remains difficult. We have developed a construct called the relative packing group (RPG) that applies the clique concept from graph theory as a natural basis for defining the packing motifs in proteins. An RPG is defined as a clique of residues, where every member contacts all others as determined by the Delaunay tessellation. Geometrically similar RPGs define a regular element of tertiary structure or tertiary motif (TerMo). This intuitive construct provides a simple approach to characterize general repetitive elements of tertiary structure.

Results

A dataset of over 4 million tetrahedral RPGs was clustered using different criteria to characterize the various aspects of regular tertiary structure in TerMos. Grouping this data within the SCOP classification levels of Family, Superfamily, Fold, Class and PDB showed that similar packing is shared across different folds. Classification of RPGs based on residue sequence locality reveals topological preferences according to protein sizes and secondary structure. We find that larger proteins favor RPGs with three local residues packed against a non-local residue. Classifying by secondary structure, helices prefer mostly local residues, sheets favor at least two local residues, while turns and coil populate with more local residues. To depict these TerMos, we have developed 2 complementary and intuitive representations: (i) Dirichlet process mixture density estimation of the torsion angle distributions and (ii) kernel density estimation of the Cartesian coordinate distribution. The TerMo library and representations software are available upon request.

```
@article{DayLDVT:2010,
author = {Day, Ryan and Lennox, Kristin P. and Dahl, David B. and Vannucci, Marina and Tsai, Jerry W.},
title = {Characterizing the regularity of tetrahedral packing motifs in protein tertiary structure.},
journal = {Bioinformatics},
volume = {26},
number = {24},
pages = {3059-66},
year = {2010},
month = dec,
doi = {10.1093/bioinformatics/btq573},
}
```

Exploitation of locally similar 3D patterns of physicochemical properties on the surface of a protein for detection of binding sites that may lack sequence and global structural conservation.

Results

An algorithm, ProBiS is described that detects structurally similar sites on protein surfaces by local surface structure alignment. It compares the query protein to members of a database of protein 3D structures and detects with sub-residue precision, structurally similar sites as patterns of physicochemical properties on the protein surface. Using an efficient maximum clique algorithm, the program identifies proteins that share local structural similarities with the query protein and generates structure-based alignments of these proteins with the query. Structural similarity scores are calculated for the query protein’s surface residues, and are expressed as different colors on the query protein surface. The algorithm has been used successfully for the detection of protein-protein, protein-small ligand and protein-DNA binding sites.

Availability

The software is available, as a web tool, free of charge for academic users at http://probis.cmm.ki.si.

```
@article{KoncJ:2010,
author = {Konc, Janez and Janezic, Dusanka},
title = {ProBiS algorithm for detection of structurally similar protein binding sites by local structural alignment.},
journal = {Bioinformatics},
volume = {26},
number = {9},
pages = {1160-8},
year = {2010},
month = may,
doi = {10.1093/bioinformatics/btq100},
}
```

```
@article{KumarTZ:2010,
author = {Kumar, M. Pawan and Torr, P. H S. and Zisserman, A.},
title = {OBJCUT: efficient segmentation using top-down and bottom-up cues.},
journal = {IEEE Transactions On Pattern Analysis and Machine Intelligence},
volume = {32},
number = {3},
pages = {530-45},
year = {2010},
month = mar,
doi = {10.1109/TPAMI.2009.16},
}
```

```
@article{LanCLLYHWHLH:2010,
author = {Lan, Ming-Ying and Chen, Chi-Long and Lin, Kuan-Ting and Lee, Sheng-An and Yang, Wu-Lung R. and Hsu, Chun-Nan and Wu, Jaw-Ching and Ho, Ching-Yin and Lin, Jin-Ching and Huang, Chi-Ying F.},
title = {From NPC therapeutic target identification to potential treatment strategy.},
journal = {Molecular Cancer Therapeutics},
volume = {9},
number = {9},
pages = {2511-23},
year = {2010},
month = sep,
doi = {10.1158/1535-7163.MCT-09-0966},
}
```

```
@article{LiWCCC:2010,
author = {Min Li and Jianxin Wang and Jianer Chen and Zhao Cai and Gang Chen},
title = {Identifying the overlapping complexes in protein interaction networks},
journal = {International Journal of Data Mining and Bioinformatics (IJDMB)},
volume = {4},
number = {1},
pages = {91--108},
publisher = {Inderscience Publishers},
year = {2010},
address = {Geneva, Switzerland},
doi = {10.1504/IJDMB.2010.030969},
}
```

Comparing 3D structures of homologous RNA molecules yields information about sequence and structural variability. To compare large RNA 3D structures, accurate automatic comparison tools are needed. In this article, we introduce a new algorithm and web server to align large homologous RNA structures nucleotide by nucleotide using local superpositions that accommodate the flexibility of RNA molecules. Local alignments are merged to form a global alignment by employing a maximum clique algorithm on a specially defined graph that we call the ’local alignment’ graph.

Results

The algorithm is implemented in a program suite and web server called ’R3D Align’. The R3D Align alignment of homologous 3D structures of 5S, 16S and 23S rRNA was compared to a high-quality hand alignment. A full comparison of the 16S alignment with the other state-of-the-art methods is also provided. The R3D Align program suite includes new diagnostic tools for the structural evaluation of RNA alignments. The R3D Align alignments were compared to those produced by other programs and were found to be the most accurate, in comparison with a high quality hand-crafted alignment and in conjunction with a series of other diagnostics presented. The number of aligned base pairs as well as measures of geometric similarity are used to evaluate the accuracy of the alignments.

Availability

R3D Align is freely available through a web server http://rna.bgsu.edu/R3DAlign. The MATLAB source code of the program suite is also freely available for download at that location. 45810, USA. r-rahrig@onu.edu

```
@article{RahrigLZ:2010,
author = {Rahrig, Ryan R. and Leontis, Neocles B. and Zirbel, Craig L.},
title = {R3D Align: global pairwise alignment of RNA 3D structures using local superpositions.},
journal = {Bioinformatics},
volume = {26},
number = {21},
pages = {2689-97},
year = {2010},
month = nov,
doi = {10.1093/bioinformatics/btq506},
}
```

```
@article{ReisenWKS:2010,
author = {Reisen, Felix and Weisel, Martin and Kriegl, Jan M. and Schneider, Gisbert},
title = {Self-organizing fuzzy graphs for structure-based comparison of protein pockets.},
journal = {Journal of Proteome Research},
volume = {9},
number = {12},
pages = {6498-510},
year = {2010},
month = dec,
doi = {10.1021/pr100719n},
}
```

Gene expression signatures are typically identified by correlating gene expression patterns to a disease phenotype of interest. However, individual gene-based signatures usually suffer from low reproducibility and interpretability.

Results

We have developed a novel algorithm Iterative Clique Enumeration (ICE) for identifying relatively independent maximal cliques as co-expression modules and a module-based approach to the analysis of gene expression data. Applying this approach on a public breast cancer dataset identified 19 modules whose expression levels were significantly correlated with tumor grade. The correlations were reproducible for 17 modules in an independent breast cancer dataset, and the reproducibility was considerably higher than that based on individual genes or modules identified by other algorithms. Sixteen out of the 17 modules showed significant enrichment in certain Gene Ontology (GO) categories. Specifically, modules related to cell proliferation and immune response were up-regulated in high-grade tumors while those related to cell adhesion was down-regulated. Further analyses showed that transcription factors NYFB, E2F1/E2F3, NRF1, and ELK1 were responsible for the up-regulation of the cell proliferation modules. IRF family and ETS family proteins were responsible for the up-regulation of the immune response modules. Moreover, inhibition of the PPARA signaling pathway may also play an important role in tumor progression. The module without GO enrichment was found to be associated with a potential genomic gain in 8q21-23 in high-grade tumors. The 17-module signature of breast tumor progression clustered patients into subgroups with significantly different relapse-free survival times. Namely, patients with lower cell proliferation and higher cell adhesion levels had significantly lower risk of recurrence, both for all patients (p = 0.004) and for those with grade 2 tumors (p = 0.017).

Conclusions

The ICE algorithm is effective in identifying relatively independent co-expression modules from gene co-expression networks and the module-based approach illustrated in this study provides a robust, interpretable, and mechanistic characterization of transcriptional changes. Nashville, TN 37240, USA.

```
@article{ShiDZ:2010,
author = {Shi, Zhiao and Derow, Catherine K. and Zhang, Bing},
title = {Co-expression module analysis reveals biological processes, genomic gain, and regulatory mechanisms associated with breast cancer progression.},
journal = {BMC Systems Biology},
volume = {4},
pages = {74},
year = {2010},
doi = {10.1186/1752-0509-4-74},
}
```

```
@article{SimonsM:2010,
author = {Simons, Shellie R. and Mawn, Barbara},
title = {Bullying in the workplace--a qualitative study of newly licensed registered nurses.},
journal = {Aaohn Journal},
volume = {58},
number = {7},
pages = {305-11},
year = {2010},
month = jul,
doi = {10.3928/08910162-20100616-02},
}
```

Identification of protein complexes in large interaction networks is crucial to understand principles of cellular organization and predict protein functions, which is one of the most important issues in the post-genomic era. Each protein might be subordinate multiple protein complexes in the real protein-protein interaction networks. Identifying overlapping protein complexes from protein-protein interaction networks is a considerable research topic.

Result

As an effective algorithm in identifying overlapping module structures, clique percolation method (CPM) has a wide range of application in social networks and biological networks. However, the recognition accuracy of algorithm CPM is lowly. Furthermore, algorithm CPM is unfit to identifying protein complexes with meso-scale when it applied in protein-protein interaction networks. In this paper, we propose a new topological model by extending the definition of k-clique community of algorithm CPM and introduced distance restriction, and develop a novel algorithm called CP-DR based on the new topological model for identifying protein complexes. In this new algorithm, the protein complex size is restricted by distance constraint to conquer the shortcomings of algorithm CPM. The algorithm CP-DR is applied to the protein interaction network of Sacchromyces cerevisiae and identifies many well known complexes.

Conclusion

The proposed algorithm CP-DR based on clique percolation and distance restriction makes it possible to identify dense subgraphs in protein interaction networks, a large number of which correspond to known protein complexes. Compared to algorithm CPM, algorithm CP-DR has more outstanding performance.

```
@article{WangLLP:2010,
author = {Wang, Jianxin and Liu, Binbin and Li, Min and Pan, Yi},
title = {Identifying protein complexes from interaction networks based on clique percolation and distance restriction},
journal = {BMC Genomics},
volume = {11},
number = {Suppl 2},
pages = {S10},
year = {2010},
doi = {10.1186/1471-2164-11-S2-S10},
}
```

```
@article{WitvlietBvKV:2010,
author = {Witvliet, Miranda and Brendgen, Mara and van Lier, Pol A. C and Koot, Hans M. and Vitaro, Frank},
title = {Early adolescent depressive symptoms: prediction from clique isolation, loneliness, and perceived social acceptance.},
journal = {Journal of Abnormal Child Psychology},
volume = {38},
number = {8},
pages = {1045-56},
year = {2010},
month = nov,
doi = {10.1007/s10802-010-9426-x},
}
```

```
@article{WitvlietvBKV:2010,
author = {Witvliet, Miranda and van Lier, Pol A. C and Brendgen, Mara and Koot, Hans M. and Vitaro, Frank},
title = {Longitudinal associations between clique membership status and internalizing and externalizing problems during late childhood.},
journal = {Journal of Clinical Child and Adolescent Psychology},
volume = {39},
number = {5},
pages = {693-704},
year = {2010},
doi = {10.1080/15374416.2010.501678},
}
```

```
@article{WitvlietvCK:2010,
author = {Witvliet, Miranda and van Lier, Pol A. C and Cuijpers, Pim and Koot, Hans M.},
title = {Change and stability in childhood clique membership, isolation from cliques, and associated child characteristics.},
journal = {Journal of Clinical Child and Adolescent Psychology},
volume = {39},
number = {1},
pages = {12-24},
year = {2010},
doi = {10.1080/15374410903401161},
}
```

```
@article{YangXNYZ:2010,
author = {Yang, Yi and Xu, Dong and Nie, Feiping and Yan, Shuicheng and Zhuang, Yueting},
title = {Image clustering using local discriminant models and global integration.},
journal = {IEEE Transactions On Image Processing},
volume = {19},
number = {10},
pages = {2761-73},
year = {2010},
month = oct,
doi = {10.1109/TIP.2010.2049235},
}
```

Accurate prediction of the domain content and arrangement in multi-domain proteins (which make up >65% of the large-scale protein databases) provides a valuable tool for function prediction, comparative genomics and studies of molecular evolution. However, scanning a multi-domain protein against a database of domain sequence profiles can often produce conflicting and overlapping matches. We have developed a novel method that employs heaviest weighted clique-finding (HCF), which we show significantly outperforms standard published approaches based on successively assigning the best non-overlapping match (Best Match Cascade, BMC).

Results

We created benchmark data set of structural domain assignments in the CATH database and a corresponding set of Hidden Markov Model-based domain predictions. Using these, we demonstrate that by considering all possible combinations of matches using the HCF approach, we achieve much higher prediction accuracy than the standard BMC method. We also show that it is essential to allow overlapping domain matches to a query in order to identify correct domain assignments. Furthermore, we introduce a straightforward and effective protocol for resolving any overlapping assignments, and producing a single set of non-overlapping predicted domains. AVAILABILITY AND IMPLEMENTATION: The new approach will be used to determine MDAs for UniProt and Ensembl, and made available via the Gene3D website: http://gene3d.biochem.ucl.ac.uk/Gene3D/. The software has been implemented in C++ and compiled for Linux: source code and binaries can be found at: ftp://ftp.biochem.ucl.ac.uk/pub/gene3d_data/DomainFinder3/

Contact

yeats@biochem.ucl.ac.uk SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online. yeats@biochem.ucl.ac.uk

```
@article{YeatsRO:2010,
author = {Yeats, Corin and Redfern, Oliver C. and Orengo, Christine},
title = {A fast and automated solution for accurately resolving protein domain architectures.},
journal = {Bioinformatics},
volume = {26},
number = {6},
pages = {745-51},
year = {2010},
month = mar,
doi = {10.1093/bioinformatics/btq034},
}
```

```
@inproceedings{ZhaoZP:2011,
author = {Kun Zhao and Shao-Wu Zhang and Quan Pan},
title = {Fuzzy analysis for overlapping community structure of complex network},
booktitle = {Control and Decision Conference (CCDC), 2010 Chinese},
pages = {3976--3981},
publisher = {IEEE Computer Society},
year = {2010},
doi = {10.1109/CCDC.2010.5498458},
}
```

```
@article{Barber:2009,
author = {Barber, David},
title = {Identifying graph clusters using variational inference and links to covariance parametrization.},
journal = {Philosophical Transactions. Series A, Mathematical, Physical, and Engineering Sciences},
volume = {367},
number = {1906},
pages = {4407-26},
year = {2009},
month = nov,
doi = {10.1098/rsta.2009.0117},
}
```

```
@article{CaetanoM:2009,
author = {Caetano, Tiberio S. and McAuley, Julian J.},
title = {Faster graphical models for point-pattern matching.},
journal = {Spatial Vision},
volume = {22},
number = {5},
pages = {443-53},
year = {2009},
doi = {10.1163/156856809789476083},
}
```

```
@article{ChenC:2009,
author = {Chen, Jiun-Rung and Chang, Ye-In},
title = {A Condition-Enumeration Tree method for mining biclusters from DNA microarray data sets.},
journal = {Bio Systems},
volume = {97},
number = {1},
pages = {44-59},
year = {2009},
month = jul,
doi = {10.1016/j.biosystems.2009.04.003},
}
```

```
@article{Darehmiraki:2009,
author = {Darehmiraki, Majid},
title = {A new solution for maximal clique problem based sticker model.},
journal = {Bio Systems},
volume = {95},
number = {2},
pages = {145-9},
year = {2009},
month = feb,
doi = {10.1016/j.biosystems.2008.09.007},
}
```

```
@article{DebVV:2009,
author = {Deb, Dhruba and Vishveshwara, Saraswathi and Vishveshwara, Smitha},
title = {Understanding protein structure from a percolation perspective.},
journal = {Biophysical Journal},
volume = {97},
number = {6},
pages = {1787-94},
year = {2009},
month = sep,
doi = {10.1016/j.bpj.2009.07.016},
}
```

```
@article{FatakiaCC:2009,
author = {Fatakia, Sarosh N. and Costanzi, Stefano and Chow, Carson C.},
title = {Computing highly correlated positions using mutual information and graph theory for G protein-coupled receptors.},
journal = {Plos One},
volume = {4},
number = {3},
pages = {e4681},
year = {2009},
doi = {10.1371/journal.pone.0004681},
}
```

```
@article{GardinerCTG:2009,
author = {Gardiner, Eleanor J. and Cosgrove, David A. and Taylor, Robin and Gillet, Valerie J.},
title = {Multiobjective optimization of pharmacophore hypotheses: bias toward low-energy conformations.},
journal = {Journal of Chemical Information and Modeling},
volume = {49},
number = {12},
pages = {2761-73},
year = {2009},
month = dec,
doi = {10.1021/ci9002816},
}
```

```
@article{HillsMMSS:2009,
author = {Hills, Thomas T. and Maouene, Mounir and Maouene, Josita and Sheya, Adam and Smith, Linda},
title = {Categorical structure among shared features in networks of early-learned nouns.},
journal = {Cognition},
volume = {112},
number = {3},
pages = {381-96},
year = {2009},
month = sep,
doi = {10.1016/j.cognition.2009.06.002},
}
```

```
@article{KohliPT:2009,
author = {Kohli, Pushmeet and Pawan Kumar, M. and Torr, Philip H. S.},
title = {P3 & beyond: move making algorithms for solving higher order functions.},
journal = {IEEE Transactions On Pattern Analysis and Machine Intelligence},
volume = {31},
number = {9},
pages = {1645-56},
year = {2009},
month = sep,
doi = {10.1109/TPAMI.2008.217},
}
```

```
@article{LiZPTLZ:2009,
author = {Li, Jing and Zimmerman, Lisa J. and Park, Byung-Hoon and Tabb, David L. and Liebler, Daniel C. and Zhang, Bing},
title = {Network-assisted protein identification and data interpretation in shotgun proteomics.},
journal = {Molecular Systems Biology},
volume = {5},
pages = {303},
year = {2009},
doi = {10.1038/msb.2009.54},
}
```

```
@article{LinJHHMH:2009,
author = {Lin, Chen-Ching and Juan, Hsueh-Fen and Hsiang, Jen-Tsung and Hwang, Yih-Chii and Mori, Hirotada and Huang, Hsuan-Cheng},
title = {Essential core of protein-protein interaction network in Escherichia coli.},
journal = {Journal of Proteome Research},
volume = {8},
number = {4},
pages = {1925-31},
year = {2009},
month = apr,
doi = {10.1021/pr8008786},
}
```

Cardiovascular disease is the main cause of premature death in patients with type 1 diabetes. Patients with diabetic kidney disease have an increased risk of heart attack or stroke. Accurate knowledge of the complex inter-dependencies between the risk factors is critical for pinpointing the best targets for research and treatment. Therefore, the aim of this study was to describe the association patterns between clinical and biochemical features of diabetic complications.

Methods

Medical records and serum and urine samples of 4,197 patients with type 1 diabetes were collected from health care centers in Finland. At baseline, the mean diabetes duration was 22 years, 52% were male, 23% had kidney disease (urine albumin excretion over 300 mg/24 h or end-stage renal disease) and 8% had a history of macrovascular events. All-cause mortality was evaluated after an average of 6.5 years of follow-up (25,714 patient years). The dataset comprised 28 clinical and 25 biochemical variables that were regarded as the nodes of a network to assess their mutual relationships.

Results

The networks contained cliques that were densely inter-connected (r > 0.6), including cliques for high-density lipoprotein (HDL) markers, for triglycerides and cholesterol, for urinary excretion and for indices of body mass. The links between the cliques showed biologically relevant interactions: an inverse relationship between HDL cholesterol and the triglyceride clique (r < -0.3, P < 10(-16)), a connection between triglycerides and body mass via C-reactive protein (r > 0.3, P < 10(-16)) and intermediate-density cholesterol as the connector between lipoprotein metabolism and albuminuria (r > 0.3, P < 10(-16)). Aging and macrovascular disease were linked to death via working ability and retinopathy. Diabetic kidney disease, serum creatinine and potassium, retinopathy and blood pressure were inter-connected. Blood pressure correlations indicated accelerated vascular aging in individuals with kidney disease (P < 0.001).

Conclusion

The complex pattern of links between diverse characteristics and the lack of a single dominant factor suggests a need for multifactorial and multidisciplinary paradigms for the research, treatment and prevention of diabetic complications. Helsinki, Finland. ville-petteri.makinen@finndiane.fi

```
@article{MakinenFTWKAG:2009,
author = {Makinen, Ville-Petteri and Forsblom, Carol and Thorn, Lena M. and Waden, Johan and Kaski, Kimmo and Ala-Korpela, Mika and Groop, Per-Henrik},
title = {Network of vascular diseases, death and biochemical characteristics in a set of 4,197 patients with type 1 diabetes (the FinnDiane Study).},
journal = {Cardiovascular Diabetology},
volume = {8},
pages = {54},
year = {2009},
doi = {10.1186/1475-2840-8-54},
}
```

Biological networks characterize the interactions of biomolecules at a systems-level. One important property of biological networks is the modular structure, in which nodes are densely connected with each other, but between which there are only sparse connections. In this report, we attempted to find the relationship between the network topology and formation of modular structure by comparing gene co-expression networks with random networks. The organization of gene functional modules was also investigated.

Results

We constructed a genome-wide Arabidopsis gene co-expression network (AGCN) by using 1094 microarrays. We then analyzed the topological properties of AGCN and partitioned the network into modules by using an efficient graph clustering algorithm. In the AGCN, 382 hub genes formed a clique, and they were densely connected only to a small subset of the network. At the module level, the network clustering results provide a systems-level understanding of the gene modules that coordinate multiple biological processes to carry out specific biological functions. For instance, the photosynthesis module in AGCN involves a very large number (> 1000) of genes which participate in various biological processes including photosynthesis, electron transport, pigment metabolism, chloroplast organization and biogenesis, cofactor metabolism, protein biosynthesis, and vitamin metabolism. The cell cycle module orchestrated the coordinated expression of hundreds of genes involved in cell cycle, DNA metabolism, and cytoskeleton organization and biogenesis. We also compared the AGCN constructed in this study with a graphical Gaussian model (GGM) based Arabidopsis gene network. The photosynthesis, protein biosynthesis, and cell cycle modules identified from the GGM network had much smaller module sizes compared with the modules found in the AGCN, respectively.

Conclusion

This study reveals new insight into the topological properties of biological networks. The preferential hub-hub connections might be necessary for the formation of modular structure in gene co-expression networks. The study also reveals new insight into the organization of gene functional modules. linyongmao@gmail.com

```
@article{MaoVDD:2009,
author = {Mao, Linyong and Van Hemert, John L. and Dash, Sudhansu and Dickerson, Julie A.},
title = {Arabidopsis gene co-expression network and its functional modules.},
journal = {BMC Bioinformatics},
volume = {10},
pages = {346},
year = {2009},
doi = {10.1186/1471-2105-10-346},
}
```

Progress in the life sciences cannot be made without integrating biomedical knowledge on numerous genes in order to help formulate hypotheses on the genetic mechanisms behind various biological phenomena, including diseases. There is thus a strong need for a way to automatically and comprehensively search from biomedical databases for related genes, such as genes in the same families and genes encoding components of the same pathways. Here we address the extraction of related genes by searching for densely-connected subgraphs, which are modeled as cliques, in a biomedical relational graph.

Results

We constructed a graph whose nodes were gene or disease pages, and edges were the hyperlink connections between those pages in the Online Mendelian Inheritance in Man (OMIM) database. We obtained over 20,000 sets of related genes (called ’gene modules’) by enumerating cliques computationally. The modules included genes in the same family, genes for proteins that form a complex, and genes for components of the same signaling pathway. The results of experiments using ’metabolic syndrome’-related gene modules show that the gene modules can be used to get a coherent holistic picture helpful for interpreting relations among genes.

Conclusion

We presented a data mining approach extracting related genes by enumerating cliques. The extracted gene sets provide a holistic picture useful for comprehending complex disease mechanisms. Japan. matsunagat@nttdata.co.jp

```
@article{MatsunagaYTM:2009,
author = {Matsunaga, Tsutomu and Yonemori, Chikara and Tomita, Etsuji and Muramatsu, Masaaki},
title = {Clique-based data mining for related genes in a biomedical database.},
journal = {BMC Bioinformatics},
volume = {10},
pages = {205},
year = {2009},
doi = {10.1186/1471-2105-10-205},
}
```

Commonly-occurring disease etiology may involve complex combinations of genes and exposures resulting in etiologic heterogeneity. We present a computational algorithm that employs clique-finding for heterogeneity and multidimensionality in biomedical and epidemiological research (the "CHAMBER" algorithm). METHODOLOGY/PRINCIPAL FINDINGS: This algorithm uses graph-building to (1) identify genetic variants that influence disease risk and (2) predict individuals at risk for disease based on inherited genotype. We use a set-covering algorithm to identify optimal cliques and a Boolean function that identifies etiologically heterogeneous groups of individuals. We evaluated this approach using simulated case-control genotype-disease associations involving two- and four-gene patterns. The CHAMBER algorithm correctly identified these simulated etiologies. We also used two population-based case-control studies of breast and endometrial cancer in African American and Caucasian women considering data on genotypes involved in steroid hormone metabolism. We identified novel patterns in both cancer sites that involved genes that sulfate or glucuronidate estrogens or catecholestrogens. These associations were consistent with the hypothesized biological functions of these genes. We also identified cliques representing the joint effect of multiple candidate genes in all groups, suggesting the existence of biologically plausible combinations of hormone metabolism genes in both breast and endometrial cancer in both races.

Conclusions

The CHAMBER algorithm may have utility in exploring the multifactorial etiology and etiologic heterogeneity in complex disease.

```
@article{MushlinGKR:2009,
author = {Mushlin, Richard A. and Gallagher, Stephen and Kershenbaum, Aaron and Rebbeck, Timothy R.},
title = {Clique-finding for heterogeneity and multidimensionality in biomarker epidemiology research: the CHAMBER algorithm.},
journal = {Plos One},
volume = {4},
number = {3},
pages = {e4862},
year = {2009},
doi = {10.1371/journal.pone.0004862},
}
```

Availability

http://jclust.embl.de/. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online. Germany. pavlopou@embl.de

```
@article{PavlopoulosMHSK:2009,
author = {Pavlopoulos, Georgios A. and Moschopoulos, Charalampos N. and Hooper, Sean D. and Schneider, Reinhard and Kossida, Sophia},
title = {jClust: a clustering and visualization toolbox.},
journal = {Bioinformatics},
volume = {25},
number = {15},
pages = {1994-6},
year = {2009},
month = aug,
doi = {10.1093/bioinformatics/btp330},
}
```

```
@article{PodolyanK:2009,
author = {Podolyan, Yevgeniy and Karypis, George},
title = {Common pharmacophore identification using frequent clique detection algorithm.},
journal = {Journal of Chemical Information and Modeling},
volume = {49},
number = {1},
pages = {13-21},
year = {2009},
month = jan,
doi = {10.1021/ci8002478},
}
```

```
@article{ThomasRB:2009,
author = {Thomas, John and Ramakrishnan, Naren and Bailey-Kellogg, Chris},
title = {Protein design by sampling an undirected graphical model of residue constraints.},
journal = {IEEE/Acm Transactions On Computational Biology and Bioinformatics / IEEE, Acm},
volume = {6},
number = {3},
pages = {506-16},
year = {2009},
month = jul,
doi = {10.1109/TCBB.2008.124},
}
```

The ubiquitin system (Ub-system) can be defined as the ensemble of components including Ub/ubiquitin-like proteins, their conjugation and deconjugation apparatus, binding partners and the proteasomal system. While several studies have concentrated on structure-function relationships and evolution of individual components of the Ub-system, a study of the system as a whole is largely lacking.

Results

Using numerous genome-scale datasets, we assemble for the first time a comprehensive reconstruction of the budding yeast Ub-system, revealing static and dynamic properties. We devised two novel representations, the rank plot to understand the functional diversification of different components and the clique-specific point-wise mutual-information network to identify significant interactions in the Ub-system.

Conclusions

Using these representations, evidence is provided for the functional diversification of components such as SUMO-dependent Ub-ligases. We also identify novel components of SCF (Skp1-cullin-F-box)-dependent complexes, receptors in the ERAD (endoplasmic reticulum associated degradation) system and a key role for Sus1 in coordinating multiple Ub-related processes in chromatin dynamics. We present evidence for a major impact of the Ub-system on large parts of the proteome via its interaction with the transcription regulatory network. Furthermore, the dynamics of the Ub-network suggests that Ub and SUMO modifications might function cooperatively with transcription control in regulating cell-cycle-stage-specific complexes and in reinforcing periodicities in gene expression. Combined with evolutionary information, the structure of this network helps in understanding the lineage-specific expansion of SCF complexes with a potential role in pathogen response and the origin of the ERAD and ESCRT systems. Bethesda, MD 20894, USA. venancit@ncbi.nlm.nih.gov

```
@article{VenancioBIA:2009,
author = {Venancio, Thiago M. and Balaji, S. and Iyer, Lakshminarayan M. and Aravind, L.},
title = {Reconstructing the ubiquitin network: cross-talk with other systems and identification of novel functions.},
journal = {Genome Biology},
volume = {10},
number = {3},
pages = {R33},
year = {2009},
doi = {10.1186/gb-2009-10-3-r33},
}
```

```
@article{WuchtyAF:2009,
author = {Wuchty, Stefan and Adams, John H. and Ferdig, Michael T.},
title = {A comprehensive Plasmodium falciparum protein interaction map reveals a distinct architecture of a core interactome.},
journal = {Proteomics},
volume = {9},
number = {7},
pages = {1841-9},
year = {2009},
month = apr,
doi = {10.1002/pmic.200800383},
}
```

```
@article{XiaoS:2009,
author = {Xiao, Yuanyuan and Segal, Mark R.},
title = {Identification of yeast transcriptional regulation networks using multivariate random forests.},
journal = {Plos Computational Biology},
volume = {5},
number = {6},
pages = {e1000414},
year = {2009},
month = jun,
doi = {10.1371/journal.pcbi.1000414},
}
```

```
@article{ZhangSWZ:2009,
author = {Zhang, Huanping and Song, Xiaofeng and Wang, Huinan and Zhang, Xiaobai},
title = {MIClique: An algorithm to identify differentially coexpressed disease gene subset from microarray data.},
journal = {Journal of Biomedicine & Biotechnology},
volume = {2009},
pages = {642524},
year = {2009},
doi = {10.1155/2009/642524},
}
```

```
@article{BezansonGMP:2008,
author = {Bezanson, Michelle and Garber, Paul A. and Murphy, John T. and Premo, L. S.},
title = {Patterns of subgrouping and spatial affiliation in a community of mantled howling monkeys (Alouatta palliata).},
journal = {American Journal of Primatology},
volume = {70},
number = {3},
pages = {282-93},
year = {2008},
month = mar,
doi = {10.1002/ajp.20486},
}
```

Graphs and networks are common analysis representations for biological systems. Many traditional graph algorithms such as k-clique, k-coloring, and subgraph matching have great potential as analysis techniques for newly available data in biology. Yet, as the amount of genomic and bionetwork information rapidly grows, scientists need advanced new computational strategies and tools for dealing with the complexities of the bionetwork analysis and the volume of the data.

Results

We introduce a computational framework for graph analysis called the Biological Graph Environment (BioGraphE), which provides a general, scalable integration platform for connecting graph problems in biology to optimized computational solvers and high-performance systems. This framework enables biology researchers and computational scientists to identify and deploy network analysis applications and to easily connect them to efficient and powerful computational software and hardware that are specifically designed and tuned to solve complex graph problems. In our particular application of BioGraphE to support network analysis in genome biology, we investigate the use of a Boolean satisfiability solver known as Survey Propagation as a core computational solver executing on standard high-performance parallel systems, as well as multi-threaded architectures.

Conclusion

In our application of BioGraphE to conduct bionetwork analysis of homology networks, we found that BioGraphE and a custom, parallel implementation of the Survey Propagation SAT solver were capable of solving very large bionetwork problems at high rates of execution on different high-performance computing platforms. Division, Pacific Northwest National Laboratory, Richland, Washington, USA. george.chin@pnl.gov

```
@article{ChinCNS:2008,
author = {Chin, George Jr and Chavarria, Daniel G. and Nakamura, Grant C. and Sofia, Heidi J.},
title = {BioGraphE: high-performance bionetwork analysis using the Biological Graph Environment.},
journal = {BMC Bioinformatics},
volume = {9 Suppl 6},
pages = {S6},
year = {2008},
doi = {10.1186/1471-2105-9-S6-S6},
}
```

```
@article{CuiCHH:2008,
author = {Cui, Guangyu and Chen, Yu and Huang, De-Shuang and Han, Kyungsook},
title = {An algorithm for finding functional modules and protein complexes in protein-protein interaction networks.},
journal = {Journal of Biomedicine & Biotechnology},
volume = {2008},
pages = {860270},
year = {2008},
doi = {10.1155/2008/860270},
}
```

```
@article{CushmanTWBS:2008,
author = {Cushman, John C. and Tillett, Richard L. and Wood, Joshua A. and Branco, Joshua M. and Schlauch, Karen A.},
title = {Large-scale mRNA expression profiling in the common ice plant, Mesembryanthemum crystallinum, performing C3 photosynthesis and Crassulacean acid metabolism (CAM).},
journal = {Journal of Experimental Botany},
volume = {59},
number = {7},
pages = {1875-94},
year = {2008},
doi = {10.1093/jxb/ern008},
}
```

```
@article{GhoshV:2008,
author = {Ghosh, Amit and Vishveshwara, Saraswathi},
title = {Variations in clique and community patterns in protein structures during allosteric communication: investigation of dynamically equilibrated structures of methionyl tRNA synthetase complexes.},
journal = {Biochemistry},
volume = {47},
number = {44},
pages = {11398-407},
year = {2008},
month = nov,
doi = {10.1021/bi8007559},
}
```

```
@article{GuturuD:2008,
author = {Guturu, Parthasarathy and Dantu, Ram},
title = {An impatient evolutionary algorithm with probabilistic tabu search for unified solution of some NP-hard problems in graph and set theory via clique finding.},
journal = {IEEE Transactions On Systems, Man, and Cybernetics. Part B, Cybernetics},
volume = {38},
number = {3},
pages = {645-66},
year = {2008},
month = jun,
doi = {10.1109/TSMCB.2008.915645},
}
```

```
@article{HongPCRPCK:2008,
author = {Hong, Seong-Eui and Park, Inju and Cha, Hyeseon and Rho, Seong-Hwan and Park, Woo Jin and Cho, Chunghee and Kim, Do Han},
title = {Identification of mouse heart transcriptomic network sensitive to various heart diseases.},
journal = {Biotechnology Journal},
volume = {3},
number = {5},
pages = {648-58},
year = {2008},
month = may,
doi = {10.1002/biot.200700250},
}
```

Comparative modeling is a technique to predict the three dimensional structure of a given protein sequence based primarily on its alignment to one or more proteins with experimentally determined structures. A major bottleneck of current comparative modeling methods is the lack of methods to accurately refine a starting initial model so that it approaches the resolution of the corresponding experimental structure. We investigate the effectiveness of a graph-theoretic clique finding approach to solve this problem.

Results

Our method takes into account the information presented in multiple templates/alignments at the three-dimensional level by mixing and matching regions between different initial comparative models. This method enables us to obtain an optimized conformation ensemble representing the best combination of secondary structures, resulting in the refined models of higher quality. In addition, the process of mixing and matching accumulates near-native conformations, resulting in discriminating the native-like conformation in a more effective manner. In the seventh Critical Assessment of Structure Prediction (CASP7) experiment, the refined models produced are more accurate than the starting initial models.

Conclusion

This novel approach can be applied without any manual intervention to improve the quality of comparative predictions where multiple template/alignment combinations are available for modeling, producing conformational models of higher quality than the starting initial predictions. Seattle, WA 98195, USA. tianyunl@stanford.edu

```
@article{LiuGS:2008,
author = {Liu, Tianyun and Guerquin, Michal and Samudrala, Ram},
title = {Improving the accuracy of template-based predictions by mixing and matching between initial models.},
journal = {BMC Structural Biology},
volume = {8},
pages = {24},
year = {2008},
doi = {10.1186/1472-6807-8-24},
}
```

```
@article{LiuKAvA:2008,
author = {Liu, Fan and Kirichenko, Anatoliy and Axenovich, Tatiana I. and van Duijn, Cornelia M. and Aulchenko, Yurii S.},
title = {An approach for cutting large and complex pedigrees for linkage analysis.},
journal = {European Journal of Human Genetics},
volume = {16},
number = {7},
pages = {854-60},
year = {2008},
month = jul,
doi = {10.1038/ejhg.2008.24},
}
```

```
@article{McAuleyCB:2008,
author = {McAuley, Julian J. and Caetano, Tiberio S. and Barbosa, Marconi S.},
title = {Graph rigidity, cyclic belief propagation, and point pattern matching.},
journal = {IEEE Transactions On Pattern Analysis and Machine Intelligence},
volume = {30},
number = {11},
pages = {2047-54},
year = {2008},
month = nov,
doi = {10.1109/TPAMI.2008.124},
}
```

Protein complexes integrate multiple gene products to coordinate many biological functions. Given a graph representing pairwise protein interaction data one can search for subgraphs representing protein complexes. Previous methods for performing such search relied on the assumption that complexes form a clique in that graph. While this assumption is true for some complexes, it does not hold for many others. New algorithms are required in order to recover complexes with other types of topological structure.

Results

We present an algorithm for inferring protein complexes from weighted interaction graphs. By using graph topological patterns and biological properties as features, we model each complex subgraph by a probabilistic Bayesian network (BN). We use a training set of known complexes to learn the parameters of this BN model. The log-likelihood ratio derived from the BN is then used to score subgraphs in the protein interaction graph and identify new complexes. We applied our method to protein interaction data in yeast. As we show our algorithm achieved a considerable improvement over clique based algorithms in terms of its ability to recover known complexes. We discuss some of the new complexes predicted by our algorithm and determine that they likely represent true complexes.

Availability

Matlab implementation is available on the supporting website: www.cs.cmu.edu/ qyj/SuperComplex. USA.

```
@article{QiBFKB:2008,
author = {Qi, Yanjun and Balem, Fernanda and Faloutsos, Christos and Klein-Seetharaman, Judith and Bar-Joseph, Ziv},
title = {Protein complex identification by supervised graph local clustering.},
journal = {Bioinformatics},
volume = {24},
number = {13},
pages = {i250-8},
year = {2008},
month = jul,
doi = {10.1093/bioinformatics/btn164},
}
```

In recent years, a considerable amount of research effort has been directed to the analysis of biological networks with the availability of genome-scale networks of genes and/or proteins of an increasing number of organisms. A protein-protein interaction (PPI) network is a particular biological network which represents physical interactions between pairs of proteins of an organism. Major research on PPI networks has focused on understanding the topological organization of PPI networks, evolution of PPI networks and identification of conserved subnetworks across different species, discovery of modules of interaction, use of PPI networks for functional annotation of uncharacterized proteins, and improvement of the accuracy of currently available networks.

Results

In this article, we map known functional annotations of proteins onto a PPI network in order to identify frequently occurring interaction patterns in the functional space. We propose a new frequent pattern identification technique, PPISpan, adapted specifically for PPI networks from a well-known frequent subgraph identification method, gSpan. Existing module discovery techniques either look for specific clique-like highly interacting protein clusters or linear paths of interaction. However, our goal is different; instead of single clusters or pathways, we look for recurring functional interaction patterns in arbitrary topologies. We have applied PPISpan on PPI networks of Saccharomyces cerevisiae and identified a number of frequently occurring functional interaction patterns.

Conclusion

With the help of PPISpan, recurring functional interaction patterns in an organism’s PPI network can be identified. Such an analysis offers a new perspective on the modular organization of PPI networks. The complete list of identified functional interaction patterns is available at http://bioserver.ceng.metu.edu.tr/PPISpan/. 42075 Selcuklu, Konya, Turkey. eturanalp@selcuk.edu.tr

```
@article{TuranalpC:2008,
author = {Turanalp, Mehmet E. and Can, Tolga},
title = {Discovering functional interaction patterns in protein-protein interaction networks.},
journal = {BMC Bioinformatics},
volume = {9},
pages = {276},
year = {2008},
doi = {10.1186/1471-2105-9-276},
}
```

```
@article{ZengL:2008,
author = {Zeng, Jia and Liu, Zhi-Qiang},
title = {Markov random field-based statistical character structure modeling for handwritten Chinese character recognition.},
journal = {IEEE Transactions On Pattern Analysis and Machine Intelligence},
volume = {30},
number = {5},
pages = {767-80},
year = {2008},
month = may,
doi = {10.1109/TPAMI.2007.70734},
}
```

```
@article{tenMR:2008,
author = {ten Caat, Michael and Maurits, Natasha M. and Roerdink, Jos B. T M.},
title = {Data-driven visualization and group analysis of multichannel EEG coherence with functional units.},
journal = {IEEE Transactions On Visualization and Computer Graphics},
volume = {14},
number = {4},
pages = {756-71},
year = {2008},
month = jul,
doi = {10.1109/TVCG.2008.21},
}
```

```
@article{CarvalhoMW:2007,
author = {Carvalho, Carlos M. and Massam, H{\'e}l{\`e}ne and West, Mike},
title = {Simulation of hyper-inverse {W}ishart distributions in graphical models},
journal = {Biometrika},
volume = {94},
number = {3},
pages = {647--659},
year = {2007},
doi = {10.1093/biomet/asm056},
}
```

```
@article{DanchinFN:2007,
author = {Danchin, Antoine and Fang, Gang and Noria, Stanislas},
title = {The extant core bacterial proteome is an archive of the origin of life.},
journal = {Proteomics},
volume = {7},
number = {6},
pages = {875-89},
year = {2007},
month = mar,
doi = {10.1002/pmic.200600442},
}
```

In this paper, we present the algorithm ComTector(Community DeTector) which is more efficient for the community detection in large-scale social networks based on the nature of overlapping communities in the real world. This algorithm does not require any priori knowledge about the number or the original division of the communities. Because real networks are often large sparse graphs, its running time is thus \(O(C \times Tri^2)\), where \(C\) is the number of the detected communities and \(Tri\) is the number of the triangles in the given network for the worst case. Then we propose a general naming method by combining the topological information with the entity attributes to define the discovered communities. With respected to practical applications, ComTector is challenged with several real life networks including the Zachary Karate Club, American College Football, Scientific Collaboration, and Telecommunications Call networks. Experimental results show that this algorithm can extract meaningful communities that are agreed with both of the objective facts and our intuitions.

```
@inproceedings{DuWPWX:2007,
author = {Du, Nan and Wu, Bin and Pei, Xin and Wang, Bai and Xu, Liutong},
title = {Community detection in large-scale social networks},
booktitle = {Proceedings of the 9th WebKDD and 1st SNA-KDD 2007 workshop on Web mining and social network analysis},
series = {WebKDD/SNA-KDD '07},
pages = {16--25},
publisher = {ACM},
year = {2007},
address = {New York, NY, USA},
doi = {10.1145/1348549.1348552},
}
```

```
@article{FinocchiaroMCM:2007,
author = {Finocchiaro, Giacomo and Mancuso, Francesco Mattia and Cittaro, Davide and Muller, Heiko},
title = {Graph-based identification of cancer signaling pathways from published gene expression signatures using PubLiME.},
journal = {Nucleic Acids Research},
volume = {35},
number = {7},
pages = {2343-55},
year = {2007},
doi = {10.1093/nar/gkm119},
}
```

```
@article{Garcia-ArnauMRS:2007,
author = {Garcia-Arnau, Marc and Manrique, Daniel and Rodriguez-Paton, Alfonso and Sosik, Petr},
title = {A P system and a constructive membrane-inspired DNA algorithm for solving the Maximum Clique Problem.},
journal = {Bio Systems},
volume = {90},
number = {3},
pages = {687-97},
year = {2007},
month = nov,
doi = {10.1016/j.biosystems.2007.02.005},
}
```

```
@article{Good:2007,
author = {Good, Andrew C.},
title = {Novel DOCK clique driven 3D similarity database search tools for molecule shape matching and beyond: adding flexibility to the search for ligand kin.},
journal = {Journal of Molecular Graphics & Modelling},
volume = {26},
number = {3},
pages = {656-66},
year = {2007},
month = oct,
doi = {10.1016/j.jmgm.2007.03.016},
}
```

The Bacteroidetes and Chlorobi species constitute two main groups of the Bacteria that are closely related in phylogenetic trees. The Bacteroidetes species are widely distributed and include many important periodontal pathogens. In contrast, all Chlorobi are anoxygenic obligate photoautotrophs. Very few (or no) biochemical or molecular characteristics are known that are distinctive characteristics of these bacteria, or are commonly shared by them.

Results

Systematic blast searches were performed on each open reading frame in the genomes of Porphyromonas gingivalis W83, Bacteroides fragilis YCH46, B. thetaiotaomicron VPI-5482, Gramella forsetii KT0803, Chlorobium luteolum (formerly Pelodictyon luteolum) DSM 273 and Chlorobaculum tepidum (formerly Chlorobium tepidum) TLS to search for proteins that are uniquely present in either all or certain subgroups of Bacteroidetes and Chlorobi. These studies have identified > 600 proteins for which homologues are not found in other organisms. This includes 27 and 51 proteins that are specific for most of the sequenced Bacteroidetes and Chlorobi genomes, respectively; 52 and 38 proteins that are limited to species from the Bacteroidales and Flavobacteriales orders, respectively, and 5 proteins that are common to species from these two orders; 185 proteins that are specific for the Bacteroides genus. Additionally, 6 proteins that are uniquely shared by species from the Bacteroidetes and Chlorobi phyla (one of them also present in the Fibrobacteres) have also been identified. This work also describes two large conserved inserts in DNA polymerase III (DnaE) and alanyl-tRNA synthetase that are distinctive characteristics of the Chlorobi species and a 3 aa deletion in ClpB chaperone that is mainly found in various Bacteroidales, Flavobacteriales and Flexebacteraceae, but generally not found in the homologs from other organisms. Phylogenetic analyses of the Bacteroidetes and Chlorobi species is also reported based on concatenated sequences for 12 conserved proteins by different methods including the character compatibility (or clique) approach. The placement of Salinibacter ruber with other Bacteroidetes species was not resolved by other phylogenetic methods, but this affiliation was strongly supported by the character compatibility approach.

Conclusion

The molecular signatures described here provide novel tools for identifying and circumscribing species from the Bacteroidetes and Chlorobi phyla as well as some of their main groups in clear terms. These results also provide strong evidence that species from these two phyla (and also possibly Fibrobacteres) are specifically related to each other and they form a single superphylum. Functional studies on these proteins and indels should aid in the discovery of novel biochemical and physiological characteristics that are unique to these groups of bacteria. ON, Canada. gupta@mcmaster.ca

```
@article{GuptaL:2007,
author = {Gupta, Radhey S. and Lorenzini, Emily},
title = {Phylogeny and molecular signatures (conserved proteins and indels) that are specific for the Bacteroidetes and Chlorobi species.},
journal = {BMC Evolutionary Biology},
volume = {7},
pages = {71},
year = {2007},
doi = {10.1186/1471-2148-7-71},
}
```

```
@article{GuptaS:2007,
author = {Gupta, Radhey S. and Sneath, Peter H. A.},
title = {Application of the character compatibility approach to generalized molecular sequence data: branching order of the proteobacterial subdivisions.},
journal = {Journal of Molecular Evolution},
volume = {64},
number = {1},
pages = {90-100},
year = {2007},
month = jan,
doi = {10.1007/s00239-006-0082-2},
}
```

```
@article{HutchinsonR:2007,
author = {Hutchinson, Delyse M. and Rapee, Ronald M.},
title = {Do friends share similar body image and eating problems? The role of social networks and peer influences in early adolescence.},
journal = {Behaviour Research and Therapy},
volume = {45},
number = {7},
pages = {1557-77},
year = {2007},
month = jul,
doi = {10.1016/j.brat.2006.11.007},
}
```

```
@article{IronmongerWBCAASN:2007,
author = {Ironmonger, Alan and Whittaker, Benjamin and Baron, Andrew J. and Clique, Blandine and Adams, Chris J. and Ashcroft, Alison E. and Stockley, Peter G. and Nelson, Adam},
title = {Scanning conformational space with a library of stereo- and regiochemically diverse aminoglycoside derivatives: the discovery of new ligands for RNA hairpin sequences.},
journal = {Organic & Biomolecular Chemistry},
volume = {5},
number = {7},
pages = {1081-6},
year = {2007},
month = apr,
doi = {10.1039/b618683a},
}
```

```
@article{PallaBV:2007,
author = {Palla, Gergely and Barabasi, Albert-Laszlo and Vicsek, Tamas},
title = {Quantifying social group evolution.},
journal = {Nature},
volume = {446},
number = {7136},
pages = {664-7},
year = {2007},
month = apr,
doi = {10.1038/nature05670},
}
```

Methods

All living organisms and the survival of all cells critically depend on their ability to sense and quickly adapt to changes in the environment and to other stress conditions. We study stress response mechanisms in Saccharomyces cerevisiae by identifying genes that, according to very stringent criteria, have persistent co-expression under a variety of stress conditions. This is enabled through a fast clique search method applied to the intersection of several co-expression graphs calculated over the data of Gasch et al. This method exploits the topological characteristics of these graphs.

Results

We observe cliques in the intersection graphs that are much larger than expected under a null model of changing gene identities for different stress conditions but maintaining the co-expression topology within each one. Persistent cliques are analyzed to identify enriched function as well as enriched regulation by a small number of TFs. These TFs, therefore, characterize a universal and persistent reaction to stress response. We further demonstrate that the vertices (genes) of many cliques in the intersection graphs are co-localized in the yeast genome, to a degree far beyond the random expectation. Co-localization can hypothetically contribute to a quick co-ordinated response. We propose the use of persistent cliques in further study of properties of co-regulation. 32000, Israel. olegro@cs.technion.ac.il

```
@article{RokhlenkoWY:2007,
author = {Rokhlenko, Oleg and Wexler, Ydo and Yakhini, Zohar},
title = {Similarities and differences of gene expression in yeast stress conditions.},
journal = {Bioinformatics},
volume = {23},
number = {2},
pages = {e184-90},
year = {2007},
month = jan,
doi = {10.1093/bioinformatics/btl308},
}
```

```
@article{Tsien:2007,
author = {Tsien, Joe Z.},
title = {Real-time neural coding of memory.},
journal = {Progress in Brain Research},
volume = {165},
pages = {105-22},
year = {2007},
doi = {10.1016/S0079-6123(06)65007-3},
}
```

```
@article{YouniesW:2007,
author = {Younies, Hassan and Wesolowsky, George O.},
title = {Planar maximal covering location problem under block norm distance measure},
journal = {Journal of the Operational Research Society},
volume = {58},
number = {6},
pages = {740-750},
year = {2007},
doi = {10.1057/palgrave.jors.2602172},
}
```

```
@article{ZhengZS:2007,
author = {Zheng, Chunfang and Zhu, Qian and Sankoff, David},
title = {Removing noise and ambiguities from comparative maps in rearrangement analysis.},
journal = {IEEE/Acm Transactions On Computational Biology and Bioinformatics / IEEE, Acm},
volume = {4},
number = {4},
pages = {515-22},
year = {2007},
month = oct,
doi = {10.1109/TCBB.2007.1075},
}
```

Availability: CFinder (for Windows, Linux and Macintosh) and its manual can be downloaded from http://angel.elte.hu/clustering.

```
@article{AdamcsekPFDV:2006,
author = {Adamcsek, Bal{\'a}zs and Palla, Gergely and Farkas, Ill{\'e}s J. and Der{\'e}nyi, Imre and Vicsek, Tam{\'a}s},
title = {CFinder: locating cliques and overlapping modules in biological networks},
journal = {Bioinformatics},
volume = {22},
number = {8},
pages = {1021--1023},
publisher = {Oxford University Press},
year = {2006},
doi = {10.1093/bioinformatics/btl039},
}
```

```
@article{BarkerBCGKWG:2006,
author = {Barker, Edward J. and Buttar, David and Cosgrove, David A. and Gardiner, Eleanor J. and Kitts, Paula and Willett, Peter and Gillet, Valerie J.},
title = {Scaffold hopping using clique detection applied to reduced graphs.},
journal = {Journal of Chemical Information and Modeling},
volume = {46},
number = {2},
pages = {503-11},
year = {2006},
month = mar,
doi = {10.1021/ci050347r},
}
```

```
@article{BoginskiBP:2006,
author = {Boginski, Vladimir and Butenko, Sergiy and Pardalos, Panos M.},
title = {Mining market data: A network approach},
journal = {Computers & Operations Research},
volume = {33},
number = {11},
pages = {3171--3184},
publisher = {Elsevier},
year = {2006},
doi = {10.1016/j.cor.2005.01.027},
}
```

```
@article{FengSY:2006,
author = {Feng, Jun and Sanil, Ashish and Young, S. Stanley},
title = {PharmID: pharmacophore identification using Gibbs sampling.},
journal = {Journal of Chemical Information and Modeling},
volume = {46},
number = {3},
pages = {1352-9},
year = {2006},
month = may,
doi = {10.1021/ci050427v},
}
```

```
@article{HamblyDMD:2006,
author = {Hambly, Kevin and Danzer, Joseph and Muskal, Steven and Debe, Derek A.},
title = {Interrogating the druggable genome with structural informatics.},
journal = {Molecular Diversity},
volume = {10},
number = {3},
pages = {273-81},
year = {2006},
month = aug,
doi = {10.1007/s11030-006-9035-3},
}
```

Structure matching plays an important part in understanding the functional role of biological structures. Bioinformatics assists in this effort by reformulating this process into a problem of finding a maximum common subgraph between graphical representations of these structures. Among the many different variants of the maximum common subgraph problem, the maximum common induced subgraph of two graphs is of special interest.

Results

Based on current research in the area of parameterized computation, we derive a new lower bound for the exact algorithms of the maximum common induced subgraph of two graphs which is the best currently known. Then we investigate the upper bound and design techniques for approaching this problem, specifically, reducing it to one of finding a maximum clique in the product graph of the two given graphs. Considering the upper bound result, the derived lower bound result is asymptotically tight.

Conclusion

Parameterized computation is a viable approach with great potential for investigating many applications within bioinformatics, such as the maximum common subgraph problem studied in this paper. With an improved hardness result and the proposed approaches in this paper, future research can be focused on further exploration of efficient approaches for different variants of this problem within the constraints imposed by real applications. Arkansas 72467, USA. xzhuang@csm.astate.edu

```
@article{HuangLJ:2006,
author = {Huang, Xiuzhen and Lai, Jing and Jennings, Steven F.},
title = {Maximum common subgraph: some upper bound and lower bound results.},
journal = {BMC Bioinformatics},
volume = {7 Suppl 4},
pages = {S6},
year = {2006},
doi = {10.1186/1471-2105-7-S4-S6},
}
```

The sparse connectivity of protein-protein interaction data sets makes identification of functional modules challenging. The purpose of this study is to critically evaluate a novel clustering technique for clustering and detecting functional modules in protein-protein interaction networks, termed STM.

Results

STM selects representative proteins for each cluster and iteratively refines clusters based on a combination of the signal transduced and graph topology. STM is found to be effective at detecting clusters with a diverse range of interaction structures that are significant on measures of biological relevance. The STM approach is compared to six competing approaches including the maximum clique, quasi-clique, minimum cut, betweeness cut and Markov Clustering (MCL) algorithms. The clusters obtained by each technique are compared for enrichment of biological function. STM generates larger clusters and the clusters identified have p-values that are approximately 125-fold better than the other methods on biological function. An important strength of STM is that the percentage of proteins that are discarded to create clusters is much lower than the other approaches.

Conclusion

STM outperforms competing approaches and is capable of effectively detecting both densely and sparsely connected, biologically relevant functional modules with fewer discards. Buffalo, USA. whwang2@cse.buffalo.edu

```
@article{HwangCZR:2006,
author = {Hwang, Woochang and Cho, Young-Rae and Zhang, Aidong and Ramanathan, Murali},
title = {A novel functional module detection algorithm for protein-protein interaction networks.},
journal = {Algorithms for Molecular Biology},
volume = {1},
pages = {24},
year = {2006},
doi = {10.1186/1748-7188-1-24},
}
```

```
@article{JenMMPWGW:2006,
author = {Jen, Chih-Hung and Manfield, Iain W. and Michalopoulos, Ioannis and Pinney, John W. and Willats, William G. T and Gilmartin, Philip M. and Westhead, David R.},
title = {The Arabidopsis co-expression tool (ACT): a WWW-based tool and database for microarray-based gene expression analysis.},
journal = {The Plant Journal},
volume = {46},
number = {2},
pages = {336-48},
year = {2006},
month = apr,
doi = {10.1111/j.1365-313X.2006.02681.x},
}
```

```
@article{LehmannKSN:2006,
author = {Lehmann, Katharina A. and Kaufmann, Michael and Steigele, Stephan and Nieselt, Kay},
title = {On the maximal cliques in c-max-tolerance graphs and their application in clustering molecular sequences},
journal = {Algorithms for Molecular Biology},
volume = {1},
number = {1},
year = {2006},
doi = {10.1186/1748-7188-1-9},
}
```

```
@article{LinOT:2006,
author = {Lin, Longnian and Osan, Remus and Tsien, Joe Z.},
title = {Organizing principles of real-time memory encoding: neural clique assemblies and universal neural codes.},
journal = {Trends in Neurosciences},
volume = {29},
number = {1},
pages = {48-57},
year = {2006},
month = jan,
doi = {10.1016/j.tins.2005.11.004},
}
```

```
@article{ManfieldJPMBGW:2006,
author = {Manfield, Iain W. and Jen, Chih-Hung and Pinney, John W. and Michalopoulos, Ioannis and Bradford, James R. and Gilmartin, Philip M. and Westhead, David R.},
title = {Arabidopsis Co-expression Tool (ACT): web server tools for microarray-based gene expression analysis.},
journal = {Nucleic Acids Research},
volume = {34},
number = {Web Server issue},
pages = {W504-9},
year = {2006},
month = jul,
doi = {10.1093/nar/gkl204},
}
```

Modeling of cis-elements or regulatory motifs in promoter (upstream) regions of genes is a challenging computational problem. In this work, set of regulatory motifs simultaneously present in the promoters of a set of genes is modeled as a biclique in a suitably defined bipartite graph. A biologically meaningful co-occurrence of multiple cis-elements in a gene promoter is assessed by the combined analysis of genomic and gene expression data. Greater statistical significance is associated with a set of genes that shares a common set of regulatory motifs, while simultaneously exhibiting highly correlated gene expression under given experimental conditions.

Methods

XcisClique, the system developed in this work, is a comprehensive infrastructure that associates annotated genome and gene expression data, models known cis-elements as regular expressions, identifies maximal bicliques in a bipartite gene-motif graph; and ranks bicliques based on their computed statistical significance. Significance is a function of the probability of occurrence of those motifs in a biclique (a hypergeometric distribution), and on the new sum of absolute values statistic (SAV) that uses Spearman correlations of gene expression vectors. SAV is a statistic well-suited for this purpose as described in the discussion.

Results

XcisClique identifies new motif and gene combinations that might indicate as yet unidentified involvement of sets of genes in biological functions and processes. It currently supports Arabidopsis thaliana and can be adapted to other organisms, assuming the existence of annotated genomic sequences, suitable gene expression data, and identified regulatory motifs. A subset of Xcis Clique functionalities, including the motif visualization component MotifSee, source code, and supplementary material are available at https://bioinformatics.cs.vt.edu/xcisclique/. University, Blacksburg, VA 24061, USA. apati@vt.edu

```
@article{PatiVHGM:2006,
author = {Pati, Amrita and Vasquez-Robinet, Cecilia and Heath, Lenwood S. and Grene, Ruth and Murali, T. M.},
title = {XcisClique: analysis of regulatory bicliques.},
journal = {BMC Bioinformatics},
volume = {7},
pages = {218},
year = {2006},
doi = {10.1186/1471-2105-7-218},
}
```

```
@article{VoySPSBCBL:2006,
author = {Voy, Brynn H. and Scharff, Jon A. and Perkins, Andy D. and Saxton, Arnold M. and Borate, Bhavesh and Chesler, Elissa J. and Branstetter, Lisa K. and Langston, Michael A.},
title = {Extracting gene networks for low-dose radiation using graph theoretical algorithms.},
journal = {Plos Computational Biology},
volume = {2},
number = {7},
pages = {e89},
year = {2006},
month = jul,
doi = {10.1371/journal.pcbi.0020089},
}
```

Contact

Mark.Gerstein@yale.edu SUPPLEMENTARY INFORMATION: Supplementary Materials are available at Bioinformatics online. University, PO Box 208114, New Haven, CT 06520-8285, USA.

```
@article{YuPTG:2006,
author = {Yu, Haiyuan and Paccanaro, Alberto and Trifonov, Valery and Gerstein, Mark},
title = {Predicting interactions in protein networks by completing defective cliques.},
journal = {Bioinformatics},
volume = {22},
number = {7},
pages = {823-9},
year = {2006},
month = apr,
doi = {10.1093/bioinformatics/btl014},
}
```

```
@article{ZhangG:2006,
author = {Zhang, Ziding and Grigorov, Martin G.},
title = {Similarity networks of protein binding sites.},
journal = {Proteins},
volume = {62},
number = {2},
pages = {470-8},
year = {2006},
month = feb,
doi = {10.1002/prot.20752},
}
```

```
@article{ZhangLZ:2006,
author = {Zhang, Chi and Liu, Song and Zhou, Yaoqi},
title = {Fast and accurate method for identifying high-quality protein-interaction modules by clique merging and its application to yeast.},
journal = {Journal of Proteome Research},
volume = {5},
number = {4},
pages = {801-7},
year = {2006},
month = apr,
doi = {10.1021/pr050366g},
}
```

```
@article{ZhangNZ:2006,
author = {Zhang, Shihua and Ning, Xuemei and Zhang, Xiang-Sun},
title = {Identification of functional modules in a PPI network by clique percolation clustering.},
journal = {Computational Biology and Chemistry},
volume = {30},
number = {6},
pages = {445-51},
year = {2006},
month = dec,
doi = {10.1016/j.compbiolchem.2006.10.001},
}
```

```
@article{CarpentierD:2005,
author = {Carpentier, Normand and Ducharme, Francine},
title = {Support network transformations in the first stages of the caregiver's career.},
journal = {Qualitative Health Research},
volume = {15},
number = {3},
pages = {289-311},
year = {2005},
month = mar,
doi = {10.1177/1049732304270813},
}
```

```
@article{ChenC:2005,
author = {Chen, Yu and Crippen, Gordon M.},
title = {A novel approach to structural alignment using realistic structural and environmental information.},
journal = {Protein Science},
volume = {14},
number = {12},
pages = {2935-46},
year = {2005},
month = dec,
doi = {10.1110/ps.051428205},
}
```

```
@article{ChenM:2005,
author = {Chen, Ting and Metaxas, Dimitris},
title = {A hybrid framework for 3D medical image segmentation.},
journal = {Medical Image Analysis},
volume = {9},
number = {6},
pages = {547-65},
year = {2005},
month = dec,
doi = {10.1016/j.media.2005.04.004},
}
```

```
@article{CliqueIWCTSN:2005,
author = {Clique, Blandine and Ironmonger, Alan and Whittaker, Benjamin and Colley, Jacqueline and Titchmarsh, James and Stockley, Peter and Nelson, Adam},
title = {Synthesis of a library of stereo- and regiochemically diverse aminoglycoside derivatives.},
journal = {Organic & Biomolecular Chemistry},
volume = {3},
number = {15},
pages = {2776-85},
year = {2005},
month = aug,
doi = {10.1039/b505865a},
}
```

```
@article{DerenyiPV:2005,
author = {Der{\'e}nyi, Imre and Palla, Gergely and Vicsek, Tam{\'a}s},
title = {Clique percolation in random networks},
journal = {Physical review letters},
volume = {94},
number = {16},
pages = {160202},
publisher = {APS},
year = {2005},
doi = {10.1103/PhysRevLett.94.160202},
}
```

```
@article{LinOSJZT:2005,
author = {Lin, Longnian and Osan, Remus and Shoham, Shy and Jin, Wenjun and Zuo, Wenqi and Tsien, Joe Z.},
title = {Identification of network-level coding units for real-time representation of episodic experiences in the hippocampus.},
journal = {Proceedings of the National Academy of Sciences of the United States of America},
volume = {102},
number = {17},
pages = {6125-30},
year = {2005},
month = apr,
doi = {10.1073/pnas.0408233102},
}
```

```
@article{MuhlenbeinH:2005,
author = {Muhlenbein, Heinz and Hons, Robin},
title = {The estimation of distributions and the minimum relative entropy principle.},
journal = {Evolutionary Computation},
volume = {13},
number = {1},
pages = {1-27},
year = {2005},
doi = {10.1162/1063656053583469},
}
```

```
@article{TabbTKVM:2005,
author = {Tabb, David L. and Thompson, Melissa R. and Khalsa-Moyers, Gurusahai and VerBerkmoes, Nathan C. and McDonald, W. Hayes},
title = {MS2Grouper: group assessment and synthetic replacement of duplicate proteomic tandem mass spectra.},
journal = {Journal of the American Society for Mass Spectrometry},
volume = {16},
number = {8},
pages = {1250-61},
year = {2005},
month = aug,
doi = {10.1016/j.jasms.2005.04.010},
}
```

```
@article{ArnoldBPTLK:2004,
author = {Arnold, James R. and Burdick, Keith W. and Pegg, Scott C-H and Toba, Samuel and Lamb, Michelle L. and Kuntz, Irwin D.},
title = {SitePrint: three-dimensional pharmacophore descriptors derived from protein binding sites for family based active site analysis, classification, and drug design.},
journal = {Journal of Chemical Information and Computer Sciences},
volume = {44},
number = {6},
pages = {2190-8},
year = {2004},
month = nov,
doi = {10.1021/ci049814f},
}
```

```
@article{BrakouliasJ:2004,
author = {Brakoulias, Andreas and Jackson, Richard M.},
title = {Towards a structural classification of phosphate binding sites in protein-nucleotide complexes: an automated all-against-all structural comparison using geometric matching.},
journal = {Proteins},
volume = {56},
number = {2},
pages = {250-60},
year = {2004},
month = aug,
doi = {10.1002/prot.20123},
}
```

```
@article{DejoriSTS:2004,
author = {Dejori, Mathaus and Schwaighofer, Anton and Tresp, Volker and Stetter, Martin},
title = {Mining functional modules in genetic networks with decomposable graphical models.},
journal = {Omics},
volume = {8},
number = {2},
pages = {176-88},
year = {2004},
doi = {10.1089/1536231041388375},
}
```

RNA structure motifs contained in mRNAs have been found to play important roles in regulating gene expression. However, identification of novel RNA regulatory motifs using computational methods has not been widely explored. Effective tools for predicting novel RNA regulatory motifs based on genomic sequences are needed.

Results

We present a new method for predicting common RNA secondary structure motifs in a set of functionally or evolutionarily related RNA sequences. This method is based on comparison of stems (palindromic helices) between sequences and is implemented by applying graph-theoretical approaches. It first finds all possible stable stems in each sequence and compares stems pairwise between sequences by some defined features to find stems conserved across any two sequences. Then by applying a maximum clique finding algorithm, it finds all significant stems conserved across at least k sequences. Finally, it assembles in topological order all possible compatible conserved stems shared by at least k sequences and reports a number of the best assembled stem sets as the best candidate common structure motifs. This method does not require prior structural alignment of the sequences and is able to detect pseudoknot structures. We have tested this approach on some RNA sequences with known secondary structures, in which it is capable of detecting the real structures completely or partially correctly and outperforms other existing programs for similar purposes.

Availability

The algorithm has been implemented in C++ in a program called comRNA, which is available at http://ural.wustl.edu/softwares.html 63110, USA.

```
@article{JiXS:2004,
author = {Ji, Yongmei and Xu, Xing and Stormo, Gary D.},
title = {A graph theoretical approach for predicting common RNA secondary structure motifs including pseudoknots in unaligned sequences.},
journal = {Bioinformatics},
volume = {20},
number = {10},
pages = {1591-602},
year = {2004},
month = jul,
doi = {10.1093/bioinformatics/bth131},
}
```

Graph-based clique-detection techniques are widely used for the recognition of common substructures in proteins. They permit the detection of resemblances that are independent of sequence or fold homologies and are also able to handle conformational flexibility. Their high computational complexity is often a limiting factor and prevents a detailed and fine-grained modeling of the protein structure.

Results

We present an efficient two-step method that significantly speeds up the detection of common substructures, especially when used to screen larger databases. It combines the advantages from both clique-detection and geometric hashing. The method is applied to an established approach for the comparison of protein binding-pockets, and some empirical results are presented.

Availability

Upon request from the authors. Hans-Meerwein-Strasse, 35032 Marburg, Germany.

```
@article{WeskampKHK:2004,
author = {Weskamp, Nils and Kuhn, Daniel and Hullermeier, Eyke and Klebe, Gerhard},
title = {Efficient similarity search in protein structure databases by k-clique hashing.},
journal = {Bioinformatics},
volume = {20},
number = {10},
pages = {1522-6},
year = {2004},
month = jul,
doi = {10.1093/bioinformatics/bth113},
}
```

```
@article{HattoriOGK:2003,
author = {Hattori, Masahiro and Okuno, Yasushi and Goto, Susumu and Kanehisa, Minoru},
title = {Development of a chemical structure comparison method for integrated analysis of chemical and genomic information in the metabolic pathways.},
journal = {Journal of the American Chemical Society},
volume = {125},
number = {39},
pages = {11853-65},
year = {2003},
month = oct,
doi = {10.1021/ja036030u},
}
```

```
@article{KinoshitaN:2003,
author = {Kinoshita, Kengo and Nakamura, Haruki},
title = {Identification of protein biochemical functions by similarity search using the molecular surface database eF-site.},
journal = {Protein Science},
volume = {12},
number = {8},
pages = {1589-95},
year = {2003},
month = aug,
doi = {10.1110/ps.0368703},
}
```

```
@article{RhodesWCDH:2003,
author = {Rhodes, Nicholas and Willett, Peter and Calvet, Alain and Dunbar, James B. and Humblet, Christine},
title = {CLIP: similarity searching of 3D databases using clique detection.},
journal = {Journal of Chemical Information and Computer Sciences},
volume = {43},
number = {2},
pages = {443-8},
year = {2003},
month = mar,
doi = {10.1021/ci025605o},
}
```

```
@article{WangTC:2003,
author = {Wang, Rong Long and Tang, Zheng and Cao, Qi Ping},
title = {An efficient approximation algorithm for finding a maximum clique using Hopfield network learning.},
journal = {Neural Computation},
volume = {15},
number = {7},
pages = {1605-19},
year = {2003},
month = jul,
doi = {10.1162/089976603321891828},
}
```

```
@article{ChiuPWSW:2001,
author = {Chiu, D. T and Pezzoli, E. and Wu, H. and Stroock, A. D and Whitesides, G. M.},
title = {Using three-dimensional microfluidic networks for solving computationally hard problems.},
journal = {Proceedings of the National Academy of Sciences of the United States of America},
volume = {98},
number = {6},
pages = {2961-6},
year = {2001},
month = mar,
doi = {10.1073/pnas.061014198},
}
```

**Note:**Transformation of the problem of finding all connected maximal common subgraphs into cliques. Adaptations of Bron-Kerbosch algorithm with pruning techniques to discard cliques that represent unconnected subgraphs.

```
@article{Koch:2001,
author = {Ina Koch},
title = {Enumerating all connected maximal common subgraphs in two graphs},
journal = {Theoretical Computer Science},
volume = {250},
number = {1-2},
pages = {1--30},
year = {2001},
doi = {10.1016/S0304-3975(00)00286-3},
}
```

```
@article{GardinerWA:2000,
author = {Gardiner, Eleanor J. and Willett, Peter and Artymiuk, Peter J.},
title = {Graph-theoretic techniques for macromolecular docking},
journal = {Journal of Chemical Information and Computer Sciences},
volume = {40},
number = {2},
pages = {273--279},
publisher = {ACS Publications},
year = {2000},
doi = {10.1021/ci990262o},
}
```

```
@inproceedings{PevznerS:2000,
author = {Pevzner, Pavel A. and Sze, Sing-Hoi},
title = {Combinatorial approaches to finding subtle signals in DNA sequences},
volume = {8},
booktitle = {Proceedings of the Eighth International Conference on Intelligent Systems for Molecular Biology},
pages = {269--278},
editor = {Russ Altman and Timothy L. Bailey and Philip Bourne and Michael Gribskov and Thomas Lengauer and Ilya N. Shindyalov and Lynn F. Ten Eyck and and Helge Weissig},
year = {2000},
url = {http://www.aaai.org/Library/ISMB/2000/ismb00-028.php},
}
```

```
@article{BharitkarTT:1999,
author = {Bharitkar, S. and Tsuchiya, K. and Takefuji, Y.},
title = {Microcode optimization with neural networks.},
journal = {IEEE Transactions On Neural Networks / A Publication of the IEEE Neural Networks Council},
volume = {10},
number = {3},
pages = {698-703},
year = {1999},
doi = {10.1109/72.761728},
}
```

```
@article{MillerSK:1999,
author = {Miller, M. D and Sheridan, R. P and Kearsley, S. K.},
title = {SQ: a program for rapidly producing pharmacophorically relevent molecular superpositions.},
journal = {Journal of Medicinal Chemistry},
volume = {42},
number = {9},
pages = {1505-14},
year = {1999},
month = may,
doi = {10.1021/jm9806143},
}
```

```
@article{SamudralaM:1998,
author = {Samudrala, Ram and Moult, John},
title = {A graph-theoretic algorithm for comparative modeling of protein structure1},
journal = {Journal of molecular biology},
volume = {279},
number = {1},
pages = {287--302},
publisher = {Elsevier},
year = {1998},
doi = {10.1006/jmbi.1998.1689},
}
```

```
@article{BenderL:1997,
author = {Bender, D. and Losel, F.},
title = {Protective and risk effects of peer relations and social support on antisocial behaviour in adolescents from multi-problem milieus.},
journal = {Journal of Adolescence},
volume = {20},
number = {6},
pages = {661-78},
year = {1997},
month = dec,
doi = {10.1006/jado.1997.0118},
}
```

```
@article{GardinerAW:1997,
author = {Eleanor J. Gardiner and Peter J. Artymiuk and Peter Willett},
title = {Clique-Detection Algorithms for Matching Three-Dimensional Molecular Structures},
journal = {Journal of Molecular Graphics and Modelling},
volume = {15},
number = {4},
pages = {245--253},
year = {1997},
doi = {10.1016/S1093-3263(97)00089-2},
}
```

```
@article{HussainR:1997,
author = {Hussain, I. and Reed, T. R.},
title = {A bond percolation-based model for image segmentation.},
journal = {IEEE Transactions On Image Processing},
volume = {6},
number = {12},
pages = {1698-704},
year = {1997},
doi = {10.1109/83.650123},
}
```

```
@article{KaplanOTL:1997,
author = {Kaplan, P. D and Ouyang, Q. and Thaler, D. S and Libchaber, A.},
title = {Parallel overlap assembly for the construction of computational DNA libraries.},
journal = {Journal of Theoretical Biology},
volume = {188},
number = {3},
pages = {333-41},
year = {1997},
month = oct,
doi = {10.1006/jtbi.1997.0475},
}
```

```
@article{PlaM:1997,
author = {Pla, Filiberto and Marchant, John A.},
title = {Matching feature points in image sequences through a region-based method},
journal = {Computer vision and image understanding},
volume = {66},
number = {3},
pages = {271--285},
publisher = {Elsevier},
year = {1997},
doi = {10.1006/cviu.1996.0512},
}
```

```
@article{KochLW:1996,
author = {Koch, Ina and Lengauer, Thomas and Wanke, Egon},
title = {An algorithm for finding maximal common subtopologies in a set of protein structures},
journal = {Journal of computational biology},
volume = {3},
number = {2},
pages = {289--306},
year = {1996},
doi = {10.1089/cmb.1996.3.289},
}
```

```
@article{Jagota:1995,
author = {Jagota, Arun},
title = {Approximating maximum clique with a Hopfield network.},
journal = {IEEE Transactions On Neural Networks / A Publication of the IEEE Neural Networks Council},
volume = {6},
number = {3},
pages = {724-35},
year = {1995},
doi = {10.1109/72.377977},
}
```

```
@article{GrindleyARW:1993,
author = {Grindley, Helen M. and Artymiuk, Peter J. and Rice, David W. and Willett, Peter},
title = {Identification of tertiary structure resemblance in proteins using a maximal common subgraph isomorphism algorithm},
journal = {Journal of Molecular Biology},
volume = {229},
number = {3},
pages = {707--721},
publisher = {Elsevier},
year = {1993},
doi = {10.1006/jmbi.1993.1074},
}
```

```
@article{HoraudS:1989,
author = {Horaud, Radu and Skordas, Thomas},
title = {Stereo correspondence through feature grouping and maximal cliques},
journal = {Pattern Analysis and Machine Intelligence, IEEE Transactions on},
volume = {11},
number = {11},
pages = {1168--1180},
publisher = {IEEE},
year = {1989},
doi = {10.1109/34.42855},
}
```

```
@article{ChabardesGIGMCM:1980,
author = {Chabardes, D. and Gagnan-Brunette, M. and Imbert-Teboul, M. and Gontcharevskaia, O. and Montegut, M. and Clique, A. and Morel, F.},
title = {Adenylate cyclase responsiveness to hormones in various portions of the human nephron.},
journal = {The Journal of Clinical Investigation},
volume = {65},
number = {2},
pages = {439-48},
year = {1980},
month = feb,
doi = {10.1172/JCI109687},
}
```

```
@article{AugustsonM:1970,
author = {Augustson, J. Gary and Minker, Jack},
title = {An analysis of some graph theoretical cluster techniques},
journal = {Journal of the ACM (JACM)},
volume = {17},
number = {4},
pages = {571--588},
publisher = {ACM},
year = {1970},
doi = {10.1145/321607.321608},
}
```

```
@article{HararyR:1957,
author = {Harary, Frank and Ross, Ian C.},
title = {A procedure for clique detection using the group matrix},
journal = {Sociometry},
volume = {20},
number = {3},
pages = {205--215},
publisher = {JSTOR},
year = {1957},
url = {http://www.jstor.org/stable/2785673},
}
```

```
@article{LuceP:1949,
author = {Luce, R. Duncan and Perry, Albert D.},
title = {A method of matrix analysis of group structure},
journal = {Psychometrika},
volume = {14},
number = {1},
pages = {95--116},
publisher = {Springer},
year = {1949},
doi = {10.1007/BF02289146},
}
```

### 1.4 Exact methods

#### 1.4.1 Bron-Kerbosch and variants

**Note:**Implementation of EppsteinLS:2010 and comparison with TomitaTT:2006 on several benchmarks of real, large, but very sparse graphs with low degenearcy number, or very small DIMACS instances.

```
@incollection{EppsteinS:2011,
author = {Eppstein, David and Strash, Darren},
title = {Listing All Maximal Cliques in Large Sparse Real-World Graphs},
volume = {6630},
booktitle = {Experimental Algorithms},
series = {Lecture Notes in Computer Science},
pages = {364-375},
editor = {Pardalos, Panos and Rebennack, Steffen},
publisher = {Springer Berlin / Heidelberg},
year = {2011},
doi = {10.1007/978-3-642-20662-7_31},
}
```

**Note:**Variation of BronK:1973 with nodes ordered by degeneracy \(d\), which runs in \(O(dn3^{d/3})\). The algorithm can be applied to large graphs with low degeneracy number (see EppsteinS:2011).

```
@incollection{EppsteinLS:2010,
author = {Eppstein, David and L{\"o}ffler, Marteen and Strash, Darren},
title = {Listing All Maximal Cliques in Sparse Graphs in Near-Optimal Time},
volume = {6506},
booktitle = {Algorithms and Computation},
series = {Lecture Notes in Computer Science},
pages = {403--414},
editor = {Cheong, Otfried and Chwa, Kyung-Yong and Park, Kunsoo},
publisher = {Springer Berlin / Heidelberg},
year = {2010},
doi = {10.1007/978-3-642-17517-6_36},
}
```

**Note:**Exact algorithm very popular in computational chemistry and other application domains. Variants with special pivoting rules are among the best performing exact algorithms for the problem. Being complete, it can be applied only to very small instances or to larger instances with small degeneracy number (see EppsteinS:2011).

```
@article{BronK:1973,
author = {Bron, Coen and Kerbosch, Joep},
title = {Algorithm 457: finding all cliques of an undirected graph},
journal = {Communications of ACM},
volume = {16},
number = {9},
pages = {575--577},
publisher = {ACM},
year = {1973},
month = sep,
address = {New York, NY, USA},
doi = {10.1145/362342.362367},
}
```

#### 1.4.2 Other exact methods

```
@inproceedings{LiFX:2013,
author = {Li, Chu-Min and Fang, Zhiwen and Xu, Ke},
title = {Combining MaxSAT Reasoning and Incremental Upper Bound for the Maximum Clique Problem},
booktitle = {Tools with Artificial Intelligence (ICTAI), 2013 IEEE 25th International Conference on},
pages = {939--946},
year = {2013},
month = nov,
doi = {10.1109/ICTAI.2013.143},
}
```

```
@article{McCreeshP:2013,
author = {Ciaran McCreesh and Patrick Prosser},
title = {Multi-Threading a State-of-the-Art Maximum Clique Algorithm},
journal = {Algorithms},
volume = {6},
number = {4},
pages = {618--635},
publisher = {MDPI, Basel, Switzerland},
year = {2013},
doi = {10.3390/a6040618},
}
```

```
@inproceedings{XiangGA:2013,
author = {Xiang, Jingen and Guo, Cong and Aboulnaga, Ashraf},
title = {Scalable Maximum Clique Computation Using MapReduce},
booktitle = {Proceedings of the IEEE International Conference on Data Engineering (ICDE '13)},
pages = {--},
publisher = {IEEE Computer Society},
year = {2013},
note = {To appear.},
}
```

```
@inproceedings{LiQ:2010,
author = {Li, Chu-Min and Quan, Zhe},
title = {An Efficient Branch-and-Bound Algorithm Based on MaxSAT for the Maximum Clique Problem},
booktitle = {Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2010, Atlanta, Georgia, USA, July 11-15, 2010},
editor = {Maria Fox and David Poole},
publisher = {AAAI Press},
year = {2010},
url = {http://www.aaai.org/ocs/index.php/AAAI/AAAI10/paper/view/1611},
}
```

```
@inproceedings{LiQ:2010b,
author = {Chu-Min Li and Zhe Quan},
title = {Combining Graph Structure Exploitation and Propositional Reasoning for the Maximum Clique Problem},
volume = {1},
booktitle = {22nd IEEE International Conference on Tools with Artificial Intelligence (ICTAI)},
pages = {344--351},
publisher = {IEEE Computer Society},
year = {2010},
doi = {10.1109/ICTAI.2010.57},
}
```

**Note:**Theoretical work on worst case complexity of generating all maximal cliques with a depth-first search algorithm. The exact algorithm has a pruning methods that are similar to the Bron-Kerbosh algorithm (BronK:1973), and a different, more compact, representation of the enumerated maximal cliques. The algorithm has \(O(3^{n/3})\) worst-case time complexity for enumerating all maximal cliques (which is optimal).

```
@article{TomitaTT:2006,
author = {Tomita, Etsuji and Tanaka, Akira and Takahashi, Haruhisa},
title = {The worst-case time complexity for generating all maximal cliques and computational experiments},
journal = {Theoretical Computer Science},
volume = {363},
number = {1},
pages = {28--42},
publisher = {Elsevier},
year = {2006},
doi = {10.1016/j.tcs.2006.06.015},
}
```

```
@incollection{TomitaS:2003,
author = {Tomita, Etsuji and Seki, Tomokazu},
title = {An Efficient Branch-and-Bound Algorithm for Finding a Maximum Clique},
volume = {2731},
booktitle = {Discrete Mathematics and Theoretical Computer Science},
series = {Lecture Notes in Computer Science},
pages = {278--289},
editor = {Calude, Cristian and Dinneen, Michael and Vajnovszki, Vincent},
publisher = {Springer Berlin / Heidelberg},
year = {2003},
doi = {10.1007/3-540-45066-1_22},
}
```

Additionally, we present a taxonomy of upper bounds for maximum clique. Analytical results show that our cost based filtering is in a sense as tight as most of these well-known bounds for the maximum clique problem.

Experiments demonstrate that the combination of cost based filtering and vertex coloring bounds outperforms the old approach as well as approaches that only apply either of these techniques. Furthermore, the new algorithm is competitive with other recent algorithms for maximum clique.

```
@incollection{Fahle:2002,
author = {Fahle, Torsten},
title = {Simple and Fast: Improving a Branch-And-Bound Algorithm for Maximum Clique},
volume = {2461},
booktitle = {Algorithms -- ESA 2002},
series = {Lecture Notes in Computer Science},
pages = {47--86},
editor = {M{\"o}hring, Rolf and Raman, Rajeev},
publisher = {Springer Berlin / Heidelberg},
year = {2002},
doi = {10.1007/3-540-45749-6_44},
}
```

```
@article{Ostergard:2002,
author = {{\"O}sterg{\aa}rd, Patric R.J.},
title = {A fast algorithm for the maximum clique problem},
journal = {Discrete Applied Mathematics},
volume = {120},
number = {1},
pages = {197--207},
publisher = {Elsevier},
year = {2002},
doi = {10.1016/S0166-218X(01)00290-6},
}
```

```
@inproceedings{ShinanoFIH:1998,
author = {Shinano, Yuji and Fujie, Tetsuya and Ikebe, Yoshiko and Hirabayashi, Ryuichi},
title = {Solving the maximum clique problem using PUBB},
booktitle = {Parallel Processing Symposium, 1998. IPPS/SPDP 1998. Proceedings of the First Merged International... and Symposium on Parallel and Distributed Processing 1998},
pages = {326--332},
year = {1998},
doi = {10.1109/IPPS.1998.669935},
}
```

```
@article{Wood:1997,
author = {Wood, David R.},
title = {An algorithm for finding a maximum clique in a graph},
journal = {Operations Research Letters},
volume = {21},
number = {5},
pages = {211--217},
publisher = {Elsevier},
year = {1997},
doi = {10.1016/S0167-6377(97)00054-0},
}
```

```
@article{CarraghanP:1990,
author = {Randy Carraghan and Panos M. Pardalos},
title = {An exact algorithm for the maximum clique problem},
journal = {Operations Research Letters},
volume = {9},
number = {6},
pages = {375--382},
year = {1990},
doi = {10.1016/0167-6377(90)90057-C},
}
```

```
@article{FridenHW:1990,
author = {Friden, C. and Hertz, A. and De Werra, D.},
title = {TABARIS: an exact algorithm based on Tabu Search for finding a maximum independent set in a graph},
journal = {Computers & Operations Research},
volume = {17},
number = {5},
pages = {437--445},
publisher = {Elsevier},
year = {1990},
doi = {10.1016/0305-0548(90)90048-C},
}
```

```
@article{BalasY:1986,
author = {Balas, Egon and Yu, Chang Sung},
title = {Finding a maximum clique in an arbitrary graph},
journal = {SIAM Journal on Computing},
volume = {15},
pages = {1054},
year = {1986},
doi = {10.1137/0215075},
}
```

#### 1.5 Continuous formulations

```
@article{PengZ:2012,
author = {Peng, Yuejian and Zhao, Cheng},
title = {A Motzkin-Straus Type Result for 3-Uniform Hypergraphs},
journal = {Graphs and Combinatorics},
pages = {1-14},
publisher = {Springer Japan},
year = {2012},
}
```

```
@article{PelilloT:2006,
author = {Pelillo, Marcello and Torsello, Andrea},
title = {Payoff-monotonic game dynamics and the maximum clique problem.},
journal = {Neural Computation},
volume = {18},
number = {5},
pages = {1215-58},
year = {2006},
month = may,
doi = {10.1162/089976606776241011},
}
```

```
@article{BomzeBPR:2002,
author = {Immanuel M. Bomze and Marco Budinich and Marcello Pelillo and Claudio Rossi},
title = {Annealed replication: a new heuristic for the maximum clique problem},
journal = {Discrete Applied Mathematics},
volume = {121},
number = {1-3},
pages = {27--49},
publisher = {Elsevier},
year = {2002},
doi = {10.1016/S0166-218X(01)00233-5},
}
```

```
@article{BurerMZ:2002,
author = {Burer, Samuel and Monteiro, Renato D.C. and Zhang, Yin},
title = {Maximum stable set formulations and heuristics based on continuous optimization},
journal = {Mathematical Programming},
volume = {94},
number = {1},
pages = {137--166},
publisher = {Springer},
year = {2002},
doi = {10.1007/s10107-002-0356-4},
}
```

```
@incollection{BomzePG:1997,
author = {Bomze, Immanuel M. and Pelillo, Marcello and Giacomini, Robert},
title = {Evolutionary approach to the maximum clique problem: Empirical evidence on a larger scale},
volume = {18},
booktitle = {Developments in global optimization},
pages = {95--108},
editor = {Bomze, Immanuel M. and Csendes, Tibor and Horst, Reiner and Pardalos, Panos M.},
publisher = {Dordrecht, The Netherlands: Kluwer},
year = {1997},
}
```

```
@article{GibbonsJPR:1997,
author = {Gibbons, Luana E. and Hearn, Donald W. and Pardalos, Panos M. and Ramana, Motakuri V.},
title = {Continuous Characterizations of the Maximum Clique Problem},
journal = {Mathematics of Operations Research},
volume = {22},
number = {3},
pages = {pp. 754--768},
publisher = {INFORMS},
year = {1997},
url = {http://www.jstor.org/stable/3690403},
}
```

```
@article{GibbonsJP:1996,
author = {Gibbons, Luana E. and Hearn, Donald W. and Pardalos, Panos M.},
title = {A continuous based heuristic for the maximum clique problem},
journal = {Cliques Coloring and Satisfiability Second DIMACS Implementation Challenge},
volume = {26},
series = {DIMACS Series},
pages = {103--124},
publisher = {American Mathematical Society},
year = {1996},
}
```

```
@article{Pelillo:1995,
author = {Pelillo, Marcello},
title = {Relaxation labeling networks for the maximum clique problem},
journal = {Journal of Artificial Neural Networks},
volume = {2},
number = {4},
pages = {313--328},
year = {1995},
doi = {10.1049/cp:19950548},
}
```

```
@article{PardalosP:1990,
author = {Pardalos, Panos M. and Phillips, Andrew T.},
title = {A global optimization approach for solving the maximum clique problem},
journal = {International Journal of Computer Mathematics},
volume = {33},
number = {3-4},
pages = {209--216},
publisher = {Taylor & Francis},
year = {1990},
doi = {10.1080/00207169008803851},
}
```

### 1.6 Instances

#### 1.6.1DIMACS

We observe that the most common methods of generating graphs with known maximum independent sets are subject to attack using simple techniques that are regularly successful on graphs of practical size. We present an improved random graph generation system, DELTA, which increases the range of maximum independent sets that can be hidden from these techniques.

```
@article{BrockingtonC:1996,
author = {Brockington, Mark and Culberson, Joseph C.},
title = {Camouflaging Independent Sets in Quasi-Random Graphs},
journal = {Cliques Coloring and Satisfiability Second DIMACS Implementation Challenge},
volume = {26},
series = {DIMACS Series},
pages = {75--88},
publisher = {American Mathematical Society},
year = {1996},
}
```

```
@article{LagariasS:1992,
author = {Lagarias, Jeffrey C. and Shor, Peter W.},
title = {Keller's Cube-Tiling Conjecture Is False in High Dimensions},
journal = {BAMS: Bulletin of the American Mathematical Society},
volume = {27},
number = {2},
pages = {279--283},
year = {1992},
doi = {10.1090/S0273-0979-1992-00318-X},
}
```

```
@article{JohnsonAMS:1991,
author = {Johnson, David S. and Aragon, Cecilia R. and McGeoch, Lyle A. and Schevon, Catherine},
title = {Optimization by simulated annealing: an experimental evaluation; part {II}, graph coloring and number partitioning},
journal = {Operations Research},
volume = {39},
number = {3},
pages = {378--406},
publisher = {INFORMS},
year = {1991},
month = may,
address = {Institute for Operations Research and the Management Sciences (INFORMS), Linthicum, Maryland, USA},
doi = {10.1287/opre.39.3.378},
}
```

```
@article{CorradiS:1990,
author = {Corr{\'a}di, K. and Szab{\'o}, S.},
title = {A combinatorial approach for Keller's conjecture},
journal = {Periodica Mathematica Hungarica},
volume = {21},
number = {2},
pages = {95-100},
publisher = {Akad{\'e}miai Kiad{\'o}, co-published with Springer Science+Business Media B.V., Formerly Kluwer Academic Publishers B.V.},
year = {1990},
doi = {10.1007/BF01946848},
}
```

## 2 Generalisations

### 2.1 Quasi-Cliques

#### 2.1.1 Stochastic Local Search algorithms

```
@article{BandyopadhyayB:2009,
author = {Bandyopadhyay, Sanghamitra and Bhattacharyya, Malay},
title = {A Neuro-GA approach for the maximum fuzzy clique problem},
volume = {5506},
booktitle = {Advances in Neuro-Information Processing},
series = {Lecture Notes in Computer Science},
pages = {605-612},
editor = {K{\"o}ppen, Mario and Kasabov, Nikola and Coghill, George},
publisher = {Springer Berlin / Heidelberg},
year = {2009},
doi = {10.1007/978-3-642-02490-0_74},
}
```

**Note:**New unifying formulation of quasi-cliques and adaptation of a reactive tabu search (BattitiM:2010) and a dynamic local search (PullanH:2006) for the problem.

```
@incollection{BrunatoHB:2008,
author = {Brunato, Mauro and Hoos, Holger H. and Battiti, Roberto},
title = {On Effectively Finding Maximal Quasi-cliques in Graphs},
booktitle = {Learning and Intelligent Optimization},
series = {Lecture Notes in Computer Science},
pages = {41--55},
editor = {Maniezzo, Vittorio and Battiti, Roberto and Watson, Jean-Paul},
publisher = {Springer-Verlag},
year = {2008},
address = {Berlin, Heidelberg},
doi = {10.1007/978-3-540-92695-5_4},
}
```

#### 2.1.2 Applications

```
@article{VaroquauxGPT:2012,
author = {Ga{\"e}l Varoquaux and Alexandre Gramfort and Jean-Baptiste Poline and Bertrand Thirion},
title = {Markov models for fMRI correlation structure: Is brain functional connectivity small world, or decomposable into networks?},
journal = {Journal of Physiology-Paris},
year = {2012},
note = {In press.},
doi = {10.1016/j.jphysparis.2012.01.001},
}
```

### 2.2 Weighted Maximum Clique

#### 2.2.1 Surveys / Theory

```
@article{BrandstadtG:2012,
author = {Brandst{\"a}dt, Andreas and Giakoumakis, Vassilis},
title = {Maximum Weight Independent Sets in hole- and co-chair-free graphs},
journal = {Information Processing Letters},
volume = {112},
number = {3},
pages = {67-71},
year = {2012},
doi = {10.1016/j.ipl.2011.09.015},
}
```

```
@article{Martins:2012,
author = {Martins, Pedro},
title = {Cliques with maximum/minimum edge neighborhood and neighborhood density},
journal = {Computers and Operations Research},
volume = {39},
number = {3},
pages = {594-608},
year = {2012},
doi = {10.1016/j.cor.2011.04.016},
}
```

```
@article{TrotignonV:2012,
author = {Trotignon, Nicolas and Vu{\vs}kovi{\'c}, Kristina},
title = {Combinatorial optimization with 2-joins},
journal = {Journal of Combinatorial Theory. Series B},
volume = {102},
number = {1},
pages = {153-185},
year = {2012},
doi = {10.1016/j.jctb.2011.06.002},
}
```

#### 2.2.2 Stochastic Local Search algorithms

```
@article{WuHG:2012,
author = {Wu, Qinghua and Hao, Jin-Kao and Glover, Fred},
title = {Multi-neighborhood tabu search for the maximum weight clique problem},
journal = {Annals of Operations Research},
volume = {196},
number = {1},
pages = {611-634},
publisher = {Springer Netherlands},
year = {2012},
doi = {10.1007/s10479-012-1124-3},
}
```

```
@article{Pullan:2007,
author = {Pullan, Wayne},
title = {Approximating the maximum vertex/edge weighted clique using local search},
journal = {Journal of Heuristics},
volume = {14},
number = {2},
pages = {117--134},
year = {2007},
doi = {10.1007/s10732-007-9026-2},
}
```

#### 2.2.3 Applications

```
@article{DelormeDK:2012,
author = {Delorme, Xavier and Dolgui, Alexandre and Kovalyov, Mikhail Y.},
title = {Combinatorial design of a minimum cost transfer line},
journal = {Omega},
volume = {40},
number = {1},
pages = {31-41},
year = {2012},
doi = {10.1016/j.omega.2011.03.004},
}
```

**Note:**Novel supervised clustering technique based on weighted maximum cliques, for collectively predicting all the residues belonging to the same protein functional site.

```
@inproceedings{MasciaCBP:2010,
author = {Mascia, Franco and Cilia, Elisa and Brunato, Mauro and Passerini, Andrea},
title = {Predicting Structural and Functional Sites in Proteins by Searching for Maximum-weight Cliques},
booktitle = {Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2010, Atlanta, Georgia, USA, July 11-15, 2010},
editor = {Maria Fox and David Poole},
publisher = {AAAI Press},
year = {2010},
url = {http://www.aaai.org/ocs/index.php/AAAI/AAAI10/paper/view/1833},
}
```

```
@article{PavanP:2007,
author = {Pavan, Massimiliano and Pelillo, Marcello},
title = {Dominant sets and pairwise clustering},
journal = {Pattern Analysis and Machine Intelligence, IEEE Transactions on},
volume = {29},
number = {1},
pages = {167--172},
publisher = {IEEE},
year = {2007},
doi = {10.1109/TPAMI.2007.250608},
}
```

```
@inproceedings{WangZZ:2007,
author = {Wang, Shidong and Zheng, Li and Zhang, Zhihai},
title = {Study on plan of track lines in marshalling station},
booktitle = {IEEM 2007: 2007 IEEE International Conference on Industrial Engineering and Engineering Management},
pages = {852-856},
year = {2007},
doi = {10.1109/IEEM.2007.4419311},
}
```

#### 2.2.4 Exact methods

```
@article{BalasX:1991,
author = {Balas, Egon and Xue, J.},
title = {Minimum weighted coloring of triangulated graphs, with application to maximum weight vertex packing and clique finding in arbitrary graphs},
journal = {SIAM Journal on Computing},
volume = {20},
pages = {209},
year = {1991},
doi = {10.1137/0220012},
}
```

#### 2.2.5 Continuous formulations

```
@article{PavanP:2007,
author = {Pavan, Massimiliano and Pelillo, Marcello},
title = {Dominant sets and pairwise clustering},
journal = {Pattern Analysis and Machine Intelligence, IEEE Transactions on},
volume = {29},
number = {1},
pages = {167--172},
publisher = {IEEE},
year = {2007},
doi = {10.1109/TPAMI.2007.250608},
}
```

Computational experiments indicate that the algorithm is exact on small graphs and very efficient on the DIMACS benchmark graphs and various random maximum weight clique problem instances.

```
@article{Busygin:2006,
author = {Busygin, Stanislav},
title = {A new trust region technique for the maximum weight clique problem},
journal = {Discrete Applied Mathematics},
volume = {154},
number = {15},
pages = {2080--2096},
publisher = {Elsevier},
year = {2006},
doi = {10.1016/j.dam.2005.04.010},
}
```

```
@article{MassaroPB:2002,
author = {Massaro, Alessio and Pelillo, Marcello and Bomze, Immanuel M.},
title = {A complementary pivoting approach to the maximum weight clique problem},
journal = {SIAM Journal on Optimization},
volume = {12},
number = {4},
pages = {928--948},
publisher = {Philadelphia, Pa.: The Society, c1991-},
year = {2002},
doi = {10.1137/S1052623400381413},
}
```

```
@article{BomzePS:2000,
author = {Bomze, Immanuel M. and Pelillo, Marcello and Stix, Volker},
title = {Approximating the maximum weight clique using replicator dynamics.},
journal = {IEEE Transactions On Neural Networks / A Publication of the IEEE Neural Networks Council},
volume = {11},
number = {6},
pages = {1228-41},
year = {2000},
doi = {10.1109/72.883403},
}
```

Note:Variation of BronK:1973 with nodes ordered by degeneracy \(d\), which runs in \(O(dn3^{d/3})\). The algorithm can be applied to large graphs with low degeneracy number (see EppsteinS:2011).