BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Hing-Fung Ting

Hing-Fung Ting appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Data Structures and AlgorithmsGenomics

Catalog footprint

What is connected

4works
2topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

4 published item(s)

preprint2013arXiv

SOAP3-dp: Fast, Accurate and Sensitive GPU-based Short Read Aligner

To tackle the exponentially increasing throughput of Next-Generation Sequencing (NGS), most of the existing short-read aligners can be configured to favor speed in trade of accuracy and sensitivity. SOAP3-dp, through leveraging the computational power of both CPU and GPU with optimized algorithms, delivers high speed and sensitivity simultaneously. Compared with widely adopted aligners including BWA, Bowtie2, SeqAlto, GEM and GPU-based aligners including BarraCUDA and CUSHAW, SOAP3-dp is two to tens of times faster, while maintaining the highest sensitivity and lowest false discovery rate (FDR) on Illumina reads with different lengths. Transcending its predecessor SOAP3, which does not allow gapped alignment, SOAP3-dp by default tolerates alignment similarity as low as 60 percent. Real data evaluation using human genome demonstrates SOAP3-dp's power to enable more authentic variants and longer Indels to be discovered. Fosmid sequencing shows a 9.1 percent FDR on newly discovered deletions. SOAP3-dp natively supports BAM file format and provides a scoring scheme same as BWA, which enables it to be integrated into existing analysis pipelines. SOAP3-dp has been deployed on Amazon-EC2, NIH-Biowulf and Tianhe-1A.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Edit Distance to Monotonicity in Sliding Windows

Given a stream of items each associated with a numerical value, its edit distance to monotonicity is the minimum number of items to remove so that the remaining items are non-decreasing with respect to the numerical value. The space complexity of estimating the edit distance to monotonicity of a data stream is becoming well-understood over the past few years. Motivated by applications on network quality monitoring, we extend the study to estimating the edit distance to monotonicity of a sliding window covering the $w$ most recent items in the stream for any $w \ge 1$. We give a deterministic algorithm which can return an estimate within a factor of $(4+\eps)$ using $O(\frac{1}{\eps^2} \log^2(\eps w))$ space. We also extend the study in two directions. First, we consider a stream where each item is associated with a value from a partial ordered set. We give a randomized $(4+ε)$-approximate algorithm using $O(\frac{1}{ε^2} \log ε^2 w \log w)$ space. Second, we consider an out-of-order stream where each item is associated with a creation time and a numerical value, and items may be out of order with respect to their creation times. The goal is to estimate the edit distance to monotonicity with respect to the numerical value of items arranged in the order of creation times. We show that any randomized constant-approximate algorithm requires linear space.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Continuous Monitoring of Distributed Data Streams over a Time-based Sliding Window

The past decade has witnessed many interesting algorithms for maintaining statistics over a data stream. This paper initiates a theoretical study of algorithms for monitoring distributed data streams over a time-based sliding window (which contains a variable number of items and possibly out-of-order items). The concern is how to minimize the communication between individual streams and the root, while allowing the root, at any time, to be able to report the global statistics of all streams within a given error bound. This paper presents communication-efficient algorithms for three classical statistics, namely, basic counting, frequent items and quantiles. The worst-case communication cost over a window is $O(\frac{k} ε \log \frac{εN}{k})$ bits for basic counting and $O(\frac{k}ε \log \frac{N}{k})$ words for the remainings, where $k$ is the number of distributed data streams, $N$ is the total number of items in the streams that arrive or expire in the window, and $ε< 1$ is the desired error bound. Matching and nearly matching lower bounds are also obtained.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Deterministic Online Call Control in Cellular Networks and Triangle-Free Cellular Networks

Wireless Communication Networks based on Frequency Division Multiplexing (FDM in short) plays an important role in the field of communications, in which each request can be satisfied by assigning a frequency. To avoid interference, each assigned frequency must be different to the neighboring assigned frequencies. Since frequency is a scarce resource, the main problem in wireless networks is how to fully utilize the given bandwidth of frequencies. In this paper, we consider the online call control problem. Given a fixed bandwidth of frequencies and a sequence of communication requests arrive over time, each request must be either satisfied immediately after its arrival by assigning an available frequency, or rejected. The objective of call control problem is to maximize the number of accepted requests. We study the asymptotic performance of this problem, i.e., the number of requests in the sequence and the bandwidth of frequencies are very large. In this paper, we give a 7/3-competitive algorithm for call control problem in cellular network, improving the previous 2.5-competitive result. Moreover, we investigate the triangle-free cellular network, propose a 9/4-competitive algorithm and prove that the lower bound of competitive ratio is at least 5/3.

0 citations0 reviewsNo code linkedOpen access