Limits...
Ensemble analysis of adaptive compressed genome sequencing strategies.

Taghavi Z - BMC Bioinformatics (2014)

Bottom Line: In this paper, we propose an adaptive compressed method, also known as distilled sensing, to capture all distinct genomes in a sparse microbial community with reduced sequencing effort.Our results suggest that the expected total sequenced nucleotides grows proportional to log of the number of cells and proportional linearly with the number of distinct genomes.The probability of missing a genome depends on its abundance and the ratio of its size over the maximum genome size in the sample.

View Article: PubMed Central - HTML - PubMed

ABSTRACT

Background: Acquiring genomes at single-cell resolution has many applications such as in the study of microbiota. However, deep sequencing and assembly of all of millions of cells in a sample is prohibitively costly. A property that can come to rescue is that deep sequencing of every cell should not be necessary to capture all distinct genomes, as the majority of cells are biological replicates. Biologically important samples are often sparse in that sense. In this paper, we propose an adaptive compressed method, also known as distilled sensing, to capture all distinct genomes in a sparse microbial community with reduced sequencing effort. As opposed to group testing in which the number of distinct events is often constant and sparsity is equivalent to rarity of an event, sparsity in our case means scarcity of distinct events in comparison to the data size. Previously, we introduced the problem and proposed a distilled sensing solution based on the breadth first search strategy. We simulated the whole process which constrained our ability to study the behavior of the algorithm for the entire ensemble due to its computational intensity.

Results: In this paper, we modify our previous breadth first search strategy and introduce the depth first search strategy. Instead of simulating the entire process, which is intractable for a large number of experiments, we provide a dynamic programming algorithm to analyze the behavior of the method for the entire ensemble. The ensemble analysis algorithm recursively calculates the probability of capturing every distinct genome and also the expected total sequenced nucleotides for a given population profile. Our results suggest that the expected total sequenced nucleotides grows proportional to log of the number of cells and proportional linearly with the number of distinct genomes. The probability of missing a genome depends on its abundance and the ratio of its size over the maximum genome size in the sample. The modified resource allocation method accommodates a parameter to control that probability.

Availability: The squeezambler 2.0 C++ source code is available at http://sourceforge.net/projects/hyda/.

Show MeSH
DFS algorithm example. The adaptive depth first search algorithm for anexample with 10 cells and 3 distinct genomes shown in different colors. Eachrow corresponds to one sequencing round. Yellow boxes represent leaves.
© Copyright Policy - open-access
Related In: Results  -  Collection

License 1 - License 2
getmorefigures.php?uid=PMC4221792&req=5

Figure 1: DFS algorithm example. The adaptive depth first search algorithm for anexample with 10 cells and 3 distinct genomes shown in different colors. Eachrow corresponds to one sequencing round. Yellow boxes represent leaves.

Mentions: For both search strategies, all subsets in will be divided to two almost equal size subsets, whichconcludes iteration i. This algorithm will continue until and are empty. Figures 1 and 2 depict examples of the DFS and BFS strategies on 10 cells with 3distinct genomes shown in different colors.


Ensemble analysis of adaptive compressed genome sequencing strategies.

Taghavi Z - BMC Bioinformatics (2014)

DFS algorithm example. The adaptive depth first search algorithm for anexample with 10 cells and 3 distinct genomes shown in different colors. Eachrow corresponds to one sequencing round. Yellow boxes represent leaves.
© Copyright Policy - open-access
Related In: Results  -  Collection

License 1 - License 2
Show All Figures
getmorefigures.php?uid=PMC4221792&req=5

Figure 1: DFS algorithm example. The adaptive depth first search algorithm for anexample with 10 cells and 3 distinct genomes shown in different colors. Eachrow corresponds to one sequencing round. Yellow boxes represent leaves.
Mentions: For both search strategies, all subsets in will be divided to two almost equal size subsets, whichconcludes iteration i. This algorithm will continue until and are empty. Figures 1 and 2 depict examples of the DFS and BFS strategies on 10 cells with 3distinct genomes shown in different colors.

Bottom Line: In this paper, we propose an adaptive compressed method, also known as distilled sensing, to capture all distinct genomes in a sparse microbial community with reduced sequencing effort.Our results suggest that the expected total sequenced nucleotides grows proportional to log of the number of cells and proportional linearly with the number of distinct genomes.The probability of missing a genome depends on its abundance and the ratio of its size over the maximum genome size in the sample.

View Article: PubMed Central - HTML - PubMed

ABSTRACT

Background: Acquiring genomes at single-cell resolution has many applications such as in the study of microbiota. However, deep sequencing and assembly of all of millions of cells in a sample is prohibitively costly. A property that can come to rescue is that deep sequencing of every cell should not be necessary to capture all distinct genomes, as the majority of cells are biological replicates. Biologically important samples are often sparse in that sense. In this paper, we propose an adaptive compressed method, also known as distilled sensing, to capture all distinct genomes in a sparse microbial community with reduced sequencing effort. As opposed to group testing in which the number of distinct events is often constant and sparsity is equivalent to rarity of an event, sparsity in our case means scarcity of distinct events in comparison to the data size. Previously, we introduced the problem and proposed a distilled sensing solution based on the breadth first search strategy. We simulated the whole process which constrained our ability to study the behavior of the algorithm for the entire ensemble due to its computational intensity.

Results: In this paper, we modify our previous breadth first search strategy and introduce the depth first search strategy. Instead of simulating the entire process, which is intractable for a large number of experiments, we provide a dynamic programming algorithm to analyze the behavior of the method for the entire ensemble. The ensemble analysis algorithm recursively calculates the probability of capturing every distinct genome and also the expected total sequenced nucleotides for a given population profile. Our results suggest that the expected total sequenced nucleotides grows proportional to log of the number of cells and proportional linearly with the number of distinct genomes. The probability of missing a genome depends on its abundance and the ratio of its size over the maximum genome size in the sample. The modified resource allocation method accommodates a parameter to control that probability.

Availability: The squeezambler 2.0 C++ source code is available at http://sourceforge.net/projects/hyda/.

Show MeSH