Name
Title | ||
|---|---|---|
Efficient Algorithms for Reconstructing Zero-Recombinant Haplotypes on a Pedigree Based on Fast Elimination of Redundant Linear Equations |
Abstract | ||
|---|---|---|
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^3n^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^2n\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. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1137/070687591 | SIAM J. Comput. |
Keywords | Field | DocType |
fast elimination,general system,reconstructing zero-recombinant haplotypes,computational inference,linear equation,efficient method,new system,log n,redundant linear equations,computational biology community,underlying pedigree graph structure,fast elimination method,pedigree graph,efficient algorithms,system of linear equations,linear equations | Discrete mathematics,Linear equation,Binary logarithm,Finite field,Combinatorics,System of linear equations,Linear system,International HapMap Project,Algorithm,Spanning tree,Gaussian elimination,Mathematics | Journal |
Volume | Issue | ISSN |
38 | 6 | 0097-5397 |
Citations | PageRank | References |
7 | 0.62 | 2 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jing Xiao | 1 | 181 | 16.09 |
| Lan Liu | 2 | 54 | 5.27 |
| Lirong Xia | 3 | 1034 | 86.84 |
| Tao Jiang | 4 | 1809 | 155.32 |