Source author record

Christine Lo

Christine Lo 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 Algorithms Genomics Quantitative Methods

Catalog footprint

What is connected

2works

3topics

3close collaborators

Actions

Connect this record

Open graph Browse works

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.

preprint2012arXiv

SeeSite: Efficiently Finding Co-occurring Splice Sites and Exon Splicing Enhancers

The problem of identifying splice sites consists of two sub-problems: finding their boundaries, and characterizing their sequence markers. Other splicing elements---including, enhancers and silencers---that occur in the intronic and exonic regions play an important role in splicing activity. Existing methods for detecting splicing elements are limited to finding either splice sites or enhancers and silencers, even though these elements are well-known to co-occur. We introduce SeeSite, an efficient and accurate tool for detecting splice sites and their complementary exon splicing enhancers (ESEs). SeeSite has three stages: graph construction, finding dense subgraphs, and recovering splice sites and ESEs along with their consensus. The third step involves solving Consensus Sequence with Outliers, an NP-complete string clustering problem. We prove that our algorithm for this problem outputs near-optimal solutions in polynomial time. Using SeeSite we demonstrate that ESEs are preferentially associated with weaker splice sites, and splice sites of a certain canonical form co-occur with specific ESEs.

preprint2011arXiv

Outlier Detection for DNA Fragment Assembly

Given $n$ length-$\ell$ strings $S =\{s_1, ..., s_n\}$ over a constant size alphabet $Σ$ together with parameters $d$ and $k$, the objective in the {\em Consensus String with Outliers} problem is to find a subset $S^*$ of $S$ of size $n-k$ and a string $s$ such that $\sum_{s_i \in S^*} d(s_i, s) \leq d$. Here $d(x, y)$ denotes the Hamming distance between the two strings $x$ and $y$. We prove 1. a variant of {\em Consensus String with Outliers} where the number of outliers $k$ is fixed and the objective is to minimize the total distance $\sum_{s_i \in S^*} d(s_i, s)$ admits a simple PTAS. (ii) Under the natural assumption that the number of outliers $k$ is small, the PTAS for the distance minimization version of {\em Consensus String with Outliers} performs well. In particular, as long as $k\leq cn$ for a fixed constant $c < 1$, the algorithm provides a $(1+ε)$-approximate solution in time $f(1/ε)(n\ell)^{O(1)}$ and thus, is an EPTAS. 2. In order to improve the PTAS for {\em Consensus String with Outliers} to an EPTAS, the assumption that $k$ is small is necessary. Specifically, when $k$ is allowed to be arbitrary the {\em Consensus String with Outliers} problem does not admit an EPTAS unless FPT=W[1]. This hardness result holds even for binary alphabets. 3. The decision version of {\em Consensus String with Outliers} is fixed parameter tractable when parameterized by $\frac{d}{n-k}$. and thus, also when parameterized by just $d$. To the best of our knowledge, {\em Consensus String with Outliers} is the first problem that admits a PTAS, and is fixed parameter tractable when parameterized by the value of the objective function but does not admit an EPTAS under plausible complexity assumptions.