DNA physical mapping and alternating Eulerian cycles in colored graphs

DOI10.1007/BF01188582zbMath0840.92011MaRDI QIDQ1902468

Pavel A. Pevzner

Publication date: 1 July 1996

Published in: Algorithmica (Search for Journal in Brave)

zbMATH Keywords

DNA physical mapping; molecular biology; double digest problem; alternating Eulerian cycles; cassette transformations; combinatorics of multiple solutions; enzyme sites; equivalent physical maps; order transformations; word transformations

Mathematics Subject Classification ID

05C90: Applications of graph theory

68R15: Combinatorics on words

68R10: Graph theory (including graph drawing) in computer science

92C40: Biochemistry, molecular biology

05C15: Coloring of graphs and hypergraphs

Related Items

Shuffling biological sequences, Sufficient conditions for the existence of spanning colored trees in edge-colored graphs, The interlace polynomial of a graph, Finite automata for testing composition-based reconstructibility of sequences, Links in edge-colored graphs, Graph traversals, genes and matroids: An efficient case of the travelling salesman problem, Euler circuits and DNA sequencing by hybridization, Gene assembly through cyclic graph decomposition, Paths and trails in edge-colored graphs, Characterizing the reconstruction and enumerating the patterns of DNA sequences with re\-peats, Cycles and paths in edge‐colored graphs with given degrees, A BRACKET POLYNOMIAL FOR GRAPHS, IV: UNDIRECTED EULER CIRCUITS, GRAPH-LINKS AND MULTIPLY MARKED GRAPHS, A BRACKET POLYNOMIAL FOR GRAPHS, II: LINKS, EULER CIRCUITS AND MARKED GRAPHS

Uses Software

• DNASUN

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Interval graphs and maps of DNA
• Mapping DNA by stochastic relaxation
• Computing Eulerian trails
• Multiple solutions of DNA restriction mapping problems
• Approximate string-matching with \(q\)-grams and maximal matches
• A lower bound on the number of solutions to the probed partial digest problem
• Transformations of Euler Tours