Parameterized complexity of asynchronous border minimization

Robert Ganian, Martin Kronegger, Andreas Pfandler, Alexandru Popa

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    1 Citation (Scopus)

    Abstract

    Microarrays are research tools used in gene discovery as well as disease and cancer diagnostics. Two prominent but challenging problems related to microarrays are the Border Minimization Problem (BMP) and the Border Minimization Problem with given placement (P-BMP). In this paper we investigate the parameterized complexity of natural variants of BMP and P-BMP, termed BMPe and P-BMPe respectively, under several natural parameters. We show that BMPe and P-BMPe are in FPT under the following two combinations of parameters: (1) the size of the alphabet (c), the maximum length of a sequence (string) in the input (ℓ) and the number of rows of the microarray (r); and, (2) the size of the alphabet and the size of the border length (o). Furthermore, P-BMPe is in FPT when parameterized by c and ℓ. We complement our tractability results with corresponding hardness results.

    Original languageEnglish
    Title of host publicationTheory and Applications of Models of Computation - 12th Annual Conference, TAMC 2015, Proceedings
    PublisherSpringer Verlag
    Pages428-440
    Number of pages13
    Volume9076
    ISBN (Print)9783319171418
    DOIs
    Publication statusPublished - 2015
    Event12th Annual Conference on Theory and Applications of Models of Computation, TAMC 2015 - Singapore, Singapore
    Duration: May 18 2015May 20 2015

    Publication series

    NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
    Volume9076
    ISSN (Print)03029743
    ISSN (Electronic)16113349

    Other

    Other12th Annual Conference on Theory and Applications of Models of Computation, TAMC 2015
    CountrySingapore
    CitySingapore
    Period5/18/155/20/15

    Fingerprint

    Parameterized Complexity
    Minimization Problem
    Microarrays
    Microarray
    Tractability
    Hardness
    Placement
    Diagnostics
    Cancer
    Complement
    Genes
    Strings
    Gene

    ASJC Scopus subject areas

    • Computer Science(all)
    • Theoretical Computer Science

    Cite this

    Ganian, R., Kronegger, M., Pfandler, A., & Popa, A. (2015). Parameterized complexity of asynchronous border minimization. In Theory and Applications of Models of Computation - 12th Annual Conference, TAMC 2015, Proceedings (Vol. 9076, pp. 428-440). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9076). Springer Verlag. https://doi.org/10.1007/978-3-319-17142-5_36

    Parameterized complexity of asynchronous border minimization. / Ganian, Robert; Kronegger, Martin; Pfandler, Andreas; Popa, Alexandru.

    Theory and Applications of Models of Computation - 12th Annual Conference, TAMC 2015, Proceedings. Vol. 9076 Springer Verlag, 2015. p. 428-440 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9076).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Ganian, R, Kronegger, M, Pfandler, A & Popa, A 2015, Parameterized complexity of asynchronous border minimization. in Theory and Applications of Models of Computation - 12th Annual Conference, TAMC 2015, Proceedings. vol. 9076, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9076, Springer Verlag, pp. 428-440, 12th Annual Conference on Theory and Applications of Models of Computation, TAMC 2015, Singapore, Singapore, 5/18/15. https://doi.org/10.1007/978-3-319-17142-5_36
    Ganian R, Kronegger M, Pfandler A, Popa A. Parameterized complexity of asynchronous border minimization. In Theory and Applications of Models of Computation - 12th Annual Conference, TAMC 2015, Proceedings. Vol. 9076. Springer Verlag. 2015. p. 428-440. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-319-17142-5_36
    Ganian, Robert ; Kronegger, Martin ; Pfandler, Andreas ; Popa, Alexandru. / Parameterized complexity of asynchronous border minimization. Theory and Applications of Models of Computation - 12th Annual Conference, TAMC 2015, Proceedings. Vol. 9076 Springer Verlag, 2015. pp. 428-440 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
    @inproceedings{4bf347f538de40baacfd2c19af78ecb4,
    title = "Parameterized complexity of asynchronous border minimization",
    abstract = "Microarrays are research tools used in gene discovery as well as disease and cancer diagnostics. Two prominent but challenging problems related to microarrays are the Border Minimization Problem (BMP) and the Border Minimization Problem with given placement (P-BMP). In this paper we investigate the parameterized complexity of natural variants of BMP and P-BMP, termed BMPe and P-BMPe respectively, under several natural parameters. We show that BMPe and P-BMPe are in FPT under the following two combinations of parameters: (1) the size of the alphabet (c), the maximum length of a sequence (string) in the input (ℓ) and the number of rows of the microarray (r); and, (2) the size of the alphabet and the size of the border length (o). Furthermore, P-BMPe is in FPT when parameterized by c and ℓ. We complement our tractability results with corresponding hardness results.",
    author = "Robert Ganian and Martin Kronegger and Andreas Pfandler and Alexandru Popa",
    year = "2015",
    doi = "10.1007/978-3-319-17142-5_36",
    language = "English",
    isbn = "9783319171418",
    volume = "9076",
    series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
    publisher = "Springer Verlag",
    pages = "428--440",
    booktitle = "Theory and Applications of Models of Computation - 12th Annual Conference, TAMC 2015, Proceedings",
    address = "Germany",

    }

    TY - GEN

    T1 - Parameterized complexity of asynchronous border minimization

    AU - Ganian, Robert

    AU - Kronegger, Martin

    AU - Pfandler, Andreas

    AU - Popa, Alexandru

    PY - 2015

    Y1 - 2015

    N2 - Microarrays are research tools used in gene discovery as well as disease and cancer diagnostics. Two prominent but challenging problems related to microarrays are the Border Minimization Problem (BMP) and the Border Minimization Problem with given placement (P-BMP). In this paper we investigate the parameterized complexity of natural variants of BMP and P-BMP, termed BMPe and P-BMPe respectively, under several natural parameters. We show that BMPe and P-BMPe are in FPT under the following two combinations of parameters: (1) the size of the alphabet (c), the maximum length of a sequence (string) in the input (ℓ) and the number of rows of the microarray (r); and, (2) the size of the alphabet and the size of the border length (o). Furthermore, P-BMPe is in FPT when parameterized by c and ℓ. We complement our tractability results with corresponding hardness results.

    AB - Microarrays are research tools used in gene discovery as well as disease and cancer diagnostics. Two prominent but challenging problems related to microarrays are the Border Minimization Problem (BMP) and the Border Minimization Problem with given placement (P-BMP). In this paper we investigate the parameterized complexity of natural variants of BMP and P-BMP, termed BMPe and P-BMPe respectively, under several natural parameters. We show that BMPe and P-BMPe are in FPT under the following two combinations of parameters: (1) the size of the alphabet (c), the maximum length of a sequence (string) in the input (ℓ) and the number of rows of the microarray (r); and, (2) the size of the alphabet and the size of the border length (o). Furthermore, P-BMPe is in FPT when parameterized by c and ℓ. We complement our tractability results with corresponding hardness results.

    UR - http://www.scopus.com/inward/record.url?scp=84929649337&partnerID=8YFLogxK

    UR - http://www.scopus.com/inward/citedby.url?scp=84929649337&partnerID=8YFLogxK

    U2 - 10.1007/978-3-319-17142-5_36

    DO - 10.1007/978-3-319-17142-5_36

    M3 - Conference contribution

    SN - 9783319171418

    VL - 9076

    T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

    SP - 428

    EP - 440

    BT - Theory and Applications of Models of Computation - 12th Annual Conference, TAMC 2015, Proceedings

    PB - Springer Verlag

    ER -