Gowtham Atluri
University of Cincinnati

Large volumes of spatio-temporal data are increasingly collected and studied in diverse domains including, climate science, neuroscience, epidemiology, transportation, and Earth sciences. Relationships that exist in spatio-temporal data are known to capture interesting ’teleconnections’ in climate science and ‘functional connectivity’ in neuroimaging data. Spatio-temporal data from which these relationships are being discovered differs from relational data for which computational approaches are developed in the data mining community for multiple decades, in that both spatial and temporal attributes are available in addition to the actual measurements/attributes. The presence of these attributes introduces additional challenges that needs to be dealt with. In this talk, I will present examples of relationships from relevant application areas. I will discuss the challenges involved in mining relationships from spatio-temporal data and present some of our recent and on-going work in this area.

Short Bio:

Gowtham Atluri is an Assistant Professor of Computer Science at the University of Cincinnati. His research involves developing computational data science approaches for mining spatio-temporal data with applications in neuroscience, climate science, and mobile health. Prior to joining the University of Cincinnati, Dr. Atluri worked as a postdoctoral associate at the University of Minnesota. He received his Ph.D. in 2014 from the University of Minnesota under the supervision of Prof. Vipin Kumar.

Emily Miraldi
Cincinnati Children's Hospital

Gene expression profiling provides a global readout on what cells are doing, and transcriptional regulatory network (TRN) models provide mechanistic insight into how these behaviors are regulated (through the coordinated activities of multiple transcription factors (TFs)). Breakthroughs in sequencing technologies enable global measurements of gene expression from increasingly small amounts of sample material and recently reached single-cell resolution. The advent of single-cell RNA-seq (scRNA-seq) is especially important for understanding the behavior of cells in systems where sample material was previously too limited and/or too little known about cellular heterogeneity. However, current scRNA-seq techniques capture only 5-15% of total gene transcripts expressed in each cell. Thus, scRNA-seq results in sparse data matrices, in which sampling zeros (expressed transcripts but not detected, known as “dropout genes”) and true zeros (transcript not expressed) are difficult to distinguish. To learn TRNs from scRNA-seq data, it is important to resolve biological variations, the trends of interest, from technical variations. Thus, we test diverse computational and statistical methods (robust principal component analysis, Markov affinity propagation, multiple random imputation…) to recover dropout genes. We rigorously develop datasets to benchmark and guidelines for inference of transcriptional regulatory networks form single-cell RNA-seq measurements.

Short Bio:

Emily Miraldi is an Assistant Professor of Immunobiology and Biomedical Informatics at Cincinnati’s Children’s Hospital. Her lab develops computational methods to build predictive, mathematical models of the immune system from high-dimensional genomics measurements. Prior to joining Cincinnati Children’s Hospital, Miraldi worked as a postdoctoral fellow at New York University and the Flatiron Institute. She received her Ph.D. in Computational and Systems Biology from Massachusetts Institute of Technology (2012).

Oleg Demchenko
St. Petersburg State University

The aim of our research is to reveal factors that influence the choice of shopper's next purchase during a supermarket visit. The analysis is implemented using a combined data set obtained both from points of sales and radio frequency identifi cation tags attached to shopping carts which allows one to determine the order of purchases. It demonstrates the importance of the spatial proximity of the next purchase (TSP-optimal order) which was the focus of most previous research. Inclusion of additional information on product features such as price and hedonicity or customer characteristics such as familiarity with the store shows that they also affect customers' choice of the next purchase, though in less degree. The results obtained improve our understanding of consumer in-store path behavior thus giving implications for store layout decisions.

Short Bio:

Oleg Demchenko is an Associate Professor in the Department of Mathematics and Mechanics at St.Petersburg State University. His research interests include both pure mathematics and its application to social sciences, in particular modeling and understanding potential mechanisms behind social phenomena. Dr. Demchenko was a visiting researcher at Tohoku University and Hokkaido University. He obtained his PhD in Mathematics from St. Petersburg State University and Master's degree in Economics from European University at St.Petersburg.

Wing-Kin Sung
National University of Singapore

Due to the advance in next generation sequencing, our genome can be sequenced using approximately US$1000. The cost is going to be reduced in the near future. It gives hope to have a cheap solution for personalize medicine.

However, it is not an easy task to reconstruct a correct individual genome from such a big sequencing dataset. The main issue is the repeat regions in human genome, which make it difficult to position the sequencing reads on the human reference genome. In this talk, we will discuss issues and partial solutions to solve such a problem.

Short Bio:

Dr. Wing-Kin Sung (宋永健) received both the B.Sc. and the Ph.D. degree in the Department of Computer Science from the University of Hong Kong in 1993, 1998, respectively. He is a professor in the Department of Computer Science, School of Computing, NUS. Also, he is a senior group leader in Genome Institute of Singapore. He has over 20 years experience in Algorithm and Bioinformatics research. He also teaches courses on bioinformatics for both undergraduate and postgraduate. He was conferred the 2003 FIT paper award (Japan), the 2006 National Science Award (Singapore), and the 2008 Young Researcher Award (NUS) for his research contribution in algorithm and bioinformatics.

Ilan Newman
The University of Haifa

We study testing of sequence properties that are defined by forbidden order patterns.

An Order pattern of length \(k\) is defined by a permutation \(\pi = (\pi(1), \ldots ,\pi(k))\) of \(k\) elements. A sequence \(f: \{1,\ldots,n\} \rightarrow R\) of length \(n\) contains a pattern \(\pi\) if there is a subsequence of \(f\) in which the order of the elements in it is identical to the order defined by \(\pi\). Namely, there are indices \(i_1 < i_2 < \dots < i_k\), such that \(f(i_x) > f(i_y)\) whenever \(\pi(x) > \pi(y)\). If \(f\) does not contain \(\pi\), we say that \(f\) is \(\pi\)-free. For example, for \(\pi = (2,1)\), the property of being \(\pi\)-free is equivalent to being non-decreasing, i.e. monotone.

For a fixed order pattern \(\pi\), of constant length \(k\), and input sequence \(f\) stored in an array, we consider the property testing problem of distinguishing the case that \(f\) is \(\pi\)-free from the case that \(f\) differs in more than \(\epsilon n\) places from any \(\pi\)-free sequence. We show the following results:

1. Being \(\pi\)-free can be tested in slightly sublinear number of queries for every fixed length \(\pi\).

2. There is a clear dichotomy between the monotone patterns and the non-monotone ones: For monotone patterns of length \(k\), i.e., \((k,k-1,\dots, 1)\) and \((1,2,\dots,k)\), we design non-adaptive, one-sided error \(\epsilon\)-tests of \(\mathrm{poly}(\log n)\) query complexity. For non-monotone patterns of size k we show that any non-adaptive one-sided error test requires at least \(\Omega(\sqrt{n})\) queries. This general lower bound can be further strengthened for specific non-monotone \(k\)-length patterns to \(\Omega(n^{1-2/(k+1)})\).

3. We show that adaptivity can make a big difference in testing non-monotone patterns. We develop an adaptive algorithm that for any length \(3\) pattern \(\pi\) tests \(\pi\)-freeness by making \(\mathrm{ploy}(\log n)\) queries.

For all algorithms presented here, the running times are linear in their query complexity.

This is a joint work with Deepak Rajendraprasad, Christian Sohler and Yuri Rabinovich.

Moritz Mühlenthaler
TU Dortmund University

We consider solution graphs of combinatorial problems with respect to certain natural adjacency relations. These graphs are typically too large to be stored explicitly. We will give a brief overview of what is known about the complexity of the (st-)connectivity problem on such graphs. Furthermore, we will showcase some recent results on the st-connectivity problem in a particular class of solution graphs, namely graphs on common independent sets of matroids.

Keisuke Goto
Fujitsu Laboratories Ltd.

Initializing all elements of a given array to a specified value is basic operation that frequently appears in numerous algorithms and programs. Initializable arrays are abstract arrays that support initialization as well as reading and writing of any element of the array in constant worst case time. On the word RAM model, we propose an in-place algorithm which implements an initializable array of length \(N\) with only 1 extra bit, where \(w\) is the word size, and each element of the array can store an individual value of \(\ell \in \mathrm{O}(w)\) bits. Our algorithm significantly improves upon the previous best algorithm [Navarro, CSUR 2014] using \(N+\ell+\mathrm{o}(N)\) extra bits.

Abstract: To be announced.

Kazuki Ishiyama
The University of Tokyo

We consider the orthogonal range search problem. In this problem, we are given a point set \(P\) in \(d\)-dimensional space and an orthogonal query region \(Q\), and return some information on \(P \cap Q\). We focus on the counting query: count the number of points of \(P\) contained in \(Q\), and the reporting query: report all points of \(P\) in \(Q\). For \(2\)-dimensional case, Bose et al. proposed a space-efficient data structure supporting the counting query in \(\mathrm{O}(\lg n / \lg \lg n)\) time and the reporting query in \(\mathrm{O}(k \lg n / \lg \lg n)\) time, where \(n\) is the number of points of \(P\) and \(k\) is the number of points which are contained in \(Q\). For high-dimensional cases, the KDW-tree [Okajima, Maruyama, ALENEX 2015] and the data structure of [Ishiyama, Sadakane, DCC 2017] have been proposed. However, they are not efficient for very large \(d\), the number of dimensions. In our research, we propose practical space-efficient data structures for the problem. They run fast when \(d'\), the number of dimensions used in queries, is smaller than the data dimension \(d\). This kind of queries are typical in database queries.

Takehiro Ito
Tohoku University

It has been studied intensively from the algorithmic viewpoint to analyze the solution space of (vertex-)colorings on a graph. In this talk, we consider the problem of asking the reachability (st-connectivity) on the solution space, that is, we wish to transform a given coloring into another given one by recoloring only a single vertex at a time, while maintaining always proper coloring.

Zuo Yi
Nagoya University

Customer relationship management (CRM) is one of the most important design tools to manage customer groups and understand potential relationships. CRM tools use many communication approaches such as telephone, email and social media to collect mass of customer data, which can help the companies (managers) to increase sales growth and enhance customer retention. Since 2000s, the advancements of RFID technology brought a new perspective on customer in-store behavior. Based on such RFID data, this work describes a novel analytic approach applying social network analysis (SNA) into customer relationship network (CRN). In this work, we attempt to construct the CRN basing the shopping path (visiting pattern), which is recognized as a data stream of digitally encoded coherent signals. The CRN can help us to understand the customer relationships from the network perspective. Then, we also employ network clustering (also called community detection or node classification) method to extract customer groups by maximizing the modularity. The modularity provides us a structural and relational understanding of customer groups. Finally, we use z-P parameter space to identify the “hub” customers by a topological process.