Dataset Information

Breaking Lander-Waterman's Coverage Bound.

ABSTRACT: Lander-Waterman's coverage bound establishes the total number of reads required to cover the whole genome of size G bases. In fact, their bound is a direct consequence of the well-known solution to the coupon collector's problem which proves that for such genome, the total number of bases to be sequenced should be O(G ln G). Although the result leads to a tight bound, it is based on a tacit assumption that the set of reads are first collected through a sequencing process and then are processed through a computation process, i.e., there are two different machines: one for sequencing and one for processing. In this paper, we present a significant improvement compared to Lander-Waterman's result and prove that by combining the sequencing and computing processes, one can re-sequence the whole genome with as low as O(G) sequenced bases in total. Our approach also dramatically reduces the required computational power for the combined process. Simulation results are performed on real genomes with different sequencing error rates. The results support our theory predicting the log G improvement on coverage bound and corresponding reduction in the total number of bases required to be sequenced.

SUBMITTER: Nashta-Ali D

PROVIDER: S-EPMC5091917 | biostudies-literature | 2016

REPOSITORIES: biostudies-literature

ACCESS DATA

Publications

Breaking Lander-Waterman's Coverage Bound.

Nashta-Ali Damoun D Motahari Seyed Abolfazl SA Hosseinkhalaj Babak B

PloS one 20161102 11

Lander-Waterman's coverage bound establishes the total number of reads required to cover the whole genome of size G bases. In fact, their bound is a direct consequence of the well-known solution to the coupon collector's problem which proves that for such genome, the total number of bases to be sequenced should be O(G ln G). Although the result leads to a tight bound, it is based on a tacit assumption that the set of reads are first collected through a sequencing process and then are processed t ...[more]

PMID: 27806058

Similar Datasets

Project description:An exciting and novel science mission concept called Seismic and Atmospheric Exploration of Venus (SAEVe) has been developed which uses high-temperature electronics to enable a three-order magnitude increase in expected surface life (120 Earth days) over what has been achieved to date. This enables study of long-term, variable phenomena such as the seismicity of Venus and near surface weather, near surface energy balance, and atmospheric chemical composition. SAEVe also serves as a critical pathfinder for more sophisticated landers in the future. For example, first order seismic measurements by SAEVe will allow future missions to deliver better seismometers and systems to support the yet unknown frequency and magnitude of Venus events. SAEVe is focused on science that can be realized with low data volume instruments and will most benefit from temporal operations. The entire mission architecture and operations maximize science while minimizing energy usage and physical size and mass. The entire SAEVe system including its protective entry system is estimated to be around 45 kg and approximately 0.6 m diameter. These features allow SAEVe to be relatively cost effective and be easily integrated onto a Venus orbiter mission. The technologies needed to implement SAEVe are currently in development by several funded activities. Component and system level work is ongoing under NASA's Long Lived Insitu Solar System Explorer (LLISSE) project and the HOTTech program. . LLISSE, is a NASA project to develop a small Venus lander that will operate on the surface of Venus for 60 days and measure variations in meteorology, radiance, and atmospheric chemistry. LLISSE is developing a full-function engineering model of a Venus lander that contains essentially all the core capabilities of SAEVe thus greatly reducing the technology risk to SAEVe. The SAEVe long duration Venus lander promises exciting new science and is an ideal complimentary element to many future Venus orbiter missions being proposed or planned today.

Dataset Information

Breaking Lander-Waterman's Coverage Bound.

Publications

Breaking Lander-Waterman's Coverage Bound.

Similar Datasets

OmicsDI is part of the ELIXIR infrastructure

Tweets