A New Integer Programming Formulation for the Pure Parsimony Problem in Haplotype Analysis View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2004

AUTHORS

Daniel G. Brown , Ian M. Harrower

ABSTRACT

We present a new integer programming formulation for the haplotype inference by pure parsimony (HIPP) problem. Unlike a previous approach to this problem [2], we create an integer program whose size is polynomial in the size of the input. This IP is substantially smaller for moderate-sized instances of the HIPP problem. We also show several additional constraints, based on the input, that can be added to the IP to aid in finding a solution, and show how to find which of these constraints is active for a given instance in efficient time. We present experimental results that show our IP has comparable success to the formulation of Gusfield [2] on moderate-sized problems, though it is is much slower. However, our formulation can sometimes solve substantially larger problems than are practical with Gusfield’s formulation. More... »

PAGES

254-265

Book

TITLE

Algorithms in Bioinformatics

ISBN

978-3-540-23018-2
978-3-540-30219-3

Author Affiliations

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-540-30219-3_22

DOI

http://dx.doi.org/10.1007/978-3-540-30219-3_22

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1033395732


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "University of Waterloo", 
          "id": "https://www.grid.ac/institutes/grid.46078.3d", 
          "name": [
            "School of Computer Science, University of Waterloo, N2L 3G1, Waterloo, ON, Canada"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Brown", 
        "givenName": "Daniel G.", 
        "id": "sg:person.0642727740.54", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0642727740.54"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Waterloo", 
          "id": "https://www.grid.ac/institutes/grid.46078.3d", 
          "name": [
            "School of Computer Science, University of Waterloo, N2L 3G1, Waterloo, ON, Canada"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Harrower", 
        "givenName": "Ian M.", 
        "id": "sg:person.01203526716.95", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01203526716.95"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1093/bioinformatics/18.2.337", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1016789793"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-540-24719-7_3", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1023302947", 
          "https://doi.org/10.1007/978-3-540-24719-7_3"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-540-24719-7_3", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1023302947", 
          "https://doi.org/10.1007/978-3-540-24719-7_3"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-44888-8_11", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1023740799", 
          "https://doi.org/10.1007/3-540-44888-8_11"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1093/bioinformatics/btg239", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1024595187"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1086/319501", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1027413555"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1086/338446", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1045707308"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1287/ijoc.1040.0085", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1064706502"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1093/oxfordjournals.molbev.a040591", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1078302152"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2004", 
    "datePublishedReg": "2004-01-01", 
    "description": "We present a new integer programming formulation for the haplotype inference by pure parsimony (HIPP) problem. Unlike a previous approach to this problem [2], we create an integer program whose size is polynomial in the size of the input. This IP is substantially smaller for moderate-sized instances of the HIPP problem. We also show several additional constraints, based on the input, that can be added to the IP to aid in finding a solution, and show how to find which of these constraints is active for a given instance in efficient time. We present experimental results that show our IP has comparable success to the formulation of Gusfield [2] on moderate-sized problems, though it is is much slower. However, our formulation can sometimes solve substantially larger problems than are practical with Gusfield\u2019s formulation.", 
    "editor": [
      {
        "familyName": "Jonassen", 
        "givenName": "Inge", 
        "type": "Person"
      }, 
      {
        "familyName": "Kim", 
        "givenName": "Junhyong", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-540-30219-3_22", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-23018-2", 
        "978-3-540-30219-3"
      ], 
      "name": "Algorithms in Bioinformatics", 
      "type": "Book"
    }, 
    "name": "A New Integer Programming Formulation for the Pure Parsimony Problem in Haplotype Analysis", 
    "pagination": "254-265", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1033395732"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-540-30219-3_22"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "9f171d5e27d8d7dae029bf2a8cd0f7aed3df673517f3d6d5a5ebab0e7a49425f"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-540-30219-3_22", 
      "https://app.dimensions.ai/details/publication/pub.1033395732"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-16T08:25", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000363_0000000363/records_70049_00000001.jsonl", 
    "type": "Chapter", 
    "url": "https://link.springer.com/10.1007%2F978-3-540-30219-3_22"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-30219-3_22'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-30219-3_22'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-30219-3_22'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-30219-3_22'


 

This table displays all metadata directly associated to this object as RDF triples.

103 TRIPLES      23 PREDICATES      35 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-540-30219-3_22 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N9dd3cea003a44c099c0f08c8676069fc
4 schema:citation sg:pub.10.1007/3-540-44888-8_11
5 sg:pub.10.1007/978-3-540-24719-7_3
6 https://doi.org/10.1086/319501
7 https://doi.org/10.1086/338446
8 https://doi.org/10.1093/bioinformatics/18.2.337
9 https://doi.org/10.1093/bioinformatics/btg239
10 https://doi.org/10.1093/oxfordjournals.molbev.a040591
11 https://doi.org/10.1287/ijoc.1040.0085
12 schema:datePublished 2004
13 schema:datePublishedReg 2004-01-01
14 schema:description We present a new integer programming formulation for the haplotype inference by pure parsimony (HIPP) problem. Unlike a previous approach to this problem [2], we create an integer program whose size is polynomial in the size of the input. This IP is substantially smaller for moderate-sized instances of the HIPP problem. We also show several additional constraints, based on the input, that can be added to the IP to aid in finding a solution, and show how to find which of these constraints is active for a given instance in efficient time. We present experimental results that show our IP has comparable success to the formulation of Gusfield [2] on moderate-sized problems, though it is is much slower. However, our formulation can sometimes solve substantially larger problems than are practical with Gusfield’s formulation.
15 schema:editor N28fc45cc1b004842a0f62cbda31fc60d
16 schema:genre chapter
17 schema:inLanguage en
18 schema:isAccessibleForFree true
19 schema:isPartOf N7ba96f9a0a984e22afd79d543ff02246
20 schema:name A New Integer Programming Formulation for the Pure Parsimony Problem in Haplotype Analysis
21 schema:pagination 254-265
22 schema:productId N5b880013cd224eb786f91a225e9a688d
23 N9bd1515463564ed99c3d233a37216cae
24 Nc3fb3335bcad47ab8b49c31a457ecf7d
25 schema:publisher N386fd5de49d448c89c34fc80c69f8620
26 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033395732
27 https://doi.org/10.1007/978-3-540-30219-3_22
28 schema:sdDatePublished 2019-04-16T08:25
29 schema:sdLicense https://scigraph.springernature.com/explorer/license/
30 schema:sdPublisher Nb0f1515dab584302ae319d8f32f31070
31 schema:url https://link.springer.com/10.1007%2F978-3-540-30219-3_22
32 sgo:license sg:explorer/license/
33 sgo:sdDataset chapters
34 rdf:type schema:Chapter
35 N08c8cbd927f14151b7f716b0fc327413 rdf:first N7f117383ba7847f1bfe580e5e6a91330
36 rdf:rest rdf:nil
37 N14c5ed6efb8740e6bf46649f15363575 schema:familyName Jonassen
38 schema:givenName Inge
39 rdf:type schema:Person
40 N28fc45cc1b004842a0f62cbda31fc60d rdf:first N14c5ed6efb8740e6bf46649f15363575
41 rdf:rest N08c8cbd927f14151b7f716b0fc327413
42 N386fd5de49d448c89c34fc80c69f8620 schema:location Berlin, Heidelberg
43 schema:name Springer Berlin Heidelberg
44 rdf:type schema:Organisation
45 N5b880013cd224eb786f91a225e9a688d schema:name readcube_id
46 schema:value 9f171d5e27d8d7dae029bf2a8cd0f7aed3df673517f3d6d5a5ebab0e7a49425f
47 rdf:type schema:PropertyValue
48 N674cfa5aaa1f49959062e22f552d16fc rdf:first sg:person.01203526716.95
49 rdf:rest rdf:nil
50 N7ba96f9a0a984e22afd79d543ff02246 schema:isbn 978-3-540-23018-2
51 978-3-540-30219-3
52 schema:name Algorithms in Bioinformatics
53 rdf:type schema:Book
54 N7f117383ba7847f1bfe580e5e6a91330 schema:familyName Kim
55 schema:givenName Junhyong
56 rdf:type schema:Person
57 N9bd1515463564ed99c3d233a37216cae schema:name doi
58 schema:value 10.1007/978-3-540-30219-3_22
59 rdf:type schema:PropertyValue
60 N9dd3cea003a44c099c0f08c8676069fc rdf:first sg:person.0642727740.54
61 rdf:rest N674cfa5aaa1f49959062e22f552d16fc
62 Nb0f1515dab584302ae319d8f32f31070 schema:name Springer Nature - SN SciGraph project
63 rdf:type schema:Organization
64 Nc3fb3335bcad47ab8b49c31a457ecf7d schema:name dimensions_id
65 schema:value pub.1033395732
66 rdf:type schema:PropertyValue
67 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
68 schema:name Information and Computing Sciences
69 rdf:type schema:DefinedTerm
70 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
71 schema:name Computation Theory and Mathematics
72 rdf:type schema:DefinedTerm
73 sg:person.01203526716.95 schema:affiliation https://www.grid.ac/institutes/grid.46078.3d
74 schema:familyName Harrower
75 schema:givenName Ian M.
76 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01203526716.95
77 rdf:type schema:Person
78 sg:person.0642727740.54 schema:affiliation https://www.grid.ac/institutes/grid.46078.3d
79 schema:familyName Brown
80 schema:givenName Daniel G.
81 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0642727740.54
82 rdf:type schema:Person
83 sg:pub.10.1007/3-540-44888-8_11 schema:sameAs https://app.dimensions.ai/details/publication/pub.1023740799
84 https://doi.org/10.1007/3-540-44888-8_11
85 rdf:type schema:CreativeWork
86 sg:pub.10.1007/978-3-540-24719-7_3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1023302947
87 https://doi.org/10.1007/978-3-540-24719-7_3
88 rdf:type schema:CreativeWork
89 https://doi.org/10.1086/319501 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027413555
90 rdf:type schema:CreativeWork
91 https://doi.org/10.1086/338446 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045707308
92 rdf:type schema:CreativeWork
93 https://doi.org/10.1093/bioinformatics/18.2.337 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016789793
94 rdf:type schema:CreativeWork
95 https://doi.org/10.1093/bioinformatics/btg239 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024595187
96 rdf:type schema:CreativeWork
97 https://doi.org/10.1093/oxfordjournals.molbev.a040591 schema:sameAs https://app.dimensions.ai/details/publication/pub.1078302152
98 rdf:type schema:CreativeWork
99 https://doi.org/10.1287/ijoc.1040.0085 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064706502
100 rdf:type schema:CreativeWork
101 https://www.grid.ac/institutes/grid.46078.3d schema:alternateName University of Waterloo
102 schema:name School of Computer Science, University of Waterloo, N2L 3G1, Waterloo, ON, Canada
103 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...