NDLI: An Efficient Algorithm for Haplotype Inference on Pedigrees with Recombinations and Mutations

Please wait, while we are loading the content...

IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB) : Volume 13

IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB) : Volume 12

IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB) : Volume 11

IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB) : Volume 10

IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB) : Volume 9

Issue 6, November 2012

Issue 5, September 2012

Issue 4, July 2012

Issue 3, May 2012

Issue 2, March 2012

Issue 1, January 2012

A Memory Efficient Method for Structure-Based RNA Multiple Alignment

An Efficient Algorithm for Haplotype Inference on Pedigrees with Recombinations and Mutations

An Efficient Method for Exploring the Space of Gene Tree/Species Tree Reconciliations in a Probabilistic Framework

An Efficient Method for Modeling Kinetic Behavior of Channel Proteins in Cardiomyocytes

An Information Theoretic Approach to Constructing Robust Boolean Gene Regulatory Networks

Assortative Mixing in Directed Biological Networks

Composition Vector Method Based on Maximum Entropy Principle for Sequence Comparison

Disease Liability Prediction from Large Scale Genotyping Data Using Classifiers with a Reject Option

Drosophila Gene Expression Pattern Annotation through Multi-Instance Multi-Label Learning

Inferring the Number of Contributors to Mixed DNA Profiles

Intervention in Gene Regulatory Networks via Phenotypically Constrained Control Policies Based on Long-Run Behavior

Iterative Dictionary Construction for Compression of Large DNA Data Sets

Matching Split Distance for Unrooted Binary Phylogenetic Trees

Memory Efficient Algorithms for Structural Alignment of RNAs with Pseudoknots

Multiobjective Optimization Based-Approach for Discovering Novel Cancer Therapies

Parameter Estimation Using Metaheuristics in Systems Biology: A Comprehensive Review

Predicting Metal-Binding Sites from Protein Sequence

Reassortment Networks and the Evolution of Pandemic H1N1 Swine-Origin Influenza

RENNSH: A Novel \alpha-Helix Identification Approach for Intermediate Resolution Electron Density Maps

Residues with Similar Hexagon Neighborhoods Share Similar Side-Chain Conformations

Smolign: A Spatial Motifs-Based Protein Multiple Structural Alignment Method

Stable Gene Selection from Microarray Data via Sample Weighting

The Complexity of Finding Multiple Solutions to Betweenness and Quartet Compatibility

Touring Protein Space with Matt

Transactional Database Transformation and Its Application in Prioritizing Human Disease Genes

k-Information Gain Scaled Nearest Neighbors: A Novel Approach to Classifying Protein-Protein Interaction-Related Documents

MinePhos: A Literature Mining System for Protein Phoshphorylation Information Extraction

2011 Reviewers List

2011 Annual Index

IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB) : Volume 8

IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB) : Volume 7

IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB) : Volume 6

IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB) : Volume 5

IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB) : Volume 4

IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB) : Volume 3

IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB) : Volume 2

IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB) : Volume 1

An Efficient Algorithm for Haplotype Inference on Pedigrees with Recombinations and Mutations

Content Provider	ACM Digital Library
Author	Bonizzoni, Paola Jiang, Tao Pirola, Yuri
Abstract	Haplotype Inference (HI) is a computational challenge of crucial importance in a range of genetic studies. Pedigrees allow to infer haplotypes from genotypes more accurately than population data, since Mendelian inheritance restricts the set of possible solutions. In this work, we define a new HI problem on pedigrees, called Minimum-Change Haplotype Configuration (MCHC) problem, that allows two types of genetic variation events: recombinations and mutations. Our new formulation extends the Minimum-Recombinant Haplotype Configuration (MRHC) problem, that has been proposed in the literature to overcome the limitations of classic statistical haplotyping methods. Our contribution is twofold. First, we prove that the MCHC problem is APX-hard under several restrictions. Second, we propose an efficient and accurate heuristic algorithm for MCHC based on an L-reduction to a well-known coding problem. Our heuristic can also be used to solve the original MRHC problem and can take advantage of additional knowledge about the input genotypes. Moreover, the L-reduction proves for the first time that MCHC and MRHC are O({nm\over \log nm} -approximable on general pedigrees, where n is the pedigree size and m is the genotype length. Finally, we present an extensive experimental evaluation and comparison of our heuristic algorithm with several other state-of-the-art methods for HI on pedigrees.
Starting Page	12
Ending Page	25
Page Count	14
File Format	PDF
ISSN	15455963
DOI	10.1109/TCBB.2011.51
Volume Number	9
Issue Number	1
Journal	IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB)
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2012-01-01
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Algorithms, haplotyping, haplotype inference, pedigree, recombinations, mutations.
Content Type	Text
Resource Type	Article
Subject	Genetics Biotechnology Applied Mathematics

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

An Efficient Algorithm for Haplotype Inference on Pedigrees with Recombinations and Mutations

A fast and practical approach to genotype phasing and imputation on a pedigree with erroneous and incomplete information

A Fast and Practical Approach to Genotype Phasing and Imputation on a Pedigree with Erroneous and Incomplete Information

An Efficient Algorithm for Haplotype Inference on Pedigrees with a Small Number of Recombinants

Efficient haplotype inference algorithms in one whole genome scan for pedigree data with non-genotyped founders

An Efficient Algorithm for Haplotype Inference on Pedigrees with a Small Number of Recombinants

Linear-Time Haplotype Inference on Pedigrees without Recombinations (2006)

Haplotype Inference Constrained by Plausible Haplotype Data

Linear-Time Haplotype Inference on Pedigrees without Recombinations and Mating Loops

An Efficient Algorithm for Haplotype Inference on Pedigrees with Recombinations and Mutations

Similar Documents

An Efficient Algorithm for Haplotype Inference on Pedigrees with Recombinations and Mutations

A fast and practical approach to genotype phasing and imputation on a pedigree with erroneous and incomplete information

A Fast and Practical Approach to Genotype Phasing and Imputation on a Pedigree with Erroneous and Incomplete Information

An Efficient Algorithm for Haplotype Inference on Pedigrees with a Small Number of Recombinants

Efficient haplotype inference algorithms in one whole genome scan for pedigree data with non-genotyped founders

An Efficient Algorithm for Haplotype Inference on Pedigrees with a Small Number of Recombinants

Linear-Time Haplotype Inference on Pedigrees without Recombinations (2006)

Haplotype Inference Constrained by Plausible Haplotype Data

Linear-Time Haplotype Inference on Pedigrees without Recombinations and Mating Loops

An Efficient Algorithm for Haplotype Inference on Pedigrees with Recombinations and Mutations