Loading...
Please wait, while we are loading the content...
Similar Documents
deBGR: an efficient and near-exact representation of the weighted de Bruijn graph
| Content Provider | Semantic Scholar |
|---|---|
| Author | Pandey, Prashant Bender, Michael A. Johnson, Rob Patro, Robert |
| Copyright Year | 2017 |
| Abstract | Motivation Almost all de novo short-read genome and transcriptome assemblers start by building a representation of the de Bruijn Graph of the reads they are given as input. Even when other approaches are used for subsequent assembly (e.g. when one is using 'long read' technologies like those offered by PacBio or Oxford Nanopore), efficient k -mer processing is still crucial for accurate assembly, and state-of-the-art long-read error-correction methods use de Bruijn Graphs. Because of the centrality of de Bruijn Graphs, researchers have proposed numerous methods for representing de Bruijn Graphs compactly. Some of these proposals sacrifice accuracy to save space. Further, none of these methods store abundance information, i.e. the number of times that each k -mer occurs, which is key in transcriptome assemblers. Results We present a method for compactly representing the weighted de Bruijn Graph (i.e. with abundance information) with essentially no errors. Our representation yields zero errors while increasing the space requirements by less than 18-28% compared to the approximate de Bruijn graph representation in Squeakr. Our technique is based on a simple invariant that all weighted de Bruijn Graphs must satisfy, and hence is likely to be of general interest and applicable in most weighted de Bruijn Graph-based systems. Availability and implementation https://github.com/splatlab/debgr . Contact rob.patro@cs.stonybrook.edu. Supplementary information Supplementary data are available at Bioinformatics online. |
| Starting Page | i133 |
| Ending Page | i141 |
| Page Count | 1 |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | https://ftp.ncbi.nlm.nih.gov/pub/pmc/oa_pdf/92/4b/btx261.PMC5870571.pdf |
| Alternate Webpage(s) | http://www3.cs.stonybrook.edu/~ppandey/files/ISMB17_TALK_deGR_Full.pdf |
| Alternate Webpage(s) | https://oup.silverchair-cdn.com/oup/backfile/Content_public/Journal/bioinformatics/33/14/10.1093_bioinformatics_btx261/2/btx261.pdf?Expires=1501849515&Key-Pair-Id=APKAIUCZBIA4LVPAVW3Q&Signature=ag9gAAtSKR~zksdT9jKLoi6dLdds-u4hZuuf1-Vyqit4htQJdtdSSQJ-72cR3nTmqDbcN1mPoMG8X0AwSTDbC-6rAurzgv~04hfmX8pquI0DU9bR9uqIxt3ukpaW5YzYsFVNw5DifcmyJ46FWwToxAK0w1agytq0BM1LP-FH6ppinBFwg~pOJTP1dz8yyBtl0s3C0MDrljOK5XVwBZPVYIVZk2mW7mEQFU97KURBIpTXBk~3LORusx2sL6nlUH28I930qgy13eiKhztV3T6Ij8BPerehBVUse9xMrFx-1EqvwsojSZBWJqsAVr5hDOHfqbEakhiqIJimz5iS5BGhLQ__ |
| Alternate Webpage(s) | https://oup.silverchair-cdn.com/oup/backfile/Content_public/Journal/bioinformatics/33/14/10.1093_bioinformatics_btx261/2/btx261_Supp.pdf?Expires=1501843171&Key-Pair-Id=APKAIUCZBIA4LVPAVW3Q&Signature=Re0bzkZmd-5NgIe4sWOer8l1f7a2b3u7yfxpde3WWGdRKWQR6Jr7H~0QaHAaZe-YzGd47bhGzGNIPz0eoCMHo5pnloF043PVoNTmz3F-WVJFIBahLHknucTolNCfUru7yb2Mizq--~ji0ObKM2UjwXF08T72EHc0sMRh1PAY0HOO1h7M4HlD9cH8qGSkVGlVDyvjRB8goAki3Fw2dlrlfeFdWlE0FhiRSM-e3EyR8lgJ2xRoInaNGOO7hLwutIS0XiSKfXeQBQbF0YjXFqoXSXRBSC6vqPdPIpdev~Jaorm8ie6nADPTxQPuRol5TBRctrs2fE~wiOOBOYjIuQxXPw__ |
| Alternate Webpage(s) | https://www.wikidata.org/entity/Q42697222 |
| Alternate Webpage(s) | http://www3.cs.stonybrook.edu/~ppandey/files/ISMB17_TALK_deGR.pdf |
| PubMed reference number | 28881995 |
| Alternate Webpage(s) | https://doi.org/10.1093/bioinformatics/btx261 |
| DOI | 10.1093/bioinformatics/btx261 |
| Journal | Bioinformatics |
| Volume Number | 33 |
| Language | English |
| Access Restriction | Open |
| Subject Keyword | Approximation algorithm Arabic numeral 0 Bioinformatics Centrality De Bruijn graph De novo transcriptome assembly Error detection and correction GPER protein, human Geographic Information Systems Graph (abstract data type) Graph - visual representation IBM Notes Laboratory Reading (activity) Requirement Transcript funding grant |
| Content Type | Text |
| Resource Type | Article |
