Title: Experimental analysis of a new algorithm for partial haplotype completion

Authors: Paola Bonizzoni, Gianluca Della Vedova, Riccardo Dondi, Lorenzo Mariani

Addresses: Dipartimento di Informatica, Sistemistica e Comunicazione, Univ. Milano-Bicocca, Via Bicocca degli Arcimboldi 8, 20126 Milano, Italy. ' Dipartimento di Statistica, Univ. Milano-Bicocca, Via Bicocca degli Arcimboldi 8, 20126 Milano, Italy. ' Dipartimento di Informatica, Sistemistica e Comunicazione, Univ. Milano-Bicocca, Via Bicocca degli Arcimboldi 8, 20126 Milano, Italy. ' Dipartimento di Informatica, Sistemistica e Comunicazione, Univ. Milano-Bicocca, Via Bicocca degli Arcimboldi 8, 20126 Milano, Italy

Abstract: This paper deals with the computational problem of inferring complete information on haplotypes from haplotypes with missing data. This problem is one of the main issues in haplotyping, as the current DNA sequencing technology often produces haplotypes with missing bases and therefore the complete information on haplotypes has to be inferred through computational methods. In this paper, we propose a new algorithmic approach to the problem that assumes both the Coalescent and the Minimum Entropy models and we provide an experimental analysis relating it to the previously investigated approaches. In particular, the reconstruction of a perfect phylogeny from haplotypes with missing data is addressed.

Keywords: haplotyping; incomplete haplotype reconstruction; perfect phylogeny haplotyping; heuristics design; bioinformatics; partial haplotype completion; haplotypes; DNA sequencing; missing data; coalescent model; minimum entropy model.

DOI: 10.1504/IJBRA.2005.008448

International Journal of Bioinformatics Research and Applications, 2005 Vol.1 No.4, pp.461 - 473

Published online: 20 Dec 2005 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article