↓ Skip to main content

A new algorithm for “the LCS problem” with application in compressing genome resequencing data

Overview of attention for article published in BMC Genomics, August 2016
Altmetric Badge

Mentioned by

twitter
1 tweeter

Citations

dimensions_citation
13 Dimensions

Readers on

mendeley
9 Mendeley
You are seeing a free-to-access but limited selection of the activity Altmetric has collected about this research output. Click here to find out more.
Title
A new algorithm for “the LCS problem” with application in compressing genome resequencing data
Published in
BMC Genomics, August 2016
DOI 10.1186/s12864-016-2793-0
Pubmed ID
Authors

Richard Beal, Tazin Afrin, Aliya Farheen, Donald Adjeroh

Abstract

The longest common subsequence (LCS) problem is a classical problem in computer science, and forms the basis of the current best-performing reference-based compression schemes for genome resequencing data. First, we present a new algorithm for the LCS problem. Using the generalized suffix tree, we identify the common substrings shared between the two input sequences. Using the maximal common substrings, we construct a directed acyclic graph (DAG), based on which we determine the LCS as the longest path in the DAG. Then, we introduce an LCS-motivated reference-based compression scheme using the components of the LCS, rather than the LCS itself. Our basic scheme compressed the Homo sapiens genome (with an original size of 3,080,436,051 bytes) to 15,460,478 bytes. An improvement on the basic method further reduced this to 8,556,708 bytes, or an overall compression ratio of 360. This can be compared to the previous state-of-the-art compression ratios of 157 (Wang and Zhang, 2011) and 171 (Pinho, Pratas, and Garcia, 2011). We propose a new algorithm to address the longest common subsequence problem. Motivated by our LCS algorithm, we introduce a new reference-based compression scheme for genome resequencing data. Comparative results against state-of-the-art reference-based compression algorithms demonstrate the performance of the proposed method.

Twitter Demographics

The data shown below were collected from the profile of 1 tweeter who shared this research output. Click here to find out more about how the information was compiled.

Mendeley readers

The data shown below were compiled from readership statistics for 9 Mendeley readers of this research output. Click here to see the associated Mendeley record.

Geographical breakdown

Country Count As %
Unknown 9 100%

Demographic breakdown

Readers by professional status Count As %
Student > Master 3 33%
Unspecified 1 11%
Student > Doctoral Student 1 11%
Other 1 11%
Student > Ph. D. Student 1 11%
Other 1 11%
Unknown 1 11%
Readers by discipline Count As %
Computer Science 4 44%
Engineering 2 22%
Medicine and Dentistry 1 11%
Biochemistry, Genetics and Molecular Biology 1 11%
Unknown 1 11%

Attention Score in Context

This research output has an Altmetric Attention Score of 1. This is our high-level measure of the quality and quantity of online attention that it has received. This Attention Score, as well as the ranking and number of research outputs shown below, was calculated when the research output was last mentioned on 25 August 2016.
All research outputs
#13,645,637
of 15,466,991 outputs
Outputs from BMC Genomics
#7,562
of 8,730 outputs
Outputs of similar age
#223,432
of 265,829 outputs
Outputs of similar age from BMC Genomics
#45
of 52 outputs
Altmetric has tracked 15,466,991 research outputs across all sources so far. This one is in the 1st percentile – i.e., 1% of other outputs scored the same or lower than it.
So far Altmetric has tracked 8,730 research outputs from this source. They receive a mean Attention Score of 4.3. This one is in the 1st percentile – i.e., 1% of its peers scored the same or lower than it.
Older research outputs will score higher simply because they've had more time to accumulate mentions. To account for age we can compare this Altmetric Attention Score to the 265,829 tracked outputs that were published within six weeks on either side of this one in any source. This one is in the 1st percentile – i.e., 1% of its contemporaries scored the same or lower than it.
We're also able to compare this research output to 52 others from the same source and published within six weeks on either side of this one. This one is in the 1st percentile – i.e., 1% of its contemporaries scored the same or lower than it.