Classification of de Bruijn-based labeled digraphs

DOI10.1016/j.dam.2016.10.014zbMath1376.05134OpenAlexW2550825112WikidataQ115198416 ScholiaQ115198416MaRDI QIDQ1686053

Marta Kasprzak

Publication date: 20 December 2017

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2016.10.014

zbMATH Keywords

DNA sequence assemblydirected line graphalphabet overlap digraphDNA graphHamiltonian cycle/path problemquasi-adjoint graph

Mathematics Subject Classification ID

Applications of graph theory (05C90) Protein sequences, DNA sequences (92D20) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Directed graphs (digraphs), tournaments (05C20) Eulerian and Hamiltonian graphs (05C45) Graph operations (line graphs, products, etc.) (05C76)

Related Items

A method for constructing artificial DNA libraries based on generalized de Bruijn sequences, Bipartite graphs of small readability

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the readability of overlap digraphs
• Sequencing by hybridization with isothermic oligonucleotide libraries
• Finding Hamiltonian circuits in quasi-adjoint graphs
• On the complexity of recognizing directed path families
• The edge Hamiltonian path problem is NP-complete
• On the complexity of hamiltonian path and cycle problems in certain classes of digraphs
• On the recognition of de Bruijn graphs and their induced subgraphs
• Recognizing DNA graphs is difficult.
• Combinatorial algorithms for DNA sequence assembly
• On some properties of DNA graphs
• Embedding on alphabet overlap digraphs
• Characterizations for some types of DNA graphs
• On a generalized model of labeled graphs
• A characterization of partial directed line graphs
• The adjoints of DNA graphs
• Computational complexity of isothermic DNA sequencing by hybridization
• Reduced-by-matching Graphs: Toward Simplifying Hamiltonian Circuit Problem
• A polynomial algorithm for the Hamiltonian cycle problem in semicomplete multipartite digraphs
• Exact solution of the generalized routing problem through graph transformations