SNPs problems, complexity, and algorithms

DOI10.1007/3-540-44676-1_15MaRDI QIDQ4796705zbMATH OpenFDO

Authors Giuseppe Lancia, Vineet Bafna, Ross A. Lippert, Russell Schwartz, Sorin Istrail

Publication date 20 March 2003

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-44676-1_15

Mathematics Subject Classification ID

Complexity and performance of numerical algorithms (65Y20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorics on words (68R15) Computational methods for problems pertaining to biology (92-08) Genetics and epigenetics (92D10) Protein sequences, DNA sequences (92D20)

Recommendations

• Practical algorithms and fixed-parameter tractability for the single individual SNP haplotyping problem
• A Practical Exact Algorithm for the Individual Haplotyping Problem MEC/GI
• Polynomial and APX-hard cases of the individual haplotyping problem
• Haplotype assembly from aligned weighted SNP fragments
• The complexity of the single individual SNP haplotyping problem

Cited in

(35)

• A practical algorithm based on particle swarm optimization for haplotype reconstruction
• Designing optimally multiplexed SNP genotyping assays
• Polynomial and APX-hard cases of the individual haplotyping problem
• The haplotyping problem: an overview of computational models and solutions
• On the quantity and quality of single nucleotide polymorphisms in the human genome.
• Self-organizing map approaches for the haplotype assembly problem
• An effective haplotype assembly algorithm based on hypergraph partitioning
• A dynamic programming algorithm for the \(k\)-haplotyping problem
• The haplotype assembly model with genotype information and iterative local-exhaustive search algorithm
• The complexity of the single individual SNP haplotyping problem
• Clique-detection models in computational biochemistry and genomics
• Haplotype assembly from aligned weighted SNP fragments
• Reinforcement learning for combinatorial optimization: a survey
• Algorithmic approaches for the single individual haplotyping problem
• On the complexity of MMSNP
• Parameterizing MAX SNP Problems Above Guaranteed Values
• A Practical Parameterized Algorithm for Weighted Minimum Letter Flips Model of the Individual Haplotyping Problem
• Efficient Algorithms for SNP Haplotype Block Selection Problems
• A Practical Exact Algorithm for the Individual Haplotyping Problem MEC/GI
• Phasing of 2-SNP Genotypes Based on Non-random Mating Model
• On the Approximability of Some Haplotyping Problems
• New results for the longest haplotype reconstruction problem
• Solving VLSI design and DNA sequencing problems using bipartization of graphs
• Practical algorithms and fixed-parameter tractability for the single individual SNP haplotyping problem
• scientific article; zbMATH DE number 2040938 (Why is no real title available?)
• Parameterized complexity analysis for the closest string with wildcards problem
• Inductive graph invariants and approximation algorithms
• abSNP: RNA-Seq SNP calling in repetitive regions via abundance estimation
• Computational Methods for SNPs and Haplotype Inference
• Selection of minimum subsets of single nucleotide polymorphisms to capture haplotype block diversity
• scientific article; zbMATH DE number 7651113 (Why is no real title available?)
• A quantum walk-assisted approximate algorithm for bounded NP optimisation problems
• A practical exact algorithm for the individual haplotyping problem MEC/GI
• An improved (and practical) parameterized algorithm for the individual haplotyping problem MFR with mate-pairs
• Finding a maximum-weight induced \(k\)-partite subgraph of an \(i\)-triangulated graph

This page was built for publication: SNPs problems, complexity, and algorithms

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