The complete parsimony haplotype inference problem and algorithms based on integer programming, branch-and-bound and Boolean satisfiability

Gerold Jäger; Sharlee Climer; Weixiong Zhang

doi:10.1016/j.jda.2016.06.001

The complete parsimony haplotype inference problem and algorithms based on integer programming, branch-and-bound and Boolean satisfiability

Gerold Jäger, Sharlee Climer, Weixiong Zhang

Research output: Contribution to journal › Article › peer-review

Abstract

Haplotype inference by pure parsimony (Hipp) is a well-known paradigm for haplotype inference. In order to assess the biological significance of this paradigm, we generalize the problem of Hipp to the problem of finding all optimal solutions, which we call Chipp. We study intrinsic haplotype features, such as backbone haplotypes and fat genotypes as well as equal columns and

Original language	American English
Journal	Journal of Discrete Algorithms
Volume	37
DOIs	https://doi.org/10.1016/j.jda.2016.06.001
State	Published - Mar 1 2016
Externally published	Yes

Keywords

Boolean satisfiability
Branch-and-bound
Haplotype inference
Integer programming
Pure parsimony

Disciplines

Mathematics
Theory and Algorithms
Discrete Mathematics and Combinatorics

Access to Document

10.1016/j.jda.2016.06.001License: Unspecified

Cite this

@article{523ec98e24b3446289c44a86083f3d44,

title = "The complete parsimony haplotype inference problem and algorithms based on integer programming, branch-and-bound and Boolean satisfiability",

abstract = " Haplotype inference by pure parsimony (Hipp) is a well-known paradigm for haplotype inference. In order to assess the biological significance of this paradigm, we generalize the problem of Hipp to the problem of finding all optimal solutions, which we call Chipp. We study intrinsic haplotype features, such as backbone haplotypes and fat genotypes as well as equal columns and ",

keywords = "Boolean satisfiability, Branch-and-bound, Haplotype inference, Integer programming, Pure parsimony",

author = "Gerold J{\"a}ger and Sharlee Climer and Weixiong Zhang",

note = "Haplotype inference by pure parsimony (Hipp) is a well-known paradigm for haplotype inference. In order to assess the biological significance of this ...",

year = "2016",

month = mar,

day = "1",

doi = "10.1016/j.jda.2016.06.001",

language = "American English",

volume = "37",

journal = "Journal of Discrete Algorithms",

}

TY - JOUR

T1 - The complete parsimony haplotype inference problem and algorithms based on integer programming, branch-and-bound and Boolean satisfiability

AU - Jäger, Gerold

AU - Climer, Sharlee

AU - Zhang, Weixiong

N1 - Haplotype inference by pure parsimony (Hipp) is a well-known paradigm for haplotype inference. In order to assess the biological significance of this ...

PY - 2016/3/1

Y1 - 2016/3/1

N2 - Haplotype inference by pure parsimony (Hipp) is a well-known paradigm for haplotype inference. In order to assess the biological significance of this paradigm, we generalize the problem of Hipp to the problem of finding all optimal solutions, which we call Chipp. We study intrinsic haplotype features, such as backbone haplotypes and fat genotypes as well as equal columns and

AB - Haplotype inference by pure parsimony (Hipp) is a well-known paradigm for haplotype inference. In order to assess the biological significance of this paradigm, we generalize the problem of Hipp to the problem of finding all optimal solutions, which we call Chipp. We study intrinsic haplotype features, such as backbone haplotypes and fat genotypes as well as equal columns and

KW - Boolean satisfiability

KW - Branch-and-bound

KW - Haplotype inference

KW - Integer programming

KW - Pure parsimony

UR - https://www.sciencedirect.com/science/article/pii/S1570866716300090

U2 - 10.1016/j.jda.2016.06.001

DO - 10.1016/j.jda.2016.06.001

M3 - Article

VL - 37

JO - Journal of Discrete Algorithms

JF - Journal of Discrete Algorithms

ER -

The complete parsimony haplotype inference problem and algorithms based on integer programming, branch-and-bound and Boolean satisfiability

Abstract

Keywords

Disciplines

Access to Document

Other files and links

Cite this