Name
Abstract | ||
|---|---|---|
Computing string or sequence alignments is a classical me- thod of comparing strings and has applications in many areas of com- puting, such as signal processing and bioinformatics. Semi-local string alignment is a recent generalisation of this method, in which the align- ment of a given string and all substrings of another string are computed simultaneously at no additional asymptotic cost. In this paper, we show that there is a close connection between semi-local string alignment and a certain class of traditional comparison networks known as transposition networks. The transposition network approach can be used to represent different string comparison algorithms in a unified form, and in some cases provides generalisations or improvements on existing algorithms. This approach allows us to obtain new algorithms for sparse semi-local string comparison and for comparison of highly similar and highly dis- similar strings, as well as of run-length compressed strings. We conclude that the transposition network method is a very general and flexible way of understanding and improving different string comparison algorithms, as well as their efficient implementation. |
Year | Venue | Keywords |
|---|---|---|
2009 | Clinical Orthopaedics and Related Research | signal processing,discrete mathematics,data structure,sequence alignment |
Field | DocType | Volume |
String searching algorithm,String-to-string correction problem,Combinatorics,Substring,Computer science,Generalization,Algorithm,Theoretical computer science,Approximate string matching,String kernel,String metric,String (computer science) | Journal | abs/0903.3 |
Citations | PageRank | References |
3 | 0.37 | 26 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Peter Krusche | 1 | 25 | 2.83 |
| Alexander Tiskin | 2 | 220 | 15.50 |