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

Welcome!

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

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 Variants

Time: Aug 25, 2020 01:00 PM Singapore

Join Zoom Meeting

https://up-edu.zoom.us/j/93312975613

Meeting ID: 933 1297 5613

Passcode: 2f7bj45V

PHD Specialization Exam

Special Topics in Membrane Computing

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

https://up-edu.zoom.us/j/96925244581

Meeting ID: 969 2524 4581

Passcode: Q75CG72v

The public is invited to join the ``zoominar'', subject to moderation.

Presentation slides here.

Congratulations!

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

11 Jun 2020

Oral Defense of the

Dissertation of

GEOFFREY ASERIOS SOLANO

entitled

Clique Finding Approaches for Discovering Approximate Gene Clusters

For the degree of

DOCTOR OF PHILOSOPHY

(COMPUTER SCIENCE)

on

23 JUNE 2020, 10:00 (Manila Time)

https://up-edu.zoom.us/j/5110149016?pwd=d2RTbFY2T0Y0YUswSnFrai9pVUZOdz09

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

ABSTRACT

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

24 Mar 2020

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

6 Feb 2020

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


Congratulations!

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).


PHD DISSERTATION DEFENSE

Additional Information in Computation: Reoptimization and Advice for Some Combinatorial Problems

30 Sept 2019

Oral Defense of the Dissertation of

JHOIRENE BARASI CLEMENTE

entitled

Additional Information in Computation: Reoptimization and Advice for Some Combinatorial Problems


For the degree of

DOCTOR OF PHILOSOPHY

(COMPUTER SCIENCE)

on

30 SEPT 2020, 4:00 PM - 7:00 PM (Manila Time)

ERDT ROOM

UP ALUMNI ENGINEERS CENTENNIAL HALL

UP DILIMAN, QUEZON CITY

________________

Panel Members

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

ABSTRACT

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.

Ten years of Computer Science Theory at UP Diliman

Presented by Henry N. Adorna during Theory Days 2017.