On some properties of DNA graphs

DOI10.1016/S0166-218X(99)00109-2MaRDI QIDQ1961230zbMATH OpenDBLPWikidataFDO

Authors Alain Hertz, Daniel Kobler, Dominique De Werra, Jacek Blazewicz

Publication date 29 June 2000

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

Full work available at URL https://doi.org/10.1016/S0166-218X(99)00109-2

zbMATH Keywords

DNAprotein structure and functionsrecognition algorithms

Mathematics Subject Classification ID

Applications of graph theory (05C90) Protein sequences, DNA sequences (92D20)

Review text

The authors study properties of DNA graphs, i.e. graphs where each vertex has a label of length \(k\) written with an alphabet of size \(\alpha\), where \(k\) and \(\alpha\) are parameters.

Recommendations

• Characterizations for some types of DNA graphs
• The labeling of some DNA graphs
• DNA labelled graphs with DNA computing
• scientific article; zbMATH DE number 5951415
• DNA graph characterization for line digraph of dicycle with one chord

Cites work

• Depth-First Search and Linear Graph Algorithms
• Monge and feasibility sequences in general flow problems

Cited in

(39)

• On a graph-theoretical model for cyclic register allocation
• Complexity of DNA sequencing by hybridization.
• Graph algorithms for DNA sequencing -- origins, current models and the future
• Classification of de Bruijn-based labeled digraphs
• On directed covering and domination problems
• A method for constructing artificial DNA libraries based on generalized de Bruijn sequences
• Recognizing DNA graphs is difficult.
• DNA physical mapping and alternating Eulerian cycles in colored graphs
• Structure of the space of taboo-free sequences
• Embedding on alphabet overlap digraphs
• Edge-outer graph embedding and the complexity of the DNA reporter strand problem
• Characterizations for some types of DNA graphs
• DNA graph characterization for line digraph of dicycle with one chord
• Four-regular graphs with rigid vertices associated to DNA recombination
• On a generalized model of labeled graphs
• A characterization of partial directed line graphs
• A polynomial time equivalence between DNA sequencing and the exact perfect matching problem
• Characterizing the reconstruction and enumerating the patterns of DNA sequences with re\-peats
• The adjoints of DNA graphs
• Computational complexity of isothermic DNA sequencing by hybridization
• Some indices of alphabet overlap graph
• On the circumference of 3-connected cubic triangle-free plane graphs
• On the readability of overlap digraphs
• On the Readability of Overlap Digraphs
• On -overlap graphs
• scientific article; zbMATH DE number 5951415 (Why is no real title available?)
• The labeling of some DNA graphs
• scientific article; zbMATH DE number 5526120 (Why is no real title available?)
• scientific article; zbMATH DE number 1974594 (Why is no real title available?)
• On directed covering and domination problems
• Flexible Word Design and Graph Labeling
• Bipartite graphs of small readability
• Beyond quasi-adjoint graphs: on polynomial-time solvable cases of the Hamiltonian cycle and path problems
• Sequencing by hybridization with isothermic oligonucleotide libraries
• Selected combinatorial problems of computational biology
• Dealing with repetitions in sequencing by hybridization
• DNA labelled graphs with DNA computing
• Finding Hamiltonian circuits in quasi-adjoint graphs
• On the complexity of recognizing directed path families

This page was built for publication: On some properties of DNA graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1961230)