TY - GEN
T1 - A recursive method for solving haplotype frequencies in multiple loci linkage analysis
AU - NG, Kwok Po
AU - Fung, Eric S.
AU - Ching, Wai Ki
AU - Lee, Yiu Fai
N1 - Copyright:
Copyright 2012 Elsevier B.V., All rights reserved.
PY - 2006
Y1 - 2006
N2 - Multiple loci analysis has become popular with the advanced development in biological experiments. A lot of studies have been focused on the biological and the statistical properties of such multiple loci analysis. In this paper, we study one of the important computational problems: solving the probabilities of haplotype classes from a large linear system Ax = b derived from the recombination events in multiple loci analysis. Since the size of the recombination matrix A increases exponentially with respect to the number of loci, fast solvers are required to deal with a large number of loci in the analysis. By exploiting the nice structure of the matrix A, we develop an efficient recursive algorithm for solving such structured linear systems. In particular, the complexity of the proposed algorithm is of O(mlogm) operations and the memory requirement is of O(m) locations where m is the size of the matrix A. Numerical examples are given to demonstrate the effectiveness of our efficient solver.
AB - Multiple loci analysis has become popular with the advanced development in biological experiments. A lot of studies have been focused on the biological and the statistical properties of such multiple loci analysis. In this paper, we study one of the important computational problems: solving the probabilities of haplotype classes from a large linear system Ax = b derived from the recombination events in multiple loci analysis. Since the size of the recombination matrix A increases exponentially with respect to the number of loci, fast solvers are required to deal with a large number of loci in the analysis. By exploiting the nice structure of the matrix A, we develop an efficient recursive algorithm for solving such structured linear systems. In particular, the complexity of the proposed algorithm is of O(mlogm) operations and the memory requirement is of O(m) locations where m is the size of the matrix A. Numerical examples are given to demonstrate the effectiveness of our efficient solver.
UR - http://www.scopus.com/inward/record.url?scp=84863059479&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:84863059479
SN - 1860946232
SN - 9781860946233
T3 - Series on Advances in Bioinformatics and Computational Biology
SP - 129
EP - 138
BT - Proceedings of the 4th Asia-Pacific Bioinformatics Conference, APBC 2006
T2 - 4th Asia-Pacific Bioinformatics Conference, APBC 2006
Y2 - 13 February 2006 through 16 February 2006
ER -