Assembly-free and alignment-free sample identification using genome skims
Research output: Contribution to journal › Conference abstract in journal › Research › peer-review
Standard
Assembly-free and alignment-free sample identification using genome skims. / Sarmashghi, Shahab; Bohmann, Kristine; Gilbert, M. Thomas P.; Bafna, Vineet; Mirarab, Siavash.
In: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol. 10812, 01.01.2018, p. 276-277.Research output: Contribution to journal › Conference abstract in journal › Research › peer-review
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - ABST
T1 - Assembly-free and alignment-free sample identification using genome skims
AU - Sarmashghi, Shahab
AU - Bohmann, Kristine
AU - Gilbert, M. Thomas P.
AU - Bafna, Vineet
AU - Mirarab, Siavash
PY - 2018/1/1
Y1 - 2018/1/1
N2 - The ability to quickly and inexpensively describe the taxonomic diversity in an environment is critical in this era of rapid climate and biodiversity changes. The currently preferred molecular technique, barcoding, is low-cost and widely used, but has drawbacks. As sequencing costs continue to fall, an alternative approach based on genome-skimming has been proposed [1, 2]. This approach first applies low-pass (100 Mb – several Gb per sample) sequencing to voucher and/or query samples and then recovers marker genes and/or organelle genomes computationally. In contrast, we suggest the use of the unassembled sequence data for taxonomic identification using an alignment-free approach based on the k-mer decomposition of the sequencing reads. Specifically, we first estimate the average sequencing depth and error rate for each genome skim, by comparing our derived theoretical distribution of k-mers’ multiplicity and the histogram of k-mer counts computed using Jellyfish [3]. The genome length is also estimated from the average sequencing depth accordingly. Then, the similarity of two genome skims is measured by the Jaccard index between their corresponding k-mer collections. Finally, the hamming distance between genomes is estimated from the Jaccard index, using the following formula obtained by modeling the impact of low sequencing coverage, sequencing error, and differing genome lengths on the similarity of genome skims: D1/k2(ζ1 L1 + ζ2 L2)J D = 1 ™. η1 η2 (L1 + L2)(1 + J) In this equation, when coverage is low, we use all k-mers and set: ηi = 1 ™ e™ci(1™k/ℓ)(1™ɛi)k, ζi = ηi + ci (1 ™ k/ℓ)(1 ™ (1 ™ ɛi)k). For higher coverages, we remove k-mers with multiplicity below a threshold m, and set: m™1 ∑ (ci (1 ™ k/ℓ)(1 ™ ɛi)k)t ζi = ηi = 1 ™ e™ci(1™k/ℓ)(1™ɛi)k. t! t=0 In these equations, k and ℓ are k-mer and read length, respectively, and ci, ɛi, and Li are substituted from the estimates of coverage, error rate, and genome length for each genome skim. The Jaccard index between two genome skims, J, is computed by Mash [4] efficiently using a hashing technique. We have tested our tool, Skmer, on genome skims simulated from assemblies of 90 species from two genera of insects (Anopheles and Drosophila) and across the avian tree of life. We test the accuracy of the distances computed by Skmer, and subsequently use the distances to find the exact/closest match to a query sample in a reference set of genome skims. Comparing to the other k-mer based tools, Skmer shows excellent performance in our simulation studies, especially when the coverage is below 4X [5]. Skmer makes the assembly-free approach to genome-skimming a viable alternative to the traditional barcoding. The software is made publicly available on Github (https://github.com/shahab-sarmashghi/Skmer.git).
AB - The ability to quickly and inexpensively describe the taxonomic diversity in an environment is critical in this era of rapid climate and biodiversity changes. The currently preferred molecular technique, barcoding, is low-cost and widely used, but has drawbacks. As sequencing costs continue to fall, an alternative approach based on genome-skimming has been proposed [1, 2]. This approach first applies low-pass (100 Mb – several Gb per sample) sequencing to voucher and/or query samples and then recovers marker genes and/or organelle genomes computationally. In contrast, we suggest the use of the unassembled sequence data for taxonomic identification using an alignment-free approach based on the k-mer decomposition of the sequencing reads. Specifically, we first estimate the average sequencing depth and error rate for each genome skim, by comparing our derived theoretical distribution of k-mers’ multiplicity and the histogram of k-mer counts computed using Jellyfish [3]. The genome length is also estimated from the average sequencing depth accordingly. Then, the similarity of two genome skims is measured by the Jaccard index between their corresponding k-mer collections. Finally, the hamming distance between genomes is estimated from the Jaccard index, using the following formula obtained by modeling the impact of low sequencing coverage, sequencing error, and differing genome lengths on the similarity of genome skims: D1/k2(ζ1 L1 + ζ2 L2)J D = 1 ™. η1 η2 (L1 + L2)(1 + J) In this equation, when coverage is low, we use all k-mers and set: ηi = 1 ™ e™ci(1™k/ℓ)(1™ɛi)k, ζi = ηi + ci (1 ™ k/ℓ)(1 ™ (1 ™ ɛi)k). For higher coverages, we remove k-mers with multiplicity below a threshold m, and set: m™1 ∑ (ci (1 ™ k/ℓ)(1 ™ ɛi)k)t ζi = ηi = 1 ™ e™ci(1™k/ℓ)(1™ɛi)k. t! t=0 In these equations, k and ℓ are k-mer and read length, respectively, and ci, ɛi, and Li are substituted from the estimates of coverage, error rate, and genome length for each genome skim. The Jaccard index between two genome skims, J, is computed by Mash [4] efficiently using a hashing technique. We have tested our tool, Skmer, on genome skims simulated from assemblies of 90 species from two genera of insects (Anopheles and Drosophila) and across the avian tree of life. We test the accuracy of the distances computed by Skmer, and subsequently use the distances to find the exact/closest match to a query sample in a reference set of genome skims. Comparing to the other k-mer based tools, Skmer shows excellent performance in our simulation studies, especially when the coverage is below 4X [5]. Skmer makes the assembly-free approach to genome-skimming a viable alternative to the traditional barcoding. The software is made publicly available on Github (https://github.com/shahab-sarmashghi/Skmer.git).
UR - http://www.scopus.com/inward/record.url?scp=85046131357&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-89929-9
DO - 10.1007/978-3-319-89929-9
M3 - Conference abstract in journal
AN - SCOPUS:85046131357
VL - 10812
SP - 276
EP - 277
JO - Lecture Notes in Bioinformatics
JF - Lecture Notes in Bioinformatics
SN - 1611-3349
T2 - 22nd International Conference on Research in Computational Molecular Biology, RECOMB 2018
Y2 - 21 April 2018 through 24 April 2018
ER -
ID: 214873586