Title

An Efficient Algorithm For Perfect Phylogeny Haplotyping

Abstract

The Perfect Phytogeny Haplotyping (PPH) problem is one of the many computational approaches to the Haplotype Inference (HI) problem. Though there are many O(nm 2) solutions to the PPH problem, the complexity of the PPH problem itself has remained an open question. In this paper, We introduce the FlexTree data structure that represents all the solutions for a PPH instance. We also introduce row-ordering that arranges the genotypes in a more manageable fashion. The column ordering, the FlexTree data structure and the row ordering together make the O(nm) OPPH algorithm possible. We also present some results on simulated data which demonstrate that the OPPH algorithm performs quiet impressively when compared to the earlier O(nm 2) algorithms. © 2005 IEEE.

Publication Date

12-1-2005

Publication Title

Proceedings - 2005 IEEE Computational Systems Bioinformatics Conference, CSB 2005

Volume

2005

Number of Pages

103-110

Document Type

Article; Proceedings Paper

Personal Identifier

scopus

DOI Link

https://doi.org/10.1109/CSB.2005.12

Socpus ID

33745301284 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/33745301284

This document is currently not available here.

Share

COinS