"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

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]