| Research on parameterized algorithms of the individual haplotyping problem. | |
| | |
MedLine Citation:
|
PMID: 17688317 Owner: NLM Status: MEDLINE |
Abstract/OtherAbstract:
|
The individual haplotyping problem is a computing problem of reconstructing two haplotypes for an individual based on several optimal criteria from one's fragments sequencing data. This paper is based on the fact that the length of a fragment and the number of the fragments covering a SNP (single nucleotide polymorphism) site are both very small compared with the length of a sequenced region and the total number of the fragments and introduces the parameterized haplotyping problems. With m fragments whose maximum length is k(1), n SNP sites and the number of the fragments covering a SNP site no more than k(2), our algorithms can solve the gapless MSR (Minimum SNP Removal) and MFR (Minimum Fragment Removal) problems in the time complexity O(nk(1)k(2) + m log m + nk(2) + mk(1)) and O(mk(2)(2) + mk(1) k(2) + m log m + nk(2) + mk(1))respectively. Since, the value of k(1) and k(2) are both small (about 10) in practice, our algorithms are more efficient and applicable compared with the algorithms of V. Bafna et al. of time complexity O(mn(2)) and O(m(2)n + m(3)), respectively. |
| | |
Authors:
|
Minzhu Xie; Jian'er Chen; Jianxin Wang |
Related Documents
:
|
10111297 - The clean restaurant. ii: employee hygiene. 11652927 - Towards a non-ecumenical interchange: engelhardt, hauerwas, and ramsey on christian bio... 2280267 - Molecular structure matching by simulated annealing. ii. an exploration of the evolutio... 11527717 - Anti-aids agents. part 47: synthesis and anti-hiv activity of 3-substituted 3',4'-di-o-... 17129927 - Women coping with aids in africa: contributions of a contextually grounded research met... 17487627 - The effect of the communication output method on augmented interaction. |
Publication Detail:
|
Type: Journal Article; Research Support, Non-U.S. Gov't |
Journal Detail:
|
Title: Journal of bioinformatics and computational biology Volume: 5 ISSN: 0219-7200 ISO Abbreviation: J Bioinform Comput Biol Publication Date: 2007 Jun |
Date Detail:
|
Created Date: 2007-08-10 Completed Date: 2007-11-07 Revised Date: - |
Medline Journal Info:
|
Nlm Unique ID: 101187344 Medline TA: J Bioinform Comput Biol Country: England |
Other Details:
|
Languages: eng Pagination: 795-816 Citation Subset: IM |
Affiliation:
|
School of Information Science and Engineering, Central South University, Changsha, Hunan Province 410083, China. xieminzhu@hotmail.com |
Export Citation:
|
APA/MLA Format Download EndNote Download BibTex |
| MeSH Terms | |
Descriptor/Qualifier:
|
Algorithms* Computational Biology* Genome, Human Haplotypes* Humans Models, Genetic Polymorphism, Single Nucleotide Sequence Analysis, DNA / statistics & numerical data |
From MEDLINE®/PubMed®, a database of the U.S. National Library of Medicine
Previous Document: Prediction of transcription factor binding sites using genetical genomics methods.
Next Document: Surface modification of poly(L-lactic acid) membrane via layer-by-layer assembly of silver nanoparti...