Complexity of DNA sequencing by hybridization.

DOI10.1016/S0304-3975(02)00063-4zbMath1044.68065OpenAlexW1988981027WikidataQ57387805 ScholiaQ57387805MaRDI QIDQ1401172

Jacek Błażewicz, Marta Kasprzak

Publication date: 17 August 2003

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0304-3975(02)00063-4

zbMATH Keywords

Computational biologyComputational complexityDNA sequencing

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computing methodologies and applications (68U99)

Related Items (20)

Unified encoding for hyper-heuristics with application to bioinformatics ⋮ Tabu search algorithm for DNA sequencing by hybridization with multiplicity information available ⋮ A hyper-heuristic approach to sequencing by hybridization of DNA sequences ⋮ Dealing with repetitions in sequencing by hybridization ⋮ Graph algorithms for DNA sequencing -- origins, current models and the future ⋮ A hybrid algorithm for the DNA sequencing problem ⋮ An integer programming approach to DNA sequence assembly ⋮ Advancing Shannon entropy for measuring diversity in systems ⋮ A polynomial time equivalence between DNA sequencing and the exact perfect matching problem ⋮ Characterizing the reconstruction and enumerating the patterns of DNA sequences with re\-peats ⋮ Finding Hamiltonian circuits in quasi-adjoint graphs ⋮ A greedy algorithm for the DNA sequencing by hybridization with positive and negative errors and information about repetitions ⋮ An ant colony optimization algorithm for DNA sequencing by hybridization ⋮ Computational complexity of isothermic DNA sequencing by hybridization ⋮ Tabu search algorithm for DNA sequencing by hybridization with isothermic libraries ⋮ Sequencing by hybridization with isothermic oligonucleotide libraries ⋮ Selected combinatorial problems of computational biology ⋮ Combinatorial optimization in DNA mapping — a computational thread of the Simplified Partial Digest Problem ⋮ A tissue \(P\) system and a DNA microfluidic device for solving the shortest common superstring problem ⋮ Evolutionary approaches to DNA sequencing with errors

Cites Work

• On finding minimal length superstrings
• On the recognition of de Bruijn graphs and their induced subgraphs
• Tabu search for DNA sequencing with false negatives and false positives
• On some properties of DNA graphs
• The NP-completeness column: An ongoing guide
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Complexity of DNA sequencing by hybridization.