"When you want to build a ship, then do not drum the men together in order to procure wood, to give instructions or to distribute the work, but teach them longing for the wide endless sea." - A. de Saint-Exupery


This is the official web site of the Algorithms and Complexity Laboratory (ACLab) of the Department of Computer Science at the University of the Philippines Diliman. ACLab was founded in 2007 by Henry N. Adorna, Professor of Computer Science.

ACLab regular members, (under)graduate students, and collaborators conduct investigations on a diverse range of topics, all anchored on a theoretical computer science perspective. Current active research areas include formal models, natural computing, algorithmics for hard problems, bioinformatics, and data analysis and visualization.

Recent News and Announcements

23 June 2020

ACLab is pleased to announce that Geoffrey Solano has successfully defended his dissertation for the degree of Doctor of Philosophy in Computer Science. Geoffrey will be receiving a doctorate from the College of Engineering, University of the Philippines Diliman (Department of Computer Science).


11 Jun 2020

Oral Defense of the
Dissertation of


Clique Finding Approaches for
Discovering Approximate Gene Clusters

For the degree of



23 JUNE 2020, 10:00 (Manila Time)
Meeting ID: 511 014 9016
Password: 05721723

Panel Members
Dr. Jaime DL. Caro, Adviser
Dr. Alex Gonzaga, Panel Chairman
Dr. Henry N. Adorna, Reader
Dr. Polly W. Sy, Panel Member
Dr.Wilson Tan, Panel Member


A gene cluster is a group of two or more genes found within an organism’s DNA that encode similar polypeptides or proteins. Genes belonging to a cluster may share functional dependencies and may be involved in the expression of a specific trait. Identifying these clusters is essential in establishing relationships between organisms as well as in the discovery of drugs and disease treatments. The biological problem of identifying associations among genes across genomes can be formalized as searching for cliques on undirected weighted graphs. This dissertation explores algo- rithmic approaches to two of these clique-finding optimization problems, particularly the Minimum Weight t-partite Clique Problem (MWtCP) and the Minimum Edge- Weighted Clique Problem (Min-EWCP). It was shown that MWtCP is NP- Hard as well as APX-Hard. Approximation algorithms were then presented on the two problems as well as their constant factor approximation ratios in the metric case as well as the ultrametric case of inputs. An additional performance guarantee is shown when a variable σ is provided for varying the metricity property on inputs. Finally, experimental results were presented where algorithmic solutions to the two problems were applied to the problem of discovering approximate gene clusters. A data set composed of 1406 putative orthologous genes of the genomes E. coli str. K-12 and B. subtilis. Another data set composed of 25 gene clusters corresponding to 33 different biological pathways of the same set of species was used to benchmark the results.

24 Mar 2020

The Philippine Genome Center: Stockpiling for COVID-19

March 10, 2020 | Written by Khalil Ismael Michael G. Quilinguing

``On February 13, 2020, President Rodrigo R. Duterte addressed the nation on television as fears over the spread of the Novel Coronavirus 2019 or Corona Virus Disease 2019 (COVID-19) gripped many. Speaking in a video message recorded at the Malacañang Palace, he assured the public that his administration was taking all the necessary measures to limit the spread of the disease. “I call on our people to remain calm, vigilant, responsible. And I also ask [for] your trust and cooperation, support as we face the challenge,” he said.

Earlier during the day, the Manila HealthTek Inc. posted on its official Facebook page a photo of the COVID-19 test kit developed by experts from the Philippine Genome Center and the National Institutes of Health of the University of the Philippines Manila.

... After a specimen is sequenced, it is then forwarded to another unit of the PGC called the Core Facility for Bioinformatics. The unit, according to its supervisor, Dr. Jan Michael Yap, will subject the sequenced samples to a verification process to establish its proper attributes.

6 Feb 2020

From ABS CBN news:

``Filipino scientists offer help in detecting 2019-nCoV in PH

Davinci Maru, ABS-CBN News
Posted at Jan 30 2020 08:19 PM

MANILA - A research facility in the University of the Philippines (UP) said Thursday it would help health authorities confirm cases of the 2019 novel coronavirus (2019-nCoV) in the country.

"The Philippines has the tools and cutting-edge equipment, trained DNA sequencing staff, and scientists to help validate the presence of 2019-nCoV in the country by sequencing the whole viral genome from samples collected from patients," Dr. Cynthia Saloma, executive director of the Philippine Genome Center (PGC), said in a statement.

The facility will assist the Department of Health (DOH) and Research Institute for Tropical Medicine (RITM) on diagnosing possible cases of the illness, which has killed at least 170 in China as of Thursday. Some 81,000 others globally are under observation for possible infection.

China virus death toll rises to 170, more than 1,700 new cases
Using a Next Generation DNA/RNA Sequencing (NGS) equipment, the Philippines will no longer have to send samples of suspected 2019-nCoV cases abroad, said Dr. Jan Michael Yap, head of PGC's core facility for bioinformatics.

"We can do it here," he told ABS-CBN News in a phone interview, adding the results could be released after 3 days.

The equipment, Yap said, is a fast, accurate way of identifying the genetic information of viruses.

The Philippine government already confirmed the country's first case, a 38-year-old woman from Wuhan, China who arrived in Manila on January 21. 

Philippines confirms first case of new coronavirus
The woman arrived in Manila via Hong Kong on Jan. 21. She is now in an undisclosed government hospital.

The Philippines had been sending specimen samples to the Victorian Infectious Disease Reference in Australia to confirm if the patient is infected with the new coronavirus.

"Before wala pa kasing existing data on what the 2019-nCov looks like," Yap said.

The facility is also in talks with the DOH of creating confirmatory test kits to swiftly identify patients carrying the strain, he added.

"We are now preparing our materials, tools and equipment. We are ready to assist at any moment," Yap said.

The World Health Organization (WHO) had said coronaviruses were a large family of viruses ranging from the common cold to more severe diseases such as the Middle East Respiratory Syndrome (MERS-CoV) and Severe Acute Respiratory Syndrome (SARS).

Fever, cough and breathing difficulties are among its symptoms, the UN health agency added.


"Ten years of Computer Science Theory at UP Diliman" 
presented by Henry N. Adorna during Theory Days 2017.

Selected and Recent Publications

  1. Asuncion, X.E., Sampaco III, A-R., Adorna, H., Magadia, J., Boñgolan, V. P.,  and Lluisma, A., Predicting the Molecular Targets of Conopeptides by using Principal Component Analysis and Multiclass Logistic Regression. Philippine Journal of Science 148 (S1): 237-245, Special Issue on Genomics (2019)  http://philjournalsci.dost.gov.ph/images/pdf/special_issue/148_S1/predicting_molecular_targets_.pdf  [jour/ISI/SCI]

  2. Jimenez, Z.B., Cabarle, F.G.C., de la Cruz, R.T.A, Buño, K.C., Adorna, H.N., Hernandez, N.H.S., Zeng, X. Matrix representation and simulation algorithm of spiking neural P systems with structural plasticity. Journal of Membrane Computing (2019). Springer https://doi.org/10.1007/s41965-019-00020-3 [jour]

  3. J. B. Clemente, P, L. Fernandez Jr., R.A.B. Juayong, J.A. Malinao, I.D. Ordanel, and H.N. Adorna.  Reoptimization of the Consensus Pattern Problem under Pattern Length Modification. Philippine Journal of Science 148 (3): 537-551, September 2019  [jour/ISI/SCI]

  4. R.T.A. de la Cruz, F.G.C. Cabarle, & H.N. Adorna.  Generating context-free languages using spiking neural P systems with structural plasticity. Journal of Membrane Computing (2019). Springer https://doi.org/10.1007/s41965-019-00021-2 [jour]

  5. F.G.C. Cabarle, R.T.A. de la Cruz, D.P. Cailipan, D. Zhang, X. Liu, X. Zeng. On Solutions and Representations Of Spiking Neural P Systems With Rules On Synapses. (in press) Information Sciences https://doi.org/10.1016/j.ins.2019.05.070 2019 [jour/ISI/SCI]