On some properties of DNA graphs

DOI10.1016/S0166-218X(99)00109-2zbMath0939.05078WikidataQ57387847 ScholiaQ57387847MaRDI QIDQ1961230

Daniel Kobler, Dominique de Werra, Jacek Błażewicz, Alain Hertz

Publication date: 29 June 2000

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

zbMATH Keywords

DNA; recognition algorithms; protein structure and functions

Mathematics Subject Classification ID

05C90: Applications of graph theory

92D20: Protein sequences, DNA sequences

Related Items

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, On a graph-theoretical model for cyclic register allocation, Complexity of DNA sequencing by hybridization., Recognizing DNA graphs is difficult., Embedding on alphabet overlap digraphs, Characterizations for some types of DNA 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

Cites Work

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