QAPgrid: a two level QAP-based approach for large-scale data analysis and visualization.
BACKGROUND
The visualization of large volumes of data is a computationally challenging task that often promises rewarding new insights. There is great potential in the application of new algorithms and models from combinatorial optimisation. Datasets often contain "hidden regularities" and a combined identification and visualization method should reveal these structures and present them in a way that helps analysis. While several methodologies exist, including those that use non-linear optimization algorithms, severe limitations exist even when working with only a few hundred objects.


RESULTS
We present a new data visualization approach (QAPgrid) that reveals patterns of similarities and differences in large datasets of objects for which a similarity measure can be computed. Objects are assigned to positions on an underlying square grid in a two-dimensional space. We use the Quadratic Assignment Problem (QAP) as a mathematical model to provide an objective function for assignment of objects to positions on the grid. We employ a Memetic Algorithm (a powerful metaheuristic) to tackle the large instances of this NP-hard combinatorial optimization problem, and we show its performance on the visualization of real data sets.


CONCLUSIONS
Overall, the results show that QAPgrid algorithm is able to produce a layout that represents the relationships between objects in the data set. Furthermore, it also represents the relationships between clusters that are feed into the algorithm. We apply the QAPgrid on the 84 Indo-European languages instance, producing a near-optimal layout. Next, we produce a layout of 470 world universities with an observed high degree of correlation with the score used by the Academic Ranking of World Universities compiled in the The Shanghai Jiao Tong University Academic Ranking of World Universities without the need of an ad hoc weighting of attributes. Finally, our Gene Ontology-based study on Saccharomyces cerevisiae fully demonstrates the scalability and precision of our method as a novel alternative tool for functional genomics.
Departamento de Ingeniería Informática, Universidad de Santiago de Chile, Santiago, Chile.
Mario
M
Inostroza-Ponta
Regina
R
Berretta
Pablo
P
Moscato
D000465:Algorithms; D016000:Cluster Analysis; D003196:Computer Graphics; D016208:Databases, Factual; D023281:Genomics / Q000379:methods; D008722:Methods; D008962:Models, Theoretical; D012441:Saccharomyces cerevisiae / Q000235:genetics
Radiother Oncol. 2009 Mar;90(3):400-7
18952309
Bioinformatics. 2006 Jun 1;22(11):1383-90
16533819
Genome Res. 2003 Nov;13(11):2498-504
14597658
Proc Natl Acad Sci U S A. 1998 Dec 8;95(25):14863-8
9843981
Bioinformatics. 2005 May 1;21(9):2036-42
15677705
IEEE Trans Neural Netw. 1995;6(5):1185-200
18263407
Biosystems. 2007 Mar;88(1-2):56-75
16870322