Document Detail

Parameterised algorithms of the individual haplotyping problem with gaps.
MedLine Citation:
PMID:  23207996     Owner:  NLM     Status:  In-Data-Review    
The individual haplotyping problem is the computational problem of constructing two haplotypes from one's DNA fragments. We proposed parameterised algorithms for computational models Minimum SNP Removal (MSR) and Minimum Fragment Removal (MFR) of the problem. For m DNA fragments and n SNPs, our algorithms solve MSR and MFR in O(2<SUP align="right"><small>k</small>nk<SUB align="right"><small>1</small>k<SUB align="right"><small>2</small>+mlogm+nk<SUB align="right"><small>2</small>+mk<SUB align="right"><small>1</small>) and O(mk<SUB align="right"><small>1</small>k<SUB align="right"><small>2</small>2<SUP align="right"><small>k</small>+2<SUP align="right"><small>3k</small>mk<SUB align="right"><small>2</small><SUP align="right"><small>2</small>+mlogm+nk<SUB align="right"><small>2</small>+mk<SUB align="right"><small>1</small>) time respectively, where k<SUB align="right"><small>1</small> is the maximum fragment length, k<SUB align="right"><small>2</small> is the maximum number of fragments covering a SNP site and k is the maximum number of holes in a fragment. Since k<SUB align="right"><small>1</small> and k<SUB align="right"><small>2</small> are both small in practice, our algorithms are efficient and applicable.
Minzhu Xie; Jing Wang
Related Documents :
20429526 - High-accuracy measurements of oh reaction rate constants and ir absorption spectra: ch2...
19872936 - The kinetics of penetration : xii. hydrogen sulfide.
17561776 - Cyclooctane tropospheric degradation initiated by reaction with c1 atoms.
16851486 - Kinetic study of the quenching reaction of singlet oxygen by flavonoids in ethanol solu...
21522606 - Bis{(e)-2-[(2-chloro-3-pyrid-yl)imino-meth-yl]-6-meth-oxy-phenolato-κn,o}copper(ii).
15134726 - Charge-transfer photolysis of copper(ii) dithiocarbamate mixed-ligand complexes in tolu...
Publication Detail:
Type:  Journal Article    
Journal Detail:
Title:  International journal of bioinformatics research and applications     Volume:  9     ISSN:  1744-5485     ISO Abbreviation:  Int J Bioinform Res Appl     Publication Date:  2013  
Date Detail:
Created Date:  2012-12-04     Completed Date:  -     Revised Date:  -    
Medline Journal Info:
Nlm Unique ID:  101253758     Medline TA:  Int J Bioinform Res Appl     Country:  Switzerland    
Other Details:
Languages:  eng     Pagination:  25-40     Citation Subset:  IM    
College of Physics and Information Science, Hunan Normal University, Changsha 410081, China; School of Information Science and Engineering, Central South University, Changsha 410083, China.
Export Citation:
APA/MLA Format     Download EndNote     Download BibTex
MeSH Terms

From MEDLINE®/PubMed®, a database of the U.S. National Library of Medicine

Previous Document:  A heuristic algorithm for haplotype reconstruction from aligned weighted SNP fragments.
Next Document:  A simple statistical method for discrimination of thermophilic and mesophilic proteins based on amin...