Dataset Information

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

ABSTRACT:

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 approximately 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 approximately 2 times. Overall, the proposed method with 4 processors increases the computational efficiency up to approximately 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.

SUBMITTER: Lee SH

PROVIDER: S-EPMC2375132 | biostudies-literature | 2008 Apr

REPOSITORIES: biostudies-literature

ACCESS DATA

Publications

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

Lee Sang Hong SH Van der Werf Julius H J JH Kinghorn Brian P BP

BMC bioinformatics 20080411

<h4>Background</h4>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.<h4>Results</h4>An evolutionary algorithm (EA) is a good alternative whose convergence can be eas ...[more]

PMID: 18405361

Similar Datasets

Project description:BackgroundTo improve the tedious task of reconstructing gene networks through testing experimentally the possible interactions between genes, it becomes a trend to adopt the automated reverse engineering procedure instead. Some evolutionary algorithms have been suggested for deriving network parameters. However, to infer large networks by the evolutionary algorithm, it is necessary to address two important issues: premature convergence and high computational cost. To tackle the former problem and to enhance the performance of traditional evolutionary algorithms, it is advisable to use parallel model evolutionary algorithms. To overcome the latter and to speed up the computation, it is advocated to adopt the mechanism of cloud computing as a promising solution: most popular is the method of MapReduce programming model, a fault-tolerant framework to implement parallel algorithms for inferring large gene networks.ResultsThis work presents a practical framework to infer large gene networks, by developing and parallelizing a hybrid GA-PSO optimization method. Our parallel method is extended to work with the Hadoop MapReduce programming model and is executed in different cloud computing environments. To evaluate the proposed approach, we use a well-known open-source software GeneNetWeaver to create several yeast S. cerevisiae sub-networks and use them to produce gene profiles. Experiments have been conducted and the results have been analyzed. They show that our parallel approach can be successfully used to infer networks with desired behaviors and the computation time can be largely reduced.ConclusionsParallel population-based algorithms can effectively determine network parameters and they perform better than the widely-used sequential algorithms in gene network inference. These parallel algorithms can be distributed to the cloud computing environment to speed up the computation. By coupling the parallel model population-based optimization method and the parallel computational framework, high quality solutions can be obtained within relatively short time. This integrated approach is a promising way for inferring large networks.

Dataset Information

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

Background

Results

Conclusion

Publications

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

Similar Datasets

OmicsDI is part of the ELIXIR infrastructure

Tweets