QQ客服 官方微博 反馈留言

	EFFICIENT ALGORITHMS FOR RECONSTRUCTING ZERO-RECOMBINANT HAPLOTYPES ON A PEDIGREE BASED ON FAST ELIMINATION OF REDUNDANT LINEAR EQUATIONS
	Xiao, Jing ; Liu, Lan ; Xia, Lirong ; Jiang, Tao
	2010-10-12 ; 2010-10-12
关键词	haplotype inference pedigree analysis system of linear equations low-stretch spanning tree HUMAN GENOME TRANSMISSION/DISEQUILIBRIUM TEST LINKAGE ANALYSIS Computer Science, Theory & Methods Mathematics, Applied
中文摘要	Computational inference of haplotypes from genotypes has attracted a great deal of attention in the computational biology community recently, partially driven by the international HapMap project. In this paper, we study the question of how to efficiently infer haplotypes from genotypes of individuals related by a pedigree, assuming that the hereditary process was free of mutations (i.e., the Mendelian law of inheritance) and recombinants. The problem has recently been formulated as a system of linear equations over the finite field of F(2) and solved in O(m(3)n(3)) time by using standard Gaussian elimination, where m is the number of loci (or markers) in a genotype and n the number of individuals in the pedigree. We give a much faster algorithm with running time O(mn(2) + n(3) log(2) n log log n). The key ingredients of our construction are (i) a new system of linear equations based on some spanning tree of the pedigree graph and (ii) an efficient method for eliminating redundant equations in a system of O(mn) linear equations over O(n) variables. Although such a fast elimination method is not known for general systems of linear equations, we take advantage of the underlying pedigree graph structure and recent progress on low-stretch spanning trees.
语种	英语 ; 英语
出版者	SIAM PUBLICATIONS ; PHILADELPHIA ; 3600 UNIV CITY SCIENCE CENTER, PHILADELPHIA, PA 19104-2688 USA
内容类型	期刊论文
源URL	[http://hdl.handle.net/123456789/82869]
专题	清华大学
推荐引用方式 GB/T 7714	Xiao, Jing,Liu, Lan,Xia, Lirong,et al. EFFICIENT ALGORITHMS FOR RECONSTRUCTING ZERO-RECOMBINANT HAPLOTYPES ON A PEDIGREE BASED ON FAST ELIMINATION OF REDUNDANT LINEAR EQUATIONS[J],2010, 2010.
APA	Xiao, Jing,Liu, Lan,Xia, Lirong,&Jiang, Tao.(2010).EFFICIENT ALGORITHMS FOR RECONSTRUCTING ZERO-RECOMBINANT HAPLOTYPES ON A PEDIGREE BASED ON FAST ELIMINATION OF REDUNDANT LINEAR EQUATIONS..
MLA	Xiao, Jing,et al."EFFICIENT ALGORITHMS FOR RECONSTRUCTING ZERO-RECOMBINANT HAPLOTYPES ON A PEDIGREE BASED ON FAST ELIMINATION OF REDUNDANT LINEAR EQUATIONS".(2010).

个性服务

查看访问统计

相关权益政策

暂无数据

收藏/分享

除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。