Linear-Time Reconstruction of Zero-Recombinant Mendelian Inheritance on Pedigrees without Mating Loops
スポンサーリンク
概要
- 論文の詳細を見る
With the launch of the international HapMap project, the haplotype inference problem has attracted a great deal of attention in the computational biology community recently. In this paper, we study the question of how to efficiently infer haplotypes from genotypes of individuals related by a pedigree <I>without mating loops</I>, assuming that the hereditary process was free of mutations (<I>i. e</I>. the Mendelian law of inheritance) and recombinants. We model the haplotype inference problem as a system of linear equations as in [10] and present an (optimal) linear-time (<I>i. e. O</I> (<I>mn</I>) time) algorithm to generate a <I>particular solution</I> to the haplotype inference problem, where <I>m</I> is the number of loci (or markers) in a genotype and <I>n</I> is the number of individuals in the pedigree. Moreover, the algorithm also provides a <I>general solution</I> in <I>O</I> (<I>mn</I><SUP>2</SUP>) time, which is optimal because the size of a general solution could be as large as Θ (<I>mn</I><SUP>2</SUP>). The key ingredients of our construction are (i) a fast consistency checking procedure for the system of linear equations introduced in [10] based on a careful investigation of the relationship between the equations (ii) a novel linear-time method for solving linear equations without invoking the Gaussian elimination method. Although such a fast method for solving equations is not known for general systems of linear equations, we take advantage of the underlying loop-free pedigree graph and some special properties of the linear equations.
- 日本バイオインフォマティクス学会の論文
日本バイオインフォマティクス学会 | 論文
- Performance Improvement in Protein N-Myristoyl Classification by BONSAI with Insignificant Indexing Symbol
- A combined pathway to simulate CDK-dependent phosphorylation and ARF-dependent stabilization for p53 transcriptional activity
- A versatile petri net based architecture for modeling and simulation of complex biological processes
- XML documentation of biopathways and their simulations in Genomic Object Net
- Prediction of debacle points for robustness of biological pathways by using recurrent neural networks