Using an evolutionary algorithm and parallel computing for haplotyping in a general complex pedigree with multiple marker loci

BACKGROUND: Haplotype reconstruction is important in linkage mapping and association mapping of quantitative trait loci (QTL). One widely used statistical approach for haplotype reconstruction is simulated annealing (SA), implemented in SimWalk2. However, the algorithm needs a very large number of s...

Descripción completa

Detalles Bibliográficos
Autores principales: Lee, Sang Hong, Van der Werf, Julius HJ, Kinghorn, Brian P
Formato: Texto
Lenguaje:English
Publicado: BioMed Central 2008
Materias:
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC2375132/
https://www.ncbi.nlm.nih.gov/pubmed/18405361
http://dx.doi.org/10.1186/1471-2105-9-189
_version_ 1782154584969445376
author Lee, Sang Hong
Van der Werf, Julius HJ
Kinghorn, Brian P
author_facet Lee, Sang Hong
Van der Werf, Julius HJ
Kinghorn, Brian P
author_sort Lee, Sang Hong
collection PubMed
description BACKGROUND: Haplotype reconstruction is important in linkage mapping and association mapping of quantitative trait loci (QTL). One widely used statistical approach for haplotype reconstruction is simulated annealing (SA), implemented in SimWalk2. However, the algorithm needs a very large number of sequential iterations, and it does not clearly show if convergence of the likelihood is obtained. RESULTS: An evolutionary algorithm (EA) is a good alternative whose convergence can be easily assessed during the process. It is feasible to use a powerful parallel-computing strategy with the EA, increasing the computational efficiency. It is shown that the EA can be ~4 times faster and gives more reliable estimates than SimWalk2 when using 4 processors. In addition, jointly updating dependent variables can increase the computational efficiency up to ~2 times. Overall, the proposed method with 4 processors increases the computational efficiency up to ~8 times compared to SimWalk2. The efficiency will increase more with a larger number of processors. CONCLUSION: The use of the evolutionary algorithm and the joint updating method can be a promising tool for haplotype reconstruction in linkage and association mapping of QTL.
format Text
id pubmed-2375132
institution National Center for Biotechnology Information
language English
publishDate 2008
publisher BioMed Central
record_format MEDLINE/PubMed
spelling pubmed-23751322008-05-10 Using an evolutionary algorithm and parallel computing for haplotyping in a general complex pedigree with multiple marker loci Lee, Sang Hong Van der Werf, Julius HJ Kinghorn, Brian P BMC Bioinformatics Methodology Article BACKGROUND: Haplotype reconstruction is important in linkage mapping and association mapping of quantitative trait loci (QTL). One widely used statistical approach for haplotype reconstruction is simulated annealing (SA), implemented in SimWalk2. However, the algorithm needs a very large number of sequential iterations, and it does not clearly show if convergence of the likelihood is obtained. RESULTS: An evolutionary algorithm (EA) is a good alternative whose convergence can be easily assessed during the process. It is feasible to use a powerful parallel-computing strategy with the EA, increasing the computational efficiency. It is shown that the EA can be ~4 times faster and gives more reliable estimates than SimWalk2 when using 4 processors. In addition, jointly updating dependent variables can increase the computational efficiency up to ~2 times. Overall, the proposed method with 4 processors increases the computational efficiency up to ~8 times compared to SimWalk2. The efficiency will increase more with a larger number of processors. CONCLUSION: The use of the evolutionary algorithm and the joint updating method can be a promising tool for haplotype reconstruction in linkage and association mapping of QTL. BioMed Central 2008-04-11 /pmc/articles/PMC2375132/ /pubmed/18405361 http://dx.doi.org/10.1186/1471-2105-9-189 Text en Copyright © 2008 Lee et al; licensee BioMed Central Ltd. http://creativecommons.org/licenses/by/2.0 This is an Open Access article distributed under the terms of the Creative Commons Attribution License ( (http://creativecommons.org/licenses/by/2.0) ), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
spellingShingle Methodology Article
Lee, Sang Hong
Van der Werf, Julius HJ
Kinghorn, Brian P
Using an evolutionary algorithm and parallel computing for haplotyping in a general complex pedigree with multiple marker loci
title Using an evolutionary algorithm and parallel computing for haplotyping in a general complex pedigree with multiple marker loci
title_full Using an evolutionary algorithm and parallel computing for haplotyping in a general complex pedigree with multiple marker loci
title_fullStr Using an evolutionary algorithm and parallel computing for haplotyping in a general complex pedigree with multiple marker loci
title_full_unstemmed Using an evolutionary algorithm and parallel computing for haplotyping in a general complex pedigree with multiple marker loci
title_short Using an evolutionary algorithm and parallel computing for haplotyping in a general complex pedigree with multiple marker loci
title_sort using an evolutionary algorithm and parallel computing for haplotyping in a general complex pedigree with multiple marker loci
topic Methodology Article
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC2375132/
https://www.ncbi.nlm.nih.gov/pubmed/18405361
http://dx.doi.org/10.1186/1471-2105-9-189
work_keys_str_mv AT leesanghong usinganevolutionaryalgorithmandparallelcomputingforhaplotypinginageneralcomplexpedigreewithmultiplemarkerloci
AT vanderwerfjuliushj usinganevolutionaryalgorithmandparallelcomputingforhaplotypinginageneralcomplexpedigreewithmultiplemarkerloci
AT kinghornbrianp usinganevolutionaryalgorithmandparallelcomputingforhaplotypinginageneralcomplexpedigreewithmultiplemarkerloci