Euler circuits and DNA sequencing by hybridization

DOI10.1016/S0166-218X(00)00190-6zbMath0997.92014OpenAlexW2089913552WikidataQ127109797 ScholiaQ127109797MaRDI QIDQ1585320

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

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

zbMATH Keywords

Catalan numberpairinghybridizationDNA sequencingBEST theoremmatrix-tree theoremcircle graphEuler pathEuler circuitinterlace graph

Mathematics Subject Classification ID

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

Related Items (21)

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

Uses Software

• OEIS

Cites Work

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

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