Wing-Kin Sung

TCS Journal 2021 Journal Article

A linear time algorithm for the r-gathering problem on the line

• Anik Sarker
• Wing-Kin Sung
• M. Sohel Rahman

In this paper, we revisit the r-gathering problem. Given sets C and F of points on the plane and distance d ( c, f ) for each c ∈ C and f ∈ F, an r-gathering of C to F is an assignment A of C to open facilities F ′ ⊆ F such that r or more members of C are assigned to each open facility. The cost of an r-gathering is max c ∈ C ⁡ d ( c, A ( c ) ). The r-gathering problem computes the r-gathering minimizing the cost. In this paper we study the r-gathering problem when C and F are on a line and present a O ( | C | + | F | ) -time algorithm to solve the problem. Our solution is optimal since any algorithm needs to read C and F at least once.

TCS Journal 2020 Journal Article

Faster algorithms for 1-mappability of a sequence

• Mai Alzamel
• Panagiotis Charalampopoulos
• Costas S. Iliopoulos
• Solon P. Pissis
• Jakub Radoszewski
• Wing-Kin Sung

In the k-mappability problem, we are given a string x of length n and integers m and k, and we are asked to count, for each length-m factor y of x, the number of other factors of length m of x that are at Hamming distance at most k from y. We focus here on the version of the problem where k = 1. There exists an algorithm to solve this problem for k = 1 requiring time O ( m n log ⁡ n / log ⁡ log ⁡ n ) using space O ( n ). Here we present two new algorithms that require worst-case time O ( m n ) and O ( n log ⁡ n log ⁡ log ⁡ n ), respectively, and space O ( n ), thus greatly improving the previous result. Moreover, we present another algorithm that requires average-case time and space O ( n ) for integer alphabets of size σ if m = Ω ( log σ ⁡ n ). Notably, we show that this algorithm is generalizable for arbitrary k, requiring average-case time O ( k n ) and space O ( n ) if m = Ω ( k log σ ⁡ n ), assuming that the letters are independent and uniformly distributed random variables. Finally, we provide an experimental evaluation of our average-case algorithm demonstrating its competitiveness to the state-of-the-art implementation.

ICLR Conference 2020 Conference Paper

Weakly Supervised Clustering by Exploiting Unique Class Count

• Mustafa Umit Oner
• Hwee Kuan Lee
• Wing-Kin Sung

A weakly supervised learning based clustering framework is proposed in this paper. As the core of this framework, we introduce a novel multiple instance learning task based on a bag level label called unique class count (ucc), which is the number of unique classes among all instances inside the bag. In this task, no annotations on individual instances inside the bag are needed during training of the models. We mathematically prove that with a perfect ucc classifier, perfect clustering of individual instances inside the bags is possible even when no annotations on individual instances are given during training. We have constructed a neural network based ucc classifier and experimentally shown that the clustering performance of our framework with our weakly supervised ucc classifier is comparable to that of fully supervised learning models where labels for all instances are known. Furthermore, we have tested the applicability of our framework to a real world task of semantic segmentation of breast cancer metastases in histological lymph node sections and shown that the performance of our weakly supervised framework is comparable to the performance of a fully supervised Unet model.

TCS Journal 2019 Journal Article

Off-line and on-line algorithms for closed string factorization

• Mai Alzamel
• Costas S. Iliopoulos
• W.F. Smyth
• Wing-Kin Sung

A string X = X [ 1. . n ], n > 1, is said to be closed if it has a nonempty proper prefix that is also a suffix, but that otherwise occurs nowhere else in X; for n = 1, every X is closed. Closed strings were introduced by Fici in [1] as objects of combinatorial interest. Recently Badkobeh et al. [2] described a variety of algorithms to factor a given string into closed factors. In particular, they studied the Longest Closed Factorization (LCF) problem, which greedily computes the decomposition X = X 1 X 2 ⋯ X k, where X 1 is the longest closed prefix of X, X 2 the longest closed prefix of X with prefix X 1 removed, and so on. In this paper we present an O ( log ⁡ n ) amortized per character algorithm to compute LCF on-line, where n is the length of the string. We also introduce the Minimum Closed Factorization (MCF) problem, which identifies the minimum number of closed factors that cover X. We first describe an off-line O ( n log 2 ⁡ n ) -time algorithm to compute M C F ( X ), then we present an on-line algorithm for the same problem. In fact, we show that M C F ( X ) can be computed in O ( L log ⁡ n ) time from M C F ( X ′ ), where X ′ = X [ 1. . n − 1 ], and L is the largest integer such that the suffix X [ n − L + 1. . n ] is a substring of X ′.

I&C Journal 2017 Journal Article

On finding the Adams consensus tree

• Jesper Jansson
• Zhaoxian Li
• Wing-Kin Sung

This article presents a fast algorithm for finding the Adams consensus tree of a set of conflicting phylogenetic trees with identical leaf labels. Its worst-case running time is O ( k n log ⁡ n ), where k is the number of input trees and n is the size of the leaf label set; in comparison, the original algorithm of Adams has a worst-case running time of O ( k n 2 ). To achieve subquadratic running time, the centroid path decomposition technique is applied in a novel way that traverses the input trees by following a centroid path in each of them in unison. For k = 2, an even faster algorithm running in O ( n ⋅ log ⁡ n log ⁡ log ⁡ n ) time is provided, which relies on an extension of the wavelet tree-based technique of Bose et al. for orthogonal range counting on a grid. Our extended wavelet tree data structure also supports truncated range maximum/minimum queries efficiently.

MFCS Conference 2016 Conference Paper

Minimal Phylogenetic Supertrees and Local Consensus Trees

• Jesper Jansson 0001
• Wing-Kin Sung

The problem of constructing a minimally resolved phylogenetic supertree (i. e. , having the smallest possible number of internal nodes) that contains all of the rooted triplets from a consistent set R is known to be NP-hard. In this paper, we prove that constructing a phylogenetic tree consistent with R that contains the minimum number of additional rooted triplets is also NP-hard, and develop exact, exponential-time algorithms for both problems. The new algorithms are applied to construct two variants of the local consensus tree; for any set S of phylogenetic trees over some leaf label set L, this gives a minimal phylogenetic tree over L that contains every rooted triplet present in all trees in S, where ``minimal'' means either having the smallest possible number of internal nodes or the smallest possible number of rooted triplets. The second variant generalizes the RV-II tree, introduced by Kannan, Warnow, and Yooseph in 1998.

TCS Journal 2014 Journal Article

Fast relative Lempel–Ziv self-index for similar sequences

• Huy Hoang Do
• Jesper Jansson
• Kunihiko Sadakane
• Wing-Kin Sung

Recent advances in biotechnology and web technology are continuously generating huge collections of similar strings. People now face the problem of storing them compactly while supporting fast pattern searching. One compression scheme called relative Lempel–Ziv compression uses textual substitutions from a reference text to represent each string in S as a concatenation of substrings from a reference string R. This basic scheme gives a good compression ratio when every string in S is similar to R, but does not provide any pattern searching functionality. Here, we describe a new data structure based on relative Lempel–Ziv compression that is space-efficient and also supports fast pattern searching.

SODA Conference 2013 Conference Paper

Improved Algorithms for Constructing Consensus Trees

• Jesper Jansson 0001
• Chuanqi Shen
• Wing-Kin Sung

TCS Journal 2012 Journal Article

More efficient periodic traversal in anonymous undirected graphs

• Jurek Czyzowicz
• Stefan Dobrev
• Leszek Gąsieniec
• David Ilcinkas
• Jesper Jansson
• Ralf Klasing
• Ioannis Lignos
• Russell Martin

We consider the problem of periodic graph exploration in which a mobile entity with constant memory, an agent, has to visit all n nodes of an input simple, connected, undirected graph in a periodic manner. Graphs are assumed to be anonymous, that is, nodes are unlabeled. While visiting a node, the agent may distinguish between the edges incident to it; for each node v, the endpoints of the edges incident to v are uniquely identified by different integer labels called port numbers. We are interested in algorithms for assigning the port numbers together with traversal algorithms for agents using these port numbers to obtain short traversal periods. Periodic graph exploration is unsolvable if the port numbers are set arbitrarily; see Budach (1978) [1]. However, surprisingly small periods can be achieved by carefully assigning the port numbers. Dobrev et al. (2005) [4] described an algorithm for assigning port numbers and an oblivious agent (i. e. , an agent with no memory) using it, such that the agent explores any graph with n nodes within the period 10 n. When the agent has access to a constant number of memory bits, the optimal length of the period was proved in Gąsieniec et al. (2008) [7] to be no more than 3. 75 n − 2 (using a different assignment of the port numbers and a different traversal algorithm). In this paper, we improve both these bounds. More precisely, we show how to achieve a period length of at most ( 4 + 1 3 ) n − 4 for oblivious agents and a period length of at most 3. 5 n − 2 for agents with constant memory. To obtain our results, we introduce a new, fast graph decomposition technique called a three-layer partition that may also be useful for solving other graph problems in the future. Finally, we present the first non-trivial lower bound, 2. 8 n − 2, on the period length for the oblivious case.

TCS Journal 2011 Journal Article

Succinct data structures for Searchable Partial Sums with optimal worst-case performance

• Wing-Kai Hon
• Kunihiko Sadakane
• Wing-Kin Sung

The notion of succinct indexes can be dated back from the debut of Jacobson’s thesis (1988) [14], and has triggered many results in the last decade. In traditional indexing, some given data are preprocessed so as to support online queries (and updates) on the data as efficiently as possible. When succinctness is involved, we are restricted to index the data using only an information–theoretically minimum number of bits. This paper concerns the succinct indexing schemes for a well-studied problem called Searchable Partial Sums (SPS). In SPS, an array A of n non-negative k -bit integers is preprocessed so as to support online sum and search queries, and possibly update operation of individual entry. A succinct indexing scheme would allow only k n + o ( k n ) bits to represent the array A. The only known result is that when k = 1 (in this case, it is known as the Dynamic Bit Array Problem), we can support both queries in O ( log b n ) time and update in O ( b ) amortized time for any b with lg n / lg lg n ≤ b ≤ n. This paper shows that even for k = O ( lg lg n ), we can index A succinctly such that both query and update operations can be supported using the same time complexities. Moreover, the time for update becomes the worst-case time. Furthermore, the tradeoff between the query times and the update time is optimal as implied by Paˇtraşcu and Demaine’s lower bound result (2006) [24]. In general when k = O ( lg U ), we show a lower bound of Ω ( lg n / lg lg n ) time for the search query irrespective of the update time. This gives a tighter lower bound as compared to that of Paˇtraşcu and Demaine’s, which is a consequence of the requirement of succinctness. On the other hand, we give a succinct index that can support sum in O ( log b n ) time, search in O ( τ log b n ) time, and update in O ( b ) time, where τ = min { lg lg n lg lg U / lg lg lg U, lg n / lg lg n }. The query times are optimal when b = n ϵ. This paper also extends the Searchable Partial Sums with insert and delete operations, and provides a succinct data structure for some cases.

SODA Conference 2007 Conference Paper

Ultra-succinct representation of ordered trees

• Jesper Jansson 0001
• Kunihiko Sadakane
• Wing-Kin Sung

TCS Journal 2006 Journal Article

Approximate string matching using compressed suffix arrays

• Trinh N.D. Huynh
• Wing-Kai Hon
• Tak-Wah Lam
• Wing-Kin Sung

Let T be a text of length n and P be a pattern of length m, both strings over a fixed finite alphabet A. The k -difference ( k -mismatch, respectively) problem is to find all occurrences of P in T that have edit distance (Hamming distance, respectively) at most k from P. In this paper we investigate a well-studied case in which T is fixed and preprocessed into an indexing data structure so that any pattern query can be answered faster. We give a solution using an O ( n log n ) bits indexing data structure with O ( | A | k m k · max ( k, log n ) + occ ) query time, where occ is the number of occurrences. The best previous result requires O ( n log n ) bits indexing data structure and gives O ( | A | k m k + 2 + occ ) query time. Our solution also allows us to exploit compressed suffix arrays to reduce the indexing space to O ( n ) bits, while increasing the query time by an O ( log n ) factor only.

TCS Journal 2006 Journal Article

Inferring a level-1 phylogenetic network from a dense set of rooted triplets

• Jesper Jansson
• Wing-Kin Sung

We consider the following problem: Given a set T of rooted triplets with leaf set L, determine whether there exists a phylogenetic network consistent with T, and if so, construct one. We show that if no restrictions are placed on the hybrid nodes in the solution, the problem is trivially solved in polynomial time by a simple sorting network-based construction. For the more interesting (and biologically more motivated) case where the solution is required to be a level-1 phylogenetic network, we present an algorithm solving the problem in O ( | T | 2 ) time when T is dense, i. e. , when T contains at least one rooted triplet for each cardinality three subset of L. We also give an O ( | T | 5 / 3 ) -time algorithm for finding the set of all phylogenetic networks having a single hybrid node attached to exactly one leaf (and having no other hybrid nodes) that are consistent with a given dense set of rooted triplets.

SODA Conference 2005 Conference Paper

Algorithms for combining rooted triplets into a galled phylogenetic network

• Jesper Jansson 0001
• Nguyen Bao Nguyen
• Wing-Kin Sung

AIIM Journal 2005 Journal Article

Computational modeling of oligonucleotide positional densities for human promoter prediction

• Vipin Narang
• Wing-Kin Sung
• Ankush Mittal

Objective: The gene promoter region controls transcriptional initiation of a gene, which is the most important step in gene regulation. In-silico detection of promoter region in genomic sequences has a number of applications in gene discovery and understanding gene expression regulation. However, computational prediction of eukaryotic poly-II promoters has remained a difficult task. This paper introduces a novel statistical technique for detecting promoter regions in long genomic sequences. Method: A number of existing techniques analyze the occurrence frequencies of oligonucleotides in promoter sequences as compared to other genomic regions. In contrast, the present work studies the positional densities of oligonucleotides in promoter sequences. The analysis does not require any non-promoter sequence dataset or any model of the background oligonucleotide content of the genome. The statistical model learnt from a dataset of promoter sequences automatically recognizes a number of transcription factor binding sites simultaneously with their occurrence positions relative to the transcription start site. Based on this model, a continuous naïve Bayes classifier is developed for the detection of human promoters and transcription start sites in genomic sequences. Results: The present study extends the scope of statistical models in general promoter modeling and prediction. Promoter sequence features learnt by the model correlate well with known biological facts. Results of human transcription start site prediction compare favorably with existing 2nd generation promoter prediction tools.

TCS Journal 2005 Journal Article

Computing the maximum agreement of phylogenetic networks

• Charles Choy
• Jesper Jansson
• Kunihiko Sadakane
• Wing-Kin Sung

We introduce the maximum agreement phylogenetic subnetwork problem (MASN) for finding branching structure shared by a set of phylogenetic networks. We prove that the problem is NP-hard even if restricted to three phylogenetic networks and give an O ( n 2 ) -time algorithm for the special case of two level-1 phylogenetic networks, where n is the number of leaves in the input networks and where N is called a level- f phylogenetic network if every biconnected component in the underlying undirected graph induces a subgraph of N containing at most f nodes with indegree 2. We also show how to extend our technique to yield a polynomial-time algorithm for any two level- f phylogenetic networks N 1, N 2 satisfying f = O ( log n ); more precisely, its running time is O ( | V ( N 1 ) | · | V ( N 2 ) | · 2 f 1 + f 2 ), where V ( N i ) and f i denote the set of nodes in N i and the level of N i, respectively, for i ∈ { 1, 2 }.

ECAI Conference 2004 Conference Paper

Gene Network Modeling through Semi-Fixed Bayesian Network

• Tie-Fei Liu
• Wing-Kin Sung
• Ankush Mittal

FOCS Conference 2003 Conference Paper

Breaking a Time-and-Space Barrier in Constructing Full-Text Indices

• Wing-Kai Hon
• Kunihiko Sadakane
• Wing-Kin Sung

Suffix trees and suffix arrays are the most prominent full-text indices, and their construction algorithms are well studied. It has been open for a long time whether these indices can be constructed in both O(n log n) time and O(n log n)-bit working space, where n denotes the length of the text. In the literature, the fastest algorithm runs in O(n) time, while it requires O(n log n)-bit working space. On the other hand, the most space-efficient algorithm requires O(n)-bit working space while it runs in O(n log n) time. This paper breaks the long-standing time-and-space barrier under the unit-cost word RAM. We give an algorithm for constructing the suffix array which takes O(n) time and O(n)-bit working space, for texts with constant-size alphabets. Note that both the time and the space bounds are optimal. For constructing the suffix tree, our algorithm requires O(n log/sup /spl epsi//n) time and O(n)-bit working space for any 0 < /spl epsi/ < 1. Apart from that, our algorithm can also be adopted to build other existing full-text indices, such as Compressed Suffix Tree, Compressed Suffix Arrays and FM-index. We also study the general case where the size of the alphabet A is not constant. Our algorithm can construct a suffix array and a suffix tree using optimal O(n log |A|)-bit working space while running in O(n log log |A|) time and O(n log/sup /spl epsi//n) time, respectively. These are the first algorithms that achieve 0(n log n) time with optimal working space, under a reasonable assumption that log |A| = o(log n).

STOC Conference 1997 Conference Paper

General Techniques for Comparing Unrooted Evolutionary Trees

• Ming-Yang Kao
• Tak Wah Lam
• Teresa M. Przytycka
• Wing-Kin Sung
• Hing-Fung Ting