Accurate determination of node and arc multiplicities in de bruijn graphs using conditional random fields.
BMC Bioinformatics
; 21(1): 402, 2020 Sep 14.
Article
em En
| MEDLINE
| ID: mdl-32928110
ABSTRACT
BACKGROUND:
De Bruijn graphs are key data structures for the analysis of next-generation sequencing data. They efficiently represent the overlap between reads and hence, also the underlying genome sequence. However, sequencing errors and repeated subsequences render the identification of the true underlying sequence difficult. A key step in this process is the inference of the multiplicities of nodes and arcs in the graph. These multiplicities correspond to the number of times each k-mer (resp. k+1-mer) implied by a node (resp. arc) is present in the genomic sequence. Determining multiplicities thus reveals the repeat structure and presence of sequencing errors. Multiplicities of nodes/arcs in the de Bruijn graph are reflected in their coverage, however, coverage variability and coverage biases render their determination ambiguous. Current methods to determine node/arc multiplicities base their decisions solely on the information in nodes and arcs individually, under-utilising the information present in the sequencing data.RESULTS:
To improve the accuracy with which node and arc multiplicities in a de Bruijn graph are inferred, we developed a conditional random field (CRF) model to efficiently combine the coverage information within each node/arc individually with the information of surrounding nodes and arcs. Multiplicities are thus collectively assigned in a more consistent manner.CONCLUSIONS:
We demonstrate that the CRF model yields significant improvements in accuracy and a more robust expectation-maximisation parameter estimation. True k-mers can be distinguished from erroneous k-mers with a higher F1 score than existing methods. A C++11 implementation is available at https//github.com/biointec/detox under the GNU AGPL v3.0 license.Palavras-chave
Texto completo:
1
Coleções:
01-internacional
Base de dados:
MEDLINE
Assunto principal:
Biologia Computacional
/
Genômica
/
Sequenciamento de Nucleotídeos em Larga Escala
Tipo de estudo:
Clinical_trials
/
Prognostic_studies
Limite:
Humans
Idioma:
En
Revista:
BMC Bioinformatics
Assunto da revista:
INFORMATICA MEDICA
Ano de publicação:
2020
Tipo de documento:
Article
País de afiliação:
Bélgica
País de publicação:
ENGLAND
/
ESCOCIA
/
GB
/
GREAT BRITAIN
/
INGLATERRA
/
REINO UNIDO
/
SCOTLAND
/
UK
/
UNITED KINGDOM