Integer Linear Programming Approach to Median and Center Strings for a Probability Distribution on a Set of Strings

Morihiro Hayashida, Hitoshi Koyano

2016

Abstract

We address problems of finding median and center strings for a probability distribution on a set of strings under Levenshtein distance, which are known to be NP-hard in a special case. There are many applications in various research fields, for instance, to find functional motifs in protein amino acid sequences, and to recognize shapes and characters in image processing. In this paper, we propose novel integer linear programming-based methods for finding median and center strings for a probability distribution on a set of strings under Levenshtein distance. Furthermore, we restrict several variables to a region near the diagonal in the formulation, and propose novel integer linear programming-based methods also for finding approximate median and center strings for a probability distribution on a set of strings. For evaluation of our proposed methods, we perform several computational experiments, and show that the restricted formulation reduced the execution time.

Paper Citation

in Harvard Style

Hayashida M. and Koyano H. (2016). Integer Linear Programming Approach to Median and Center Strings for a Probability Distribution on a Set of Strings . In Proceedings of the 9th International Joint Conference on Biomedical Engineering Systems and Technologies - Volume 3: BIOINFORMATICS, (BIOSTEC 2016) ISBN 978-989-758-170-0, pages 35-41. DOI: 10.5220/0005666400350041

in Bibtex Style

@conference{bioinformatics16,
author={Morihiro Hayashida and Hitoshi Koyano},
title={Integer Linear Programming Approach to Median and Center Strings for a Probability Distribution on a Set of Strings},
booktitle={Proceedings of the 9th International Joint Conference on Biomedical Engineering Systems and Technologies - Volume 3: BIOINFORMATICS, (BIOSTEC 2016)},
year={2016},
pages={35-41},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0005666400350041},
isbn={978-989-758-170-0},
}

in EndNote Style

TY - CONF
JO - Proceedings of the 9th International Joint Conference on Biomedical Engineering Systems and Technologies - Volume 3: BIOINFORMATICS, (BIOSTEC 2016)
TI - Integer Linear Programming Approach to Median and Center Strings for a Probability Distribution on a Set of Strings
SN - 978-989-758-170-0
AU - Hayashida M.
AU - Koyano H.
PY - 2016
SP - 35
EP - 41
DO - 10.5220/0005666400350041