The minimum path cover problem asks us to find a minimum-cardinality set of paths that cover all the nodes of a directed acyclic graph (DAG). We study the case when the size k of a minimum path cover is small, that is, when the DAG has a small width. This case is motivated by applications in pan-genomics, where the genomic variation of a population is expressed as a DAG. We observe that classical alignment algorithms exploiting sparse dynamic programming can be extended to the sequence-against-DAG case by mimicking the algorithm for sequences on each path of a minimum path cover and handling an evaluation order anomaly with reachability queries.
Namely, we introduce a general framework for DAG-extensions of sparse dynamic programming. This framework produces algorithms that are slower than their counterparts on sequences only by a factor k. We illustrate this on two classical problems extended to DAGs: longest increasing subsequence and longest common subsequence. For the former, we obtain an algorithm with running time O(k|E|log |V|). This matches the optimal solution to the classical problem variant when the input sequence is modeled as a path. We obtain an analogous result for the longest common subsequence problem. We then apply this technique to the co-linear chaining problem, which is a generalization of the above two problems. The algorithm for this problem turns out to be more involved, needing further ingredients, such as an FM-index tailored for large alphabets and a two-dimensional range search tree modified to support range maximum queries. We also study a general sequence-to-DAG alignment formulation that allows affine gap costs in the sequence.
The main ingredient of the proposed framework is a new algorithm for finding a minimum path cover of a DAG (V,E) in O(k|E|log |V|) time, improving all known time-bounds when k is small and the DAG is not too dense. In addition to boosting the sparse dynamic programming framework, an immediate consequence of this new minimum path cover algorithm is an improved space/time tradeoff for reachability queries in arbitrary directed graphs.2019-02-06
The panel will discuss and answer questions the landscape of employment and education pathways in data science and analytics. The panel will also talk about the current discussions within ACM and the role(s) the information technology discipline should have in the field. Finally the panel will solicit feedback from the audience on current work and desired next steps in order to address the global education and workforce needs.2017-09-27
This document, "MSIS 2016: Global Competency Model for Graduate Degree Programs in Information Systems", is the latest in the series of reports that provides guidance for degree programs in the Information Systems (IS) academic discipline. The first of these reports (Ashenhurst, 1972) was published in the early 1970s, and the work has continued ever since both at the undergraduate and master's levels. The Association for Computing Machinery (ACM) has sponsored the reports from the beginning. Since the Association for Information Systems (AIS) was established in the mid-1990s, the two organizations have collaborated on the production of curriculum recommendations for the IS discipline. At the undergraduate level, both the Association for Information Technology Professionals (AITP) (formerly DPMA) and the International Federation for Information Processing (IFIP) have also made significant contributions to the curriculum recommendations.2017-05-23