DROPS

Document

DOI: 10.4230/LIPIcs.AFT.2024.8

A Circuit Approach to Constructing Blockchains on Blockchains

Authors: Ertem Nusret Tas, David Tse, and Yifei Wang

Published in: LIPIcs, Volume 316, 6th Conference on Advances in Financial Technologies (AFT 2024)

Abstract

Recent years have witnessed an explosion of blockchains, each with an open ledger that anyone can read from and write to. In this multi-chain world, an important question emerges: how can we build a more secure overlay blockchain by reading from and writing to a given set of blockchains? Drawing an analogy with switching circuits, we approach the problem by defining two basic compositional operations between blockchains, serial and triangular compositions, and use these operations as building blocks to construct general overlay blockchains. Under the partially synchronous setting, we have the following results: 1) the serial composition, between two certificate-producing blockchains, yields an overlay blockchain that is safe if at least one of the two underlay blockchains is safe and that is live if both of them are live; 2) the triangular composition between three blockchains, akin to parallel composition of switching circuits, yields an overlay blockchain that is safe if all underlay blockchains are safe and that is live if over half of them are live; 3) repeated composition of these two basic operations can yield all possible tradeoffs of safety and liveness for an overlay blockchain built on an arbitrary number of underlay chains. The results are also extended to the synchronous setting.

Cite as

Ertem Nusret Tas, David Tse, and Yifei Wang. A Circuit Approach to Constructing Blockchains on Blockchains. In 6th Conference on Advances in Financial Technologies (AFT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 316, pp. 8:1-8:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{tas_et_al:LIPIcs.AFT.2024.8,
  author =	{Tas, Ertem Nusret and Tse, David and Wang, Yifei},
  title =	{{A Circuit Approach to Constructing Blockchains on Blockchains}},
  booktitle =	{6th Conference on Advances in Financial Technologies (AFT 2024)},
  pages =	{8:1--8:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-345-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{316},
  editor =	{B\"{o}hme, Rainer and Kiffer, Lucianna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AFT.2024.8},
  URN =		{urn:nbn:de:0030-drops-209442},
  doi =		{10.4230/LIPIcs.AFT.2024.8},
  annote =	{Keywords: interchain consensus protocols, serial composition, triangular composition, circuits}
}

Document

DOI: 10.4230/LIPIcs.WABI.2017.15

abSNP: RNA-Seq SNP Calling in Repetitive Regions via Abundance Estimation

Authors: Shunfu Mao, Soheil Mohajer, Kannan Ramachandran, David Tse, and Sreeram Kannan

Published in: LIPIcs, Volume 88, 17th International Workshop on Algorithms in Bioinformatics (WABI 2017)

Abstract

Variant calling, in particular, calling SNPs (Single Nucleotide Polymorphisms) is a fundamental task in genomics. While existing packages offer excellent performance on calling SNPs which have uniquely mapped reads, they suffer in loci where the reads are multiply mapped, and are unable to make any reliable calls. Variants in multiply mapped loci can arise, for example in long segmental duplications, and can play important role in evolution and disease. In this paper, we develop a new SNP caller named abSNP, which offers three innovations. (a) abSNP calls SNPs from RNA-Seq data. Since RNA-Seq data is primarily sampled from gene regions, this method is inexpensive. (b) abSNP is able to successfully make calls on repetitive gene regions by exploiting the quality scores of multiply mapped reads carefully in order to make variant calls. (c) abSNP exploits a specific feature of RNA-Seq data, namely the varying abundance of different genes, in order to identify which repetitive copy a particular read is sampled from. We demonstrate that the proposed method offers significant performance gains on repetitive regions in simulated data. In particular, the algorithm is able to achieve near-perfect sensitivity on high-coverage SNPs, even when multiply mapped.

Cite as

Shunfu Mao, Soheil Mohajer, Kannan Ramachandran, David Tse, and Sreeram Kannan. abSNP: RNA-Seq SNP Calling in Repetitive Regions via Abundance Estimation. In 17th International Workshop on Algorithms in Bioinformatics (WABI 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 88, pp. 15:1-15:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{mao_et_al:LIPIcs.WABI.2017.15,
  author =	{Mao, Shunfu and Mohajer, Soheil and Ramachandran, Kannan and Tse, David and Kannan, Sreeram},
  title =	{{abSNP: RNA-Seq SNP Calling in Repetitive Regions via Abundance Estimation}},
  booktitle =	{17th International Workshop on Algorithms in Bioinformatics (WABI 2017)},
  pages =	{15:1--15:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-050-7},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{88},
  editor =	{Schwartz, Russell and Reinert, Knut},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2017.15},
  URN =		{urn:nbn:de:0030-drops-76582},
  doi =		{10.4230/LIPIcs.WABI.2017.15},
  annote =	{Keywords: RNA-Seq, SNP Calling, Repetitive Region, Multiply Mapped Reads, Abundance Estimation}
}

Search Results

Documents authored by Tse, David

A Circuit Approach to Constructing Blockchains on Blockchains

Abstract

Cite as

abSNP: RNA-Seq SNP Calling in Repetitive Regions via Abundance Estimation

Abstract

Cite as

Thanks for your feedback!

Could not send message