NDLI: Haplotyping as perfect phylogeny: conceptual framework and efficient solutions

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

Computational structural proteomics and virtual ligand screening

Using motion planning to map protein folding landscapes and analyze folding kinetics of known native structures

Stochastic roadmap simulation: an efficient representation and algorithm for analyzing molecular motion

Monotony of surprise and large-scale quest for unusual words

DNA sequence evolution with neighbor-dependent mutation

A new approach to analyzing gene expression time series data

Discovering local structure in gene expression data: the order-preserving submatrix problem

The restriction scaffold problem

Comparison of minisatellites

Trilogy: discovery of sequence-structure patterns across diverse proteins

Microarray analysis of vertebrate embryonic neural induction

Provably sensitive Indexing strategies for biosequence similarity search

Structural alignment of large—size proteins via lagrangian relaxation

Designing RNA structures: natural and artificial selection

Inferring domain-domain interactions from protein-protein interactions

Analysis of gene expression profiles: class discovery and leaf ordering

A bayesian approach to transcript estimation from gene array data: the BEAM technique

Tests for gene clustering

Recent duplication, evolution and assembly of the human genome

Approximate matching of secondary structures

Applied computational genomics: polymorphism prediction, data mining and genomic analysis

Haplotyping as perfect phylogeny: conceptual framework and efficient solutions

Handling long targets and errors in sequencing by hybridization

Sequencing by hybridization using direct and reverse cooperating spectra

Lymphocyte turnover in HIV-1 infection and the role of the thymus in SIV infection

Finding motifs in the twilight zone

Phase-independent rhythmic analysis of genome-wide expression patterns

Significance Of inter-species matches when evolutionary rate varies

Combining pairwise sequence similarity and support vector machines for remote protein homology detection

Revealing protein structures: a new method for mapping antibody epitopes

Set association analysis of SNP case-control and microarray data

Picking alignments from (steiner) trees

String barcoding: uncovering optimal virus signatures

Biological and computational annotation of the Drosophila Genome Sequence

From promoter sequence to expression: a probabilistic framework

Probabilistic hierarchical clustering for biological data

An algorithm to enumerate all sorting reversals

Discriminative motifs

A dimensionality reduction approach to modeling protein flexibility

Sequencing the human genome

Toward a proteome atlas for C. Elegans

Deconvolving sequence variation in mixed DNA populations

Microarrays: how many do you need?

Haplotyping as perfect phylogeny: conceptual framework and efficient solutions

Content Provider	ACM Digital Library
Author	Gusfield, Dan
Abstract	The next high-priority phase of human genomics will involve the development of a full Haplotype Map of the human genome [12]. It will be used in large-scale screens of populations to associate specific haplotypes with specific complex genetic-influenced diseases. A prototype Haplotype Mapping strategy is presently being finalized by an NIH working-group. The biological key to that strategy is the surprising fact that genomic DNA can be partitioned into long blocks where genetic recombination has been rare, leading to strikingly fewer distinct haplotypes in the population than previously expected [12, 6, 21, 7].In this paper we explore the algorithmic implications of the key (and now realistic) "no-recombination in long blocks" observation, for the problem of inferring haplotypes in populations. We observe that the no-recombination assumption is very powerful. This assumption, along with the standard population-genetic assumption of infinite sites [23, 14] imposes severe combinatorial constraints on the permitted solutions to the haplotype inference problem, leading to an efficient deterministic algorithm to deduce all features of the permitted haplotype solution(s) that can be known with certainty. The technical key is to view haplotype data as disguised information about paths in an unknown tree, and the haplotype deduction problem as a problem of reconstructing the tree from that path information. This formulation allows us to exploit deep theorems and algorithms from graph and matroid theory to efficiently find one permitted solution to the haplotype problem; it gives a simple test to determine if it is the unique solution; if not, we can implicitly represent the set of all permitted solutions so that each can be efficiently created.
Starting Page	166
Ending Page	175
Page Count	10
File Format	PDF
ISBN	1581134983
DOI	10.1145/565196.565218
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2002-04-18
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Graph realization Haplotype inference Perfect phylogeny Graphic matroid recognition
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

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