This series, which began publication in , is the oldest continuously published anthology that chronicles the ever- changing information technology field. In these volumes we publish from 5 to 7 chapters, three times per year, that cover the latest changes to the design, development, use and implications of computer technology on society today. In this present volume we present five chapters describing new technology affecting users of such machines. In this volume we continue a theme presented last year in volume 72 — High Performance Computing.
In volume 72 we described several research projects being conducted in the United States on the development of a new generation of high performance supercomputers.
The 28 revised full papers and 16 revised short papers presented were carefully reviewed and selected from submissions. The papers address current issues in string pattern searching and matching, string discovery, data compression, data mining, text mining, machine learning, information retrieval, digital libraries, and applications in various fields, such as bioinformatics, speech and natural language processing, Web links and communities, and multilingual data.
The 28 full papers and 8 short papers presented in this volume were carefully reviewed and selected from 59 submissions. They cover topics such as: data compression; information retrieval; string algorithms; algorithms; computational biology; indexing and compression; and compressed data structures.
The 43 revised full papers presented together with 3 invited contributions were carefully reviewed and selected from a total of submissions. The papers are organized in sections on data structures, dynamic partitions, graph algorithms, online algorithms, approximation algorithms, matchings, network design, computational geometry, strings and algorithm engineering, external memory algorithms, optimization, and distributed and fault-tolerant computing.
The 29 revised full papers presented together with 3 invited contributions and 2 tutorial lectures were carefully reviewed and selected from 44 submissions. The papers are devoted to current theoretical and algorithmic issues of searching and matching strings and more complicated patterns such as trees, regular expression graphs, point sets and arrays as well as to advanced applications of CPM in areas such as Internet, computational biology, multimedia systems, information retrieval, data compression, and pattern recognition.
The 60 revised full papers presented together with 2 invited talks were carefully reviewed and selected from submissions for inclusion in the book. The focus of the volume in on the following topics: computational geometry, combinatorial optimization, graph algorithms: enumeration, matching and assignment, data structures and algorithms, fixed-parameter tractable algorithms, scheduling algorithms, computational complexity, computational complexity, approximation algorithms, graph theory and algorithms, online and approximation algorithms, and network and scheduling algorithms.
The volumes present a total of papers organized according to the five major conference themes: computational methods, algorithms and applications high performance technical computing and networks advanced and emerging applications geometric modelling, graphics and visualization information systems and information technologies. This is Part III.
Click here to sign up. Download Free PDF. Algorithms on strings, trees and sequences: computer science and computational biology Sandip Paul. A short summary of this paper. Download Download PDF. Translate PDF. Our group followed the standard assumption t h a t biologically meaningful results could come from considering DNA as a one-dimensional character string, abstracting away th e reality of DNA as a flexible three-dimensional molecule, interacting in a dynamic environment with protein and RNA, and repeating a life-cycle in which even the classic linear chromosome exists for only a fraction of the time.
A similar, but stronger, assumption existed for protein, holding for example t h a t all the information needed for correct three-dimensional folding is contained in the protein sequence itself, essentiaUy independent of the biological environment the protein lives in. This assumption has recently been modified, but remains largely intact.
For non-biologlsts, these two assllmptions were and remain a god-send allowing rapid entry into an exciting and i m p o r t a n t field.
Statements such as " T h e digital information t h a t underlies biochemistry, cell biology, an d development can be represented by a simple string of G's, A's, T's and COs. This string is the root d a t a structure of an organism's biology. So without worrying much about the more diIBcult chemical an d biological aspects of D N A and protein, our c o m p u t e r science group was empowered to consider a variety of biologically i m p o r t a n t problems defined plrimarily on sequences, or more in the computer science vernacular on strings.
We organized our efforts into two high-level tasks. First, to learn the relevant biology, laboratory protocols, and existing algorithmic methods used by biologists. Second to canvass the c o m p u t e r science literature for ideas and algorithms t h a t weren't already used by biologists, but wkich might plausibly be of use either in current problems, or in problems t h a t we could anticipate arising w h e n vast quantities of sequenced DNA or protein become available.
Our p r o b l e m None of us was an expert on string algorithms. My general background was in combinatorial optimization, although I ha d a prior interest in algorithms for building evolutionary trees and h ad studied genetics and molecular biology in order to pursue that interest.
There were also some good survey papers that had a somewhat wider scope but didn't treat. There were several texts and edited volumes from the biological side on uses of computers and algorithms for sequence analysis. Some of these were wonderful in exposing the potential benefits and the pitfalls of using computers in biology, but generally lacked algorithmic rigor and covered a narrow range of techniques.
Sankoff and J. Krnskal, that served as a bridge between algorithms and biology, and had m a n y applications of dynamic programming. But it too was much narrower t h a n our focus, and a bit dated. Moreover, most of the available sources from either cornrnunlty focused on string matching, the problem of searching for an exact or "nearly exact"- copy of a p attern in a given text. Matching problems are central, but as detailed in this book, they axe only a part of the m a n y i m p o r t a n t computational problems defined on strings.
This book is an attempt to provide such a dual, and integrated, t r e a t m e n t. My interest in computational biology began in , when I started reading papers on bu.
But seventeen years later, computational biology is hot, and many computer scientists are now entering the now more hectic, more competitive field. W h a t should they learn. The big-picture question in computational molecular biology" is how to "do" as much "real biology" as possible by exploiting molecular sequence data DNA, RN A and protein.
Getting sequence data is relatively cheap and fast and getting more so compared to more tradi- tional laboratory investigations. The use of sequence data is already central in several subareas of molecular biology and the full impact of having extensive sequence d a t a is yet to be seen. Hence, algorithms that operate on strings will continue to be the area of closest intersection and interaction between computer science and molecular biology.
Certainly then, computer scientists need to learn the string techniques that have been most successfully applied. But that is not enough. Computer scientists need to learn h m d a m e n t a l ideas and techniques t h a t will endure long after today's central motivating applications are forgotten.
They need to study meth od s t h a t prepare t h e m to frame and tackle future problems and applications. Therefore, the computer scientist who wants to enter t h e general field of computational molecular biology and. Potential application, particularly of ideas rather t h a n of concrete methods, and to anticipated rather t h a n to existing problems, is a m a t t e r of j u d g m e n t and speculation.
No doubt, some of the material contained in this book will never find direct application in biology, while other material will find uses in surprising ways. Fonowing the above discussion, this book is a general-purpose rigorous t r e a t m e n t of the entire field of deterministic algorithms t h a t operate on strings and sequences.
M a n y of those algorithms utilize trees as data- structures, or arise in biological problems related to evolutionary trees, hence the inclusion of "trees" in the title.
The book is intended to be b o t h a reference, and a main text for courses in pure computer science, and for computer science oriented courses on computational biology. Explicit discussions of biological applications appear throughout the book, but are more con- centrated in the last sections of P a r t II, and in most of Parts III and IV. I discuss a nlwnber of biological issues in detail in order to give the reader a deeper appreciation for the reasons t h a t m a n y biological problems have been cast as problems on strings, and for the variety of often very imaginative technical ways t h a t string algorithms have been employed in molecular biology.
It only lightly touches on probabilistic analysis, does not discuss parallel algorithms, or the elegant, but very theoretical results on algorithms for infinite alphabets and on algorithms using only constant au.
The book also does not cover stochastic oriented methods t h a t have come out of the machine learniug comm,mlty, although some of the algorithms in this book are extensively used as subtools in those methods. W i t h these exceptions, the book covers all the major styles of thinlcing about string algorithms.
More important, it empha- sizes the ideas and derivations of the methods it presents, rather t h a n simply providing an inventory of available algorithms.
0コメント