Document Detail


Parameterised algorithms of the individual haplotyping problem with gaps.
MedLine Citation:
PMID:  23207996     Owner:  NLM     Status:  In-Data-Review    
Abstract/OtherAbstract:
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.
Authors:
Minzhu Xie; Jing Wang
Related Documents :
11878346 - Chemical differentiation in regions of massive star formation.
18962496 - Quinoline-2-aldehyde thiosemicarbazone (qat) as spectrophotometric reagent for palladiu...
11666276 - Equilibrium and kinetics of bromine hydrolysis.
23656556 - 19-[(1's,4'r)-4'-hydroxy-1'-methoxy-2'-oxopentyl]geldanamycin, a natural geldanamycin a...
148036 - 5'-halogeno-2',3'-cyclic sulphite isomers in the preparation of 5'-halogeno nucleosides...
22799496 - Templating quantum dot to phase-transformed electrospun tio₂ nanofibers for enhanced ...
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    
Affiliation:
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
Descriptor/Qualifier:

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...