Name
Title | ||
|---|---|---|
Integer Linear Programming Approach to Median and Center Strings for a Probability Distribution on a Set of Strings. |
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. |
Year | Venue | Field |
|---|---|---|
2016 | BIOINFORMATICS | Diagonal,Edit distance,Discrete mathematics,Combinatorics,Computer science,Jaro–Winkler distance,Levenshtein distance,Probability distribution,Integer programming,Approximate string matching,String metric |
DocType | Citations | PageRank |
Conference | 0 | 0.34 |
References | Authors | |
0 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Morihiro Hayashida | 1 | 154 | 21.88 |
| hitoshi koyano | 2 | 0 | 1.69 |