Accurate decoding of pooled sequenced data using compressed sensing

Denisa Duma; Mary Wootters; Anna C. Gilbert; Hung Q. Ngo; Atri Rudra; Matthew Alpert; Timothy J. Close; Gianfranco Ciardo; Stefano Lonardi

doi:10.1007/978-3-642-40453-5_7

Accurate decoding of pooled sequenced data using compressed sensing

Denisa Duma
, Mary Wootters
, Anna C. Gilbert
, Hung Q. Ngo
, Atri Rudra
, Matthew Alpert
, Timothy J. Close
, Gianfranco Ciardo
, Stefano Lonardi

Department of AI and Society

University of California at Riverside
University of Michigan, Ann Arbor
SUNY Buffalo

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

6 Scopus citations

Abstract

In order to overcome the limitations imposed by DNA barcoding when multiplexing a large number of samples in the current generation of high-throughput sequencing instruments, we have recently proposed a new protocol that leverages advances in combinatorial pooling design (group testing) [9]. We have also demonstrated how this new protocol would enable de novo selective sequencing and assembly of large, highly-repetitive genomes. Here we address the problem of decoding pooled sequenced data obtained from such a protocol. Our algorithm employs a synergistic combination of ideas from compressed sensing and the decoding of error-correcting codes. Experimental results on synthetic data for the rice genome and real data for the barley genome show that our novel decoding algorithm enables significantly higher quality assemblies than the previous approach.

Original language	English
Title of host publication	Algorithms in Bioinformatics - 13th International Workshop, WABI 2013, Proceedings
Publisher	Springer Verlag
Pages	70-84
Number of pages	15
ISBN (Print)	9783642404528
DOIs	https://doi.org/10.1007/978-3-642-40453-5_7
State	Published - Jan 1 2013
Event	13th Workshop on Algorithms in Bioinformatics, WABI 2013 - Sophia Antipolis, France Duration: Sep 2 2013 → Sep 4 2013

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	8126 LNBI
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	13th Workshop on Algorithms in Bioinformatics, WABI 2013
Country/Territory	France
City	Sophia Antipolis
Period	09/2/13 → 09/4/13

Keywords

compressed sensing
error-correcting codes
pooled sequencing
second/next-generation sequencing

Access to Document

10.1007/978-3-642-40453-5_7

Cite this

Duma, D., Wootters, M., Gilbert, A. C., Ngo, H. Q., Rudra, A., Alpert, M., Close, T. J., Ciardo, G., & Lonardi, S. (2013). Accurate decoding of pooled sequenced data using compressed sensing. In Algorithms in Bioinformatics - 13th International Workshop, WABI 2013, Proceedings (pp. 70-84). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8126 LNBI). Springer Verlag. https://doi.org/10.1007/978-3-642-40453-5_7

Duma, Denisa ; Wootters, Mary ; Gilbert, Anna C. et al. / Accurate decoding of pooled sequenced data using compressed sensing. Algorithms in Bioinformatics - 13th International Workshop, WABI 2013, Proceedings. Springer Verlag, 2013. pp. 70-84 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{18b1119730ef46df8204e5c10754e0f1,

title = "Accurate decoding of pooled sequenced data using compressed sensing",

abstract = "In order to overcome the limitations imposed by DNA barcoding when multiplexing a large number of samples in the current generation of high-throughput sequencing instruments, we have recently proposed a new protocol that leverages advances in combinatorial pooling design (group testing) [9]. We have also demonstrated how this new protocol would enable de novo selective sequencing and assembly of large, highly-repetitive genomes. Here we address the problem of decoding pooled sequenced data obtained from such a protocol. Our algorithm employs a synergistic combination of ideas from compressed sensing and the decoding of error-correcting codes. Experimental results on synthetic data for the rice genome and real data for the barley genome show that our novel decoding algorithm enables significantly higher quality assemblies than the previous approach.",

keywords = "compressed sensing, error-correcting codes, pooled sequencing, second/next-generation sequencing",

author = "Denisa Duma and Mary Wootters and Gilbert, \{Anna C.\} and Ngo, \{Hung Q.\} and Atri Rudra and Matthew Alpert and Close, \{Timothy J.\} and Gianfranco Ciardo and Stefano Lonardi",

year = "2013",

month = jan,

day = "1",

doi = "10.1007/978-3-642-40453-5\_7",

language = "English",

isbn = "9783642404528",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "70--84",

booktitle = "Algorithms in Bioinformatics - 13th International Workshop, WABI 2013, Proceedings",

address = "Germany",

note = "13th Workshop on Algorithms in Bioinformatics, WABI 2013 ; Conference date: 02-09-2013 Through 04-09-2013",

}

Duma, D, Wootters, M, Gilbert, AC, Ngo, HQ, Rudra, A, Alpert, M, Close, TJ, Ciardo, G & Lonardi, S 2013, Accurate decoding of pooled sequenced data using compressed sensing. in Algorithms in Bioinformatics - 13th International Workshop, WABI 2013, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8126 LNBI, Springer Verlag, pp. 70-84, 13th Workshop on Algorithms in Bioinformatics, WABI 2013, Sophia Antipolis, France, 09/2/13. https://doi.org/10.1007/978-3-642-40453-5_7

Accurate decoding of pooled sequenced data using compressed sensing. / Duma, Denisa; Wootters, Mary; Gilbert, Anna C. et al.
Algorithms in Bioinformatics - 13th International Workshop, WABI 2013, Proceedings. Springer Verlag, 2013. p. 70-84 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8126 LNBI).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Accurate decoding of pooled sequenced data using compressed sensing

AU - Duma, Denisa

AU - Wootters, Mary

AU - Gilbert, Anna C.

AU - Ngo, Hung Q.

AU - Rudra, Atri

AU - Alpert, Matthew

AU - Close, Timothy J.

AU - Ciardo, Gianfranco

AU - Lonardi, Stefano

PY - 2013/1/1

Y1 - 2013/1/1

N2 - In order to overcome the limitations imposed by DNA barcoding when multiplexing a large number of samples in the current generation of high-throughput sequencing instruments, we have recently proposed a new protocol that leverages advances in combinatorial pooling design (group testing) [9]. We have also demonstrated how this new protocol would enable de novo selective sequencing and assembly of large, highly-repetitive genomes. Here we address the problem of decoding pooled sequenced data obtained from such a protocol. Our algorithm employs a synergistic combination of ideas from compressed sensing and the decoding of error-correcting codes. Experimental results on synthetic data for the rice genome and real data for the barley genome show that our novel decoding algorithm enables significantly higher quality assemblies than the previous approach.

AB - In order to overcome the limitations imposed by DNA barcoding when multiplexing a large number of samples in the current generation of high-throughput sequencing instruments, we have recently proposed a new protocol that leverages advances in combinatorial pooling design (group testing) [9]. We have also demonstrated how this new protocol would enable de novo selective sequencing and assembly of large, highly-repetitive genomes. Here we address the problem of decoding pooled sequenced data obtained from such a protocol. Our algorithm employs a synergistic combination of ideas from compressed sensing and the decoding of error-correcting codes. Experimental results on synthetic data for the rice genome and real data for the barley genome show that our novel decoding algorithm enables significantly higher quality assemblies than the previous approach.

KW - compressed sensing

KW - error-correcting codes

KW - pooled sequencing

KW - second/next-generation sequencing

UR - https://www.scopus.com/pages/publications/84884362255

U2 - 10.1007/978-3-642-40453-5_7

DO - 10.1007/978-3-642-40453-5_7

M3 - Conference contribution

AN - SCOPUS:84884362255

SN - 9783642404528

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 70

EP - 84

BT - Algorithms in Bioinformatics - 13th International Workshop, WABI 2013, Proceedings

PB - Springer Verlag

T2 - 13th Workshop on Algorithms in Bioinformatics, WABI 2013

Y2 - 2 September 2013 through 4 September 2013

ER -

Duma D, Wootters M, Gilbert AC, Ngo HQ, Rudra A, Alpert M et al. Accurate decoding of pooled sequenced data using compressed sensing. In Algorithms in Bioinformatics - 13th International Workshop, WABI 2013, Proceedings. Springer Verlag. 2013. p. 70-84. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-40453-5_7

Accurate decoding of pooled sequenced data using compressed sensing

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this