Euler circuits and DNA sequencing by hybridization

DOI10.1016/S0166-218X(00)00190-6zbMATH Open0997.92014OpenAlexW2089913552WikidataQ127109797 ScholiaQ127109797MaRDI QIDQ1585320FDOQ1585320

Authors: Richard Arratia, Béla Bollobás, Don Coppersmith, Gregory B. Sorkin 

Publication date: 13 November 2002

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

Full work available at URL: https://doi.org/10.1016/s0166-218x(00)00190-6

Recommendations

• Publication:4952623
• Finding Hamiltonian circuits in quasi-adjoint graphs
• scientific article; zbMATH DE number 1953078
• An Eulerian path approach to DNA fragment assembly
• scientific article; zbMATH DE number 5831723

zbMATH Keywords

Catalan numberhybridizationDNA sequencingBEST theoremmatrix-tree theoremcircle graphpairingEuler pathEuler circuitinterlace graph

Mathematics Subject Classification ID

Applications of graph theory (05C90) Biochemistry, molecular biology (92C40) Protein sequences, DNA sequences (92D20) Asymptotic enumeration (05A16)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Two moments suffice for Poisson approximations: The Chen-Stein method
• Title not available (Why is that?)
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• Title not available (Why is that?)
• On Unicursal Paths in a Network of Degree 4
• Title not available (Why is that?)
• Title not available (Why is that?)
• Recognition of Circle Graphs
• Title not available (Why is that?)
• DNA physical mapping and alternating Eulerian cycles in colored graphs
• Title not available (Why is that?)
• Recognizing circle graphs in polynomial time
• Title not available (Why is that?)
• Approximate string-matching with \(q\)-grams and maximal matches
• A characterization of circle graphs
• Graph traversals, genes and matroids: An efficient case of the travelling salesman problem
• Shuffling biological sequences
• Non-Sexist Solution of the Menage Problem

Cited In (24)

• Wilson loops in terms of color invariants
• Interlace polynomials of lollipop and tadpole graphs
• Distance Hereditary Graphs and the Interlace Polynomial
• The interlace polynomial of a graph
• The interlace polynomial of graphs at \(-1\)
• The number of Euler tours of random directed graphs
• Combinatorics from Bacterial Genomes
• Interlace polynomials of 4n-snowflake graphs
• Edge local complementation and equivalence of binary linear codes
• Computational complexity of isothermic DNA sequencing by hybridization
• Title not available (Why is that?)
• Interlace polynomials of friendship graphs
• Fast evaluation of interlace polynomials on graphs of bounded treewidth
• DNA-inspired information concealing: a survey
• Characterizing the reconstruction and enumerating the patterns of DNA sequences with re\-peats
• Circle graphs and monadic second-order logic
• Formation of a giant component in the intersection graph of a random chord diagram
• On the interlace polynomials of forests
• On graphs and codes preserved by edge local complementation
• An integer programming approach to DNA sequence assembly
• Interlace polynomials: enumeration, unimodality and connections to codes
• Homomorphisms and polynomial invariants of graphs
• The adjoints of DNA graphs
• Sequencing by hybridization with errors: handling longer sequences

Uses Software

• OEIS

This page was built for publication: Euler circuits and DNA sequencing by hybridization

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