ALGORITHMS & COMPLEXITY LAB
"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 in Bioinformatics
Data Analytics and Visualization
Selected and Recent Publications
Lovely Joy Casauay, Ivan Cedric H. Macababayao, Francis George C. Cabarle, Ren Tristan A. de la Cruz, Henry N. Adorna, Xiangxiang Zeng, Miguel Ángel Martı́nez-del-Amor, ``A Framework for Evolving Spiking Neural P Systems''. (in press) International Journal of Unconventional Computing, Old City Publishing (2020) [jour/isi/sci]
Prometheus Peter L. Lazo , Francis George C. Cabarle, Henry N. Adorna, Jan Michael C. Yap: A return to stochasticity and probability in spiking neural p systems. In: Pre-proc. International Conference on Membrane Computing (ICMC2020). Vienna, Austria and Ulaanbaatar, Mongolia (Sep- tember 2020) [cf]
Kelvin C. Buño, Francis George C. Cabarle, Jherico Gabriel Q. Torres, ``Spiking Neural dP Systems: Balance and Homogeneity''. Philippine Computing Journal. (Special Issue on P systems) Volume 14, Number 2, ISSN 1908-1995, pp. 1 to 10. [jour]
Prometheus Peter L. Lazo, Francis George C. Cabarle, Jan Michael C. Yap, ``A Short Survey of Stochastic Computing Models''. Philippine Computing Journal. (Special Issue on P systems) Volume 14, Number 2, ISSN 1908-1995, pp. 31 to 38. [jour]
Gyenn Neil Ibo, Henry N. Adorna, ``Periodic Dynamical Behavior in SN P Systems and the Presence of Cycles in their Graph Representation''. Philippine Computing Journal. (Special Issue on P systems) Volume 14, Number 2, ISSN 1908-1995, pp. 39 to 43. [jour]
Jules Gerard E. Juico, Jerico L. Silapan, Francis George C. Cabarle Ivan Cedric Macababayao, Ren Tristan De la Cruz, ``Evolving Spiking Neural P Systems with Polarization''. Philippine Computing Journal. (Special Issue on P systems) Volume 14, Number 2, ISSN 1908-1995, pp. 11 to 20. [jour]
Recent News and Announcements
MS THESIS PROPOSAL
Normal Forms for Spiking Neural P Systems and Some of Its Variants
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 Variants
Time: Aug 25, 2020 01:00 PM Singapore
https://up-edu.zoom.us/j/93312975613
Passcode: 2f7bj45V
PHD Specialization Exam
Special Topics in Membrane Computing
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
Passcode: Q75CG72v
The public is invited to join the ``zoominar'', subject to moderation.
Presentation slides here.
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).
PHD DISSERTATION DEFENSE
Clique Finding Approaches for Discovering Approximate Gene Clusters
Oral Defense of the
Dissertation of
GEOFFREY ASERIOS SOLANO
entitled
For the degree of
(COMPUTER SCIENCE)
23 JUNE 2020, 10:00 (Manila Time)
https://up-edu.zoom.us/j/5110149016?pwd=d2RTbFY2T0Y0YUswSnFrai9pVUZOdz09
Password: 05721723
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.
NEWS: 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/
Image Source: Philippine Genome Center
NEWS: ABS-CBN
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.
source: https://news.abs-cbn.com/news/01/30/20/filipino-scientists-offer-help-in-detecting-2019-ncov-in-ph
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).
Additional Information in Computation: Reoptimization and Advice for Some Combinatorial Problems
Oral Defense of the Dissertation of
JHOIRENE BARASI CLEMENTE
30 SEPT 2020, 4:00 PM - 7:00 PM (Manila Time)
ERDT ROOM
UP ALUMNI ENGINEERS CENTENNIAL HALL
UP DILIMAN, QUEZON CITY
Dr. Henry N. Adorna, Adviser
Dr. Jaime DL. Caro, Panel Chairman
Dr. Proceso Fernadez, Reader
Dr. Eugen Rex Jalao, Panel Member
Dr. Prospero Naval, Panel Member
In the last few decades, technological advancements in computing have proliferated. These advancements allow faster data processing and storage on a very large scale. Information is now cheaper than ever. In this study, we investigate how information is beneficial to computation in the context of reoptimization and advice. Reoptimization is a combinatorial setting applied to NP-hard optimization ( NPO) problems and advice is a piece of information provided by an oracle to an online algorithm to compensate for not knowing the whole input instance.
In reoptimization, an optimal solution to a locally modified version of the problem is given in advanced. We investigate how reoptimization can be beneficial in solving the consensus pattern problem (CPP). We show that for the variants reoptsk, reoptpk, and reoptmk, additional information does not help in reducing the hardness of the problem. We then show that one can use the given optimal solution to provide an approximate solution for the new input instances of these variants and we identify the conditions in which it is beneficial to use this information as compared to solving the problem from scratch. We also show that by using the additional information in reoptimization, we can improve the running time of the existing polynomial-time approximation scheme (PTAS) for CPP while maintaining the solution quality guarantee. Computation is reduced by ltn ((t-r) choose r) and $ t(n-(l+k)+1){t(l+2k) \choose r}$ steps for reoptsk and reoptpk, respectively.
In the context of advice, we investigate the ONLINE-SEARCH (OS) problem and its generalization, the ONLINE K-SEARCH (OkS). We show the minimum amount of advice necessary to achieve optimality of any online algorithm. We show upper bound and lower bound limits of any algorithm achieving certain competitive ratios given less advice. We show that in the case of OS and OkS, online algorithm with advice overpowers the best possible deterministic and randomized online algorithms in terms of competitiveness.
EVENT: ThEORY DAYS 2017
Ten years of Computer Science Theory at UP Diliman
Presented by Henry N. Adorna during Theory Days 2017.