DNA physical mapping and alternating Eulerian cycles in colored graphs

DOI10.1007/BF01188582zbMath0840.92011OpenAlexW2021134019MaRDI QIDQ1902468

Pavel A. Pevzner

Publication date: 1 July 1996

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01188582

zbMATH Keywords

DNA physical mappingmolecular biologydouble digest problemalternating Eulerian cyclescassette transformationscombinatorics of multiple solutionsenzyme sitesequivalent physical mapsorder transformationsword transformations

Mathematics Subject Classification ID

Applications of graph theory (05C90) Combinatorics on words (68R15) Graph theory (including graph drawing) in computer science (68R10) Biochemistry, molecular biology (92C40) Coloring of graphs and hypergraphs (05C15)

Related Items

Some algorithmic results for finding compatible spanning circuits in edge-colored graphs ⋮ Exact approaches for the orderly colored longest path problem: performance comparison ⋮ Acyclicity in edge-colored graphs ⋮ A BRACKET POLYNOMIAL FOR GRAPHS, IV: UNDIRECTED EULER CIRCUITS, GRAPH-LINKS AND MULTIPLY MARKED GRAPHS ⋮ Paths and trails in edge-colored graphs ⋮ Mathematical programming approaches for classes of random network problems ⋮ Alternating-pancyclism in 2-edge-colored graphs ⋮ Sorting genomes by prefix double-cut-and-joins ⋮ A generalization of properly colored paths and cycles in edge-colored graphs ⋮ Proper cycles and rainbow cycles in 2-triangle-free edge-colored complete graphs ⋮ Properly colored cycles in edge-colored 2-colored-triangle-free complete graphs ⋮ Parallel connectivity in edge-colored complete graphs: complexity results ⋮ Eulerian Circuits with No Monochromatic Transitions in Edge-Colored Digraphs with all Vertices of Outdegree Three ⋮ Linear amortized time enumeration algorithms for compatible Euler trails in edge-colored graphs ⋮ Sufficient conditions for the existence of spanning colored trees in edge-colored graphs ⋮ Hidden Hamiltonian Cycle Recovery via Linear Programming ⋮ Finite automata for testing composition-based reconstructibility of sequences ⋮ Binary matroids and local complementation ⋮ The edge-recoloring cost of monochromatic and properly edge-colored paths and cycles ⋮ A BRACKET POLYNOMIAL FOR GRAPHS, II: LINKS, EULER CIRCUITS AND MARKED GRAPHS ⋮ Characterizing the reconstruction and enumerating the patterns of DNA sequences with re\-peats ⋮ Chinese postman problem on edge-colored multigraphs ⋮ Compatible Eulerian circuits in Eulerian (di)graphs with generalized transition systems ⋮ Links in edge-colored graphs ⋮ A new sufficient condition for the existence of alternating Hamiltonian cycles in 2-edge-colored multigraphs ⋮ The interlace polynomial of a graph ⋮ Cycles and paths in edge‐colored graphs with given degrees ⋮ Shuffling biological sequences ⋮ Graph traversals, genes and matroids: An efficient case of the travelling salesman problem ⋮ On s-t paths and trails in edge-colored graphs ⋮ Vertex alternating-pancyclism in 2-edge-colored generalized sums of graphs ⋮ Euler circuits and DNA sequencing by hybridization ⋮ Some conditions for the existence of Euler \(H\)-trails ⋮ Gene assembly through cyclic graph decomposition

Uses Software

• DNASUN

Cites Work

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item