"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
13 August 2020
The public is invited to a moderated Zoom meeting:
Topic: MSc thesis proposal of Ivan Cedric H. Macababayao
Proposal title: Normal Forms for Spiking Neural P Systems and Some of Its
Time: Aug 25, 2020 01:00 PM Singapore
Join Zoom Meeting
Meeting ID: 933 1297 5613
29 July 2020
On 3 August 2020 (Monday) Ren Tristan de la Cruz will provide an oral presentation with the following details:
Topic: Oral PhD Specialisation exam: CS397 (Special topics in Membrane Computing)
After a quick background to membrane computing, some ``classical'' results will be provided on the computing power and efficiency of some P systems. A few of the main directions for research in membrane computing concludes the presentation.
Time: Aug 3, 2020 13:00h Philippine time
Join Zoom Meeting
Meeting ID: 969 2524 4581
The public is invited to join the ``zoominar'', subject to moderation.
Presentation slides here.
28 July 2020
ACLab is pleased to announce that Jhoirene Clemente has completed all her requirements for the degree of Doctor of Philosophy in Computer Science. Jhoirene will receive a doctorate from the College of Engineering, University of the Philippines Diliman (Department of Computer Science).
"Ten years of Computer Science Theory at UP Diliman"
presented by Henry N. Adorna during Theory Days 2017.
Selected and Recent Publications
- 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]
- 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]
- 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]
- 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]
- 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]
Dissertation title: Additional Information in Computation: Reoptimization and Advice for Some Combinatorial Problems
23 June 2020
ACLab is pleased to announce that Geoffrey Solano has successfully 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).
Dissertation title: Clique Finding Approaches for Discovering Approximate Gene
11 Jun 2020
Oral Defense of the
GEOFFREY ASERIOS SOLANO
Clique Finding Approaches for
Discovering Approximate Gene Clusters
For the degree of
DOCTOR OF PHILOSOPHY
23 JUNE 2020, 10:00 (Manila Time)
Meeting ID: 511 014 9016
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.
More information here: https://www.up.edu.ph/the-philippine-genome-center-stockpiling-for-covid-19/
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.