3 Search Results for "Liu, Tian"

Document
DOI: 10.4230/LIPIcs.ESA.2022.70
Vertex Sparsifiers for Hyperedge Connectivity

Authors: Han Jiang, Shang-En Huang, Thatchaphol Saranurak, and Tian Zhang

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)

Abstract
Recently, Chalermsook et al. {[}SODA'21{]} introduces a notion of vertex sparsifiers for c-edge connectivity, which has found applications in parameterized algorithms for network design and also led to exciting dynamic algorithms for c-edge st-connectivity {[}Jin and Sun FOCS'22{]}. We study a natural extension called vertex sparsifiers for c-hyperedge connectivity and construct a sparsifier whose size matches the state-of-the-art for normal graphs. More specifically, we show that, given a hypergraph G = (V,E) with n vertices and m hyperedges with k terminal vertices and a parameter c, there exists a hypergraph H containing only O(kc³) hyperedges that preserves all minimum cuts (up to value c) between all subset of terminals. This matches the best bound of O(kc³) edges for normal graphs by [Liu'20]. Moreover, H can be constructed in almost-linear O(p^{1+o(1)} + n(rclog n)^{O(rc)}log m) time where r = max_{e ∈ E}|e| is the rank of G and p = ∑_{e ∈ E}|e| is the total size of G, or in poly(m, n) time if we slightly relax the size to O(kc³log^{1.5}(kc)) hyperedges.
Cite as

Han Jiang, Shang-En Huang, Thatchaphol Saranurak, and Tian Zhang. Vertex Sparsifiers for Hyperedge Connectivity. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 70:1-70:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{jiang_et_al:LIPIcs.ESA.2022.70,
  author =	{Jiang, Han and Huang, Shang-En and Saranurak, Thatchaphol and Zhang, Tian},
  title =	{{Vertex Sparsifiers for Hyperedge Connectivity}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{70:1--70:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.70},
  URN =		{urn:nbn:de:0030-drops-170081},
  doi =		{10.4230/LIPIcs.ESA.2022.70},
  annote =	{Keywords: Vertex sparsifier, hypergraph, connectivity}
}
Document
DOI: 10.4230/LIPIcs.WABI.2019.19
Faster Pan-Genome Construction for Efficient Differentiation of Naturally Occurring and Engineered Plasmids with Plaster

Authors: Qi Wang, R. A. Leo Elworth, Tian Rui Liu, and Todd J. Treangen

Published in: LIPIcs, Volume 143, 19th International Workshop on Algorithms in Bioinformatics (WABI 2019)

Abstract
As sequence databases grow, characterizing diversity across extremely large collections of genomes requires the development of efficient methods that avoid costly all-vs-all comparisons [Marschall et al., 2018]. In addition to exponential increases in the amount of natural genomes being sequenced, improved techniques for the creation of human engineered sequences is ushering in a new wave of synthetic genome sequence databases that grow alongside naturally occurring genome databases. In this paper, we analyze the full diversity of available sequenced natural and synthetic plasmid genome sequences. This diversity can be represented by a data structure that captures all presently available nucleotide sequences, known as a pan-genome. In our case, we construct a single linear pan-genome nucleotide sequence that captures this diversity. To process such a large number of sequences, we introduce the plaster algorithmic pipeline. Using plaster we are able to construct the full synthetic plasmid pan-genome from 51,047 synthetic plasmid sequences as well as a natural pan-genome from 6,642 natural plasmid sequences. We demonstrate the efficacy of plaster by comparing its speed against another pan-genome construction method as well as demonstrating that nearly all plasmids align well to their corresponding pan-genome. Finally, we explore the use of pan-genome sequence alignment to distinguish between naturally occurring and synthetic plasmids. We believe this approach will lead to new techniques for rapid characterization of engineered plasmids. Applications for this work include detection of genome editing, tracking an unknown plasmid back to its lab of origin, and identifying naturally occurring sequences that may be of use to the synthetic biology community. The source code for fully reconstructing the natural and synthetic plasmid pan-genomes as well for plaster are publicly available and can be downloaded at https://gitlab.com/qiwangrice/plaster.git.
Cite as

Qi Wang, R. A. Leo Elworth, Tian Rui Liu, and Todd J. Treangen. Faster Pan-Genome Construction for Efficient Differentiation of Naturally Occurring and Engineered Plasmids with Plaster. In 19th International Workshop on Algorithms in Bioinformatics (WABI 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 143, pp. 19:1-19:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{wang_et_al:LIPIcs.WABI.2019.19,
  author =	{Wang, Qi and Elworth, R. A. Leo and Liu, Tian Rui and Treangen, Todd J.},
  title =	{{Faster Pan-Genome Construction for Efficient Differentiation of Naturally Occurring and Engineered Plasmids with Plaster}},
  booktitle =	{19th International Workshop on Algorithms in Bioinformatics (WABI 2019)},
  pages =	{19:1--19:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-123-8},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{143},
  editor =	{Huber, Katharina T. and Gusfield, Dan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2019.19},
  URN =		{urn:nbn:de:0030-drops-110492},
  doi =		{10.4230/LIPIcs.WABI.2019.19},
  annote =	{Keywords: comparative genomics, sequence alignment, pan-genome, engineered plasmids}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2017.66
A (1.4 + epsilon)-Approximation Algorithm for the 2-Max-Duo Problem

Authors: Yao Xu, Yong Chen, Guohui Lin, Tian Liu, Taibo Luo, and Peng Zhang

Published in: LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017)

Abstract
The maximum duo-preservation string mapping (Max-Duo) problem is the complement of the well studied minimum common string partition (MCSP) problem, both of which have applications in many fields including text compression and bioinformatics. k-Max-Duo is the restricted version of Max-Duo, where every letter of the alphabet occurs at most k times in each of the strings, which is readily reduced into the well known maximum independent set (MIS) problem on a graph of maximum degree \Delta \le 6(k-1). In particular, 2-Max-Duo can then be approximated arbitrarily close to 1.8 using the state-of-the-art approximation algorithm for the MIS problem. 2-Max-Duo was proved APX-hard and very recently a (1.6 + \epsilon)-approximation was claimed, for any \epsilon > 0. In this paper, we present a vertex-degree reduction technique, based on which, we show that 2-Max-Duo can be approximated arbitrarily close to 1.4.
Cite as

Yao Xu, Yong Chen, Guohui Lin, Tian Liu, Taibo Luo, and Peng Zhang. A (1.4 + epsilon)-Approximation Algorithm for the 2-Max-Duo Problem. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 66:1-66:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{xu_et_al:LIPIcs.ISAAC.2017.66,
  author =	{Xu, Yao and Chen, Yong and Lin, Guohui and Liu, Tian and Luo, Taibo and Zhang, Peng},
  title =	{{A (1.4 + epsilon)-Approximation Algorithm for the 2-Max-Duo Problem}},
  booktitle =	{28th International Symposium on Algorithms and Computation (ISAAC 2017)},
  pages =	{66:1--66:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-054-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{92},
  editor =	{Okamoto, Yoshio and Tokuyama, Takeshi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.66},
  URN =		{urn:nbn:de:0030-drops-82120},
  doi =		{10.4230/LIPIcs.ISAAC.2017.66},
  annote =	{Keywords: Approximation algorithm, duo-preservation string mapping, string partition, independent set}
}
  • Refine by Author
  • 1 Chen, Yong
  • 1 Elworth, R. A. Leo
  • 1 Huang, Shang-En
  • 1 Jiang, Han
  • 1 Lin, Guohui
  • Show More...

  • Refine by Classification
  • 1 Applied computing → Bioinformatics
  • 1 Applied computing → Computational genomics
  • 1 Applied computing → Molecular sequence analysis
  • 1 Theory of computation → Sparsification and spanners

  • Refine by Keyword
  • 1 Approximation algorithm
  • 1 Vertex sparsifier
  • 1 comparative genomics
  • 1 connectivity
  • 1 duo-preservation string mapping
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 1 2017
  • 1 2019
  • 1 2022

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact