Solving Some Sequence Problems on Run-Length Encoded Strings
Longest Common Subsequences, Edit Distances, and Squares
(Sprache: Englisch)
Measuring the similarity or difference between two strings is a fundamental problem to many applications. In bioinformatics, one has to predict the structures of RNA and proteins, to classify the functions of molecules, to infer the phylogeny of organisms,...
Leider schon ausverkauft
versandkostenfrei
Buch (Kartoniert)
49.00 €
Produktdetails
Produktinformationen zu „Solving Some Sequence Problems on Run-Length Encoded Strings “
Klappentext zu „Solving Some Sequence Problems on Run-Length Encoded Strings “
Measuring the similarity or difference between two strings is a fundamental problem to many applications. In bioinformatics, one has to predict the structures of RNA and proteins, to classify the functions of molecules, to infer the phylogeny of organisms, and to search entries in huge sequence databases. While processing electronic documents, one needs fast and flexible indexing techniques to perform searches. For this purpose, many measures are defined. The longest common subsequence and the edit distance are the most studied dealt with problems in string processing. In this book, we propose an O(min{mN,Mn}) time algorithm for finding a longest common subsequence of strings X and Y with lengths m and n, respectively, and run-length-encoded lengths M and N, respectively. On the other hand, we also improve the time bound to O(min{mN,Mn}) for finding the edit distance between strings X and Y. Squares play a central role from word combinatorics and application perspective. We show how to locate all squares in a run-length encoded string in time O(N logN). The time complexity of our result is optimal, and it is irrelevant to the length of the original uncompressed string.
Autoren-Porträt von Jia-Jie Liu, Wang, G. S. Huang
Liu, Jia-JieI was born in Taiwan in 1976. I received my B.Sc. degree in mathematics in 1998, before serving as a soldier from 1998 to 2000. And i received my M. Sc. and Ph.D degree in information management from NTUST in 2004 and 2007, respectively. In my study, I have focused of study graph theory, algorithms, and string alignment problems.Huang, G. S.
I was born in Taiwan in 1976. I received my B.Sc. degree in mathematics in 1998, before serving as a soldier from 1998 to 2000. And i received my M. Sc. and Ph.D degree in information management from NTUST in 2004 and 2007, respectively. In my study, I have focused of study graph theory, algorithms, and string alignment problems.
Bibliographische Angaben
- Autoren: Jia-Jie Liu , Wang , G. S. Huang
- 2008, 76 Seiten, Maße: 15 x 21,8 cm, Kartoniert (TB), Englisch
- Verlag: VDM Verlag Dr. Müller e.K.
- ISBN-10: 3639022653
- ISBN-13: 9783639022650
Sprache:
Englisch
Kommentar zu "Solving Some Sequence Problems on Run-Length Encoded Strings"
0 Gebrauchte Artikel zu „Solving Some Sequence Problems on Run-Length Encoded Strings“
Zustand | Preis | Porto | Zahlung | Verkäufer | Rating |
---|
Schreiben Sie einen Kommentar zu "Solving Some Sequence Problems on Run-Length Encoded Strings".
Kommentar verfassen