A recursive method for solving haplotype frequencies in multiple loci linkage analysis

Kwok Po Ng*, Eric S. Fung, Wai Ki Ching, Yiu Fai Lee

*Corresponding author for this work

Research output: Chapter in book/report/conference proceedingConference proceedingpeer-review


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.

Original languageEnglish
Title of host publicationProceedings of the 4th Asia-Pacific Bioinformatics Conference, APBC 2006
Number of pages10
Publication statusPublished - 2006
Event4th Asia-Pacific Bioinformatics Conference, APBC 2006 - Taipei, Taiwan, Province of China
Duration: 13 Feb 200616 Feb 2006

Publication series

NameSeries on Advances in Bioinformatics and Computational Biology
ISSN (Print)1751-6404


Conference4th Asia-Pacific Bioinformatics Conference, APBC 2006
Country/TerritoryTaiwan, Province of China

Scopus Subject Areas

  • Bioengineering
  • Information Systems


Dive into the research topics of 'A recursive method for solving haplotype frequencies in multiple loci linkage analysis'. Together they form a unique fingerprint.

Cite this