Euler circuits and DNA sequencing by hybridization

DOI10.1016/S0166-218X(00)00190-6MaRDI QIDQ1585320zbMATH OpenOpenAlexWikidataFDO

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

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)

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

Cites work

• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3904630 (Why is no real title available?)
• scientific article; zbMATH DE number 45266 (Why is no real title available?)
• scientific article; zbMATH DE number 52632 (Why is no real title available?)
• scientific article; zbMATH DE number 699389 (Why is no real title available?)
• scientific article; zbMATH DE number 758277 (Why is no real title available?)
• scientific article; zbMATH DE number 1445310 (Why is no real title available?)
• scientific article; zbMATH DE number 3047763 (Why is no real title available?)
• scientific article; zbMATH DE number 3068971 (Why is no real title available?)
• A characterization of circle graphs
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• Approximate string-matching with q-grams and maximal matches
• DNA physical mapping and alternating Eulerian cycles in colored graphs
• Graph traversals, genes and matroids: An efficient case of the travelling salesman problem
• Non-Sexist Solution of the Menage Problem
• On Unicursal Paths in a Network of Degree 4
• Recognition of Circle Graphs
• Recognizing circle graphs in polynomial time
• Shuffling biological sequences
• Two moments suffice for Poisson approximations: The Chen-Stein method

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
• Edge local complementation and equivalence of binary linear codes
• Interlace polynomials of 4n-snowflake graphs
• Computational complexity of isothermic DNA sequencing by hybridization
• scientific article; zbMATH DE number 1445310 (Why is no real title available?)
• 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

Describes a project that uses

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)