Principles of Biomedical Informatics

Dedication To Terry Steele-Kalet, my wife and best friend, who kept me on track when things looked impossible, and stood by me through the most difficult times as well as the best of times.

Foreword

Biomedical informatics (BMI) is an extraordinarily broad discipline. In scale, it spans across genes, cells, tissues, organ systems, individual patients, populations, and the world’s medical ecology. It ranges in methodology from hardcore mathematical modeling to descriptive observations that use “soft” methods such as those of sociology. It studies, models and designs data, processes, policies, organizations, and systems. No wonder it is difficult to find (or write) a text or reference book that encompasses the field. Yet BMI has become a discipline, gradually moving from a variety of ad hoc collections of interdisciplinary programs towards a more formally defined specialty, recognized both as a subspecialty option for many fields of medicine and as a concentration in engineering programs. What distinguishes this field is its focus on a fundamentally computational approach to biomedical problems. Of course, every field in today’s age of information uses computation as a tool, but in other disciplines, other methods such as laboratory experimentation or systems design take pride of place. Adding to the challenge of presenting the fundamentals of BMI in a book is the varying depth to which concepts need to be understood (and thus explained) depending on what role the reader expects to play. For example, a high level manager such as a chief information officer needs a good layman’s understanding of all of the issues but generally cannot know the details of all the technologies he or she needs to deploy. Yet the software engineers building those systems need to understand intricate details of databases, communication mechanisms, human-computer interface design, image processing, design for safety, decision support, etc. Similarly, a researcher who directs a clinical trial must focus on a precise understanding of the biomedical question to be answered, the data and methods needed to answer it, the study design, and factors that help assess confidence in the results. Another researcher, studying problems in bioinformatics, needs a deep knowledge of molecular biology and the specific data being analyzed, graph theory, probability and statistics, and data mining and machine learning. Perhaps with time, we will develop a complex ecology of (sub-)subspecialties corresponding to these various clusters of required expertise, but our field is young enough that we have not yet defined these clusters, and indeed many individuals play multiple roles and need multiple types of expertise even at one time, or certainly throughout their careers. Another source of difficulties in teaching BMI is the large variety of backgrounds from which students are drawn. Many are MDs who choose to specialize in BMI after their formal medical training is complete, perhaps as part of a fellowship program. Many others are engineering students who find in the challenges posed by health care an appealing outlet for their talents and interests. Some come from backgrounds as librarians, in public health, health economics, management, or law. The intersection of all the subjects studied by people from such diverse backgrounds is close to nil. Therefore, developing classes to serve this population is highly challenging, because it is impossible to rely on almost any specific background. Yet, despite the diversity of applications and backgrounds, common themes have emerged in this discipline. Methods of data collection, encoding, standardization, storage, retrieval, visualization, exchange, and integration pervade the field. Model construction, validation, and analysis underlie most applications. xiii

xiv

Foreword

Pedagogically, many biomedical informatics courses of study have adopted an approach that begins with a broad introductory subject that surveys the field, but cannot, at the same time, present the details that will be needed in its various specialties. That is then followed by a Chinese menu of far more specialized courses, often drawn from the faculties of more established departments such as computer science, mathematics, statistics, economics, public health, etc. Yet, in most such courses, the topics of special significance to biomedical informatics are scattered among a variety of interesting, but perhaps not highly relevant, materials. As a result, many students must still piece together their BMI education from such an ad hoc assembly of classwork, readings in journals and conference proceedings, and mentoring by their research supervisors and colleagues. Although this is by no means a bad way to learn, as the field becomes more popular and therefore attracts more students, it is inefficient. It also demands a high level of pedagogic skill and inspiration from all teachers, which makes it difficult to establish new programs and exposes students to the risk of poorly thought-out curricula. Professor Kalet in this book tackles the question: Where should one turn after a broad introductory treatment of BMI? In contrast to the introductory books, he takes a frankly technical, computational approach, identifying those underlying methods that cut across the many goals of BMI training and research. Thus, the book begins with a discussion of the nature of biomedical data and how it can be represented in a computer, described, communicated, and analyzed. It then moves on to the representation and use of symbolic knowledge that can form the basis for building intelligent tools. Next, it covers probabilistic methods that are crucial for both representation and interpretation. Then, it introduces methods appropriate to build information retrieval systems, which focus on the vast literature of BMI and related fields and, at least today, are the only organized systems that contain most of the knowledge gleaned from decades of biomedical investigations. The second half of the book takes up a handful of interesting topics, both because they are important to the advancement of BMI research and because they serve as wonderful illustrations and challenges to the methods presented earlier. These include computational methods critical to bioinformatics, such as computing with gene and protein data, the representation and search for biological networks, representation of structures such as those that define anatomy, and the search for a reliable system to analyze and record drug interactions. Other chapters touch on standards and medical data communications, cancer radiotherapy planning, and system safety and security. What unifies these topics is a commitment to the idea that simple familiarity with such concepts is not enough – instead, the serious student and practitioner must develop the skills to program and implement the various methods being described. This book provides a coherent and consistent presentation, and all of the examples and concepts are worked out in an extraordinarily expressive and flexible programming language, Lisp. Although the book is by no means a book about programming, it demonstrates the fundamental reliance of complex BMI ideas on elegant programming implementation. As Benjamin Whorf famously argued,1 (human) language influences the ways in which we think. Because Lisp uses a very regular, simple syntax and supports powerful methods for defining and using abstractions, it is particularly well suited to the task at hand here. As a result, many examples that could require distractingly tedious and complex implementations in more common programming languages can be done simply in Lisp and retain their logical structure in the implementation. Programming is essential to BMI. It forces us to specify ideas and methods in precise enough ways that a computer can execute them. It is the manner in which we enlist the help of computers to support the management and exploitation of data, and to interact with us to support the human processes that we undertake. In the past decades, we have moved from an era of unimaginably expensive computers to ones that are cheap enough to embed in every appliance. As a result, the equation defining the costs of projects has shifted completely from the “expensive computer/cheap programmer” model to the opposite. Thus, development of abstractions and tools that make it easy to conceptualize and implement new techniques provides more leverage than ever, and some of the most important advances are those

1. John B. Carroll, ed. Language, Thought, and Reality: Selected Writings of Benjamin Lee Whorf. MIT Press, 1964.

Foreword

xv

that improve the capabilities and efficiency of BMI practitioners. With today’s tools, it is still much easier to conceptualize a new study or a new process than to implement it. However, groups that traditionally separate conceptualization from implementation have not accrued a good track record. Instead, it seems that programmers need to understand the domain for which their programs are being built, and designers need to understand the constraints imposed by programming realities. Indeed, the high costs of programming staff dictate that many junior BMI researchers must act as their own programmers. Therefore, BMI cannot be studied in isolation from computer programming methods and techniques. Professor Kalet brings to this book extraordinarily broad experience and a deep understanding of the topics he presents. He received his PhD in theoretical physics; has taught physics, mathematics education, and even liberal arts; has worked professionally in radiation oncology; held professorial appointments in radiation oncology, medical education and biomedical informatics, computer science, biological structure, and bioengineering; has been responsible for security and networking for a hospital IT network; and has created and led a graduate program in biomedical and health informatics. Thus, he represents in one person the interdisciplinary threads of the field this book is helping to define. In addition, he is a lucid and careful expositor, and so the lessons of the book are within reach of the diverse audience it seeks to serve. Early in our new millennium, despite great advances in health care and the research that supports it, we are surprised by the slow development of methods that improve actual clinical practice; we are frustrated by pathologies in the way health care is delivered and paid for; and we are both daunted and challenged by the vast opportunities that are being opened by new biological insights, improved measurement methods, and our greatly enhanced abilities to collect and analyze vast amounts of empirical data on everything from how molecules interact within a cell to how medical services interact in a population. We are, indeed, in a time of ferment, excitement, and challenge for biomedical informatics. As Alan Perlis said, “I think that it’s extraordinarily important that we in computer science keep fun in computing.”2 The same is surely true of BMI. This book will contribute to that fun. Peter Szolovits Cambridge, Massachusetts May 2008

2. Alan J. Perlis. The keynote address. In Perspectives in Computer Science, Anita K. Jones, ed. Academic Press, 1977.

Preface

One of the great challenges of biomedical informatics is to discover and/or invent ways to express biomedical data and knowledge in computable form, and to thus be able to automate the analysis and interpretation of a wide range of biomedical data as well as facilitate access to biomedical data and knowledge. Biomedical informatics textbooks , typically present a survey of such ideas and applications but do not discuss how these ideas and applications are actually realized in computer software.1 Bioinformatics books typically have either narrow focus on sequence analysis algorithms and other statistical applications, or on how to use a wide variety of existing software tools. Some of the bioinformatics books, on closer inspection, are really about the underlying biology with little or no reference to computerized data or knowledge modeling except as a (usually mysterious) means to arrive at biological results, reported as text and/or diagrams, rather than in computable form. Others, both biological and medical, focus on sifting through the arcane and problematic syntaxes of various data sources, and the trials and tribulations of extracting useful data from natural language text. A recurring theme in discussions with biologists, medical researchers, health care providers, and computer scientists is the question, “What is biomedical informatics?” The practical answer, that is, to provide the software tools to meet biomedical research and clinical practice computing needs, addresses a real need but seems inadequate to define the intellectual content of the field of biomedical informatics. Thus, the main goal of this book is to provide an exposition of important fundamental ideas and methods in biomedical informatics using actual working code that can be read and understood. The object of the code is not only to provide software tools but also that the code should play the same formal role that equations and formulas play in theoretical physics. That is, the programs precisely embody biological, medical, or public health ideas and theories. The application of these programs to specific

1. Recent exceptions include , , , which include some perl scripts, and argue for the importance of learning something about programming.

xvii

xviii

Preface

problem instances and data is analogous to the solution of the equations of physics for specific practical problems, for example, the design of airplane wings. This is not a book about artificial intelligence (AI), or at least it does not take the viewpoint typical of AI books. My viewpoint is that of a scientist interested in the creation and study of formal theories in biology and medicine. Whether such theories embody some notion of intelligence is not relevant here. Some of the topics covered may make this book strongly resemble an AI textbook, because the ideas and languages of this branch of computer science are the right ones for modeling a wide range of biological and medical phenomena, just as differential equations, vector spaces, abstract algebra, and related areas of mathematics are the right ideas and languages for creating theories of physical phenomena. One implication of this view is that researchers in biology, medicine, and public health will learn computational science (including programming languages and how to write programs) as a part of their training. Understanding, writing, and using computer programs will be an essential part of understanding the biology, medicine, or public health phenomena, not just a bunch of machinery to be purchased and used. While the predominant view in this book is that of computer programs as implementation of formal theories, it is not the only way that computable knowledge in biomedicine is used. In regard to formal theories, biology and medicine are relatively young (compared to the physical sciences, particularly physics). Much knowledge is in small chunks like jigsaw puzzle pieces. Irrespective of whether you believe you can fit the pieces together to form a coherent theory, many people find it useful to organize, index, and search collections of such chunks to solve important practical problems. This too is an important part of biomedical informatics. Thus, Chapter 2 includes some discussion of knowledge as a collection of assertions that may or may not be a complete theory of a biomedical domain. It is developed more fully in Chapter 4, on biomedical information access, as well as in some chapters in Part II. There are precedents for using computer programs as renditions of subject matter, not just examples of programming techniques or programming language syntax and semantics. They are an inspiration for this work. Norvig’s book, Paradigms of artificial intelligence programming , explains fundamental ideas of artificial intelligence by showing how to build programs that implement these ideas. Abelson and Sussman’s well-known Structure and interpretation of computer programs is really about computation ideas and principles, and not about how to do programming in Scheme. More recently, Sussman and Wisdom have written a remarkable new treatment of classical mechanics , not from the point of view of traditional numerical approximation of solutions of differential equations but from the point of view of expressing the foundational concepts directly in a computable form. My goal similarly is to write about biomedical informatics ideas by showing how to write programs that implement them.

Structure of the Book Defining what is essential, and for what purpose, is an intractable problem. – Cornelius Rosse and Penelope Gaddum-Rosse from the Preface to “Hollinshead’s Textbook of Anatomy”

The chapters in Part I, Foundations of Biomedical Informatics, develop the principles, ideas, and methods that constitute the academic discipline of biomedical informatics. These can be organized loosely into biomedical data representation, biomedical knowledge representation, organization of biomedical information (both data and knowledge), and information access. Biomedical knowledge representation, as inherited or adapted from the field of artificial intelligence, can be loosely divided into categorical or symbolic methods and ideas, and probabilistic methods and ideas. Thus, the book begins with representation and transformation of biomedical data. Next, ideas and methods for symbolic and probabilistic biomedical knowledge are presented. This part concludes with an introduction to ideas and methods for biomedical information access, addressing both data and knowledge. Thus, Part I roughly corre-

Preface

xix

sponds to the “Biomedical informatics methods, techniques and theories” at the top of Ted Shortliffe’s well-known diagram, found on page 32 (Figure 1.19) of . Part II, Biomedical Ideas and Computational Realizations, provides a series of applications of the principles, illustrating how to express biomedical ideas, data, and knowledge easily in computable form. The chapters include examples from various biomedical application domains, but are not in any way comprehensive in coverage. The areas addressed include molecular and cellular biology, human anatomy, pharmacology, data communication in medicine and radiology, and radiation oncology. Thus, Part II traverses the horizontal axis of Shortliffe’s diagram mentioned above. Some additional topics are included in Part II. Chapter 5 develops ideas on how to simulate systems that change with time, using state machines and other formalisms. Chapter 10 treats issues around the design of medical device software and the deployment of electronic medical record systems and medical devices in a network environment. Standards are briefly mentioned in Part I, and two particular examples, HL7 and DICOM, are developed in more detail in Chapter 8. The Appendix provides reference material on the programming languages and environments used in the book. It also includes pointers to resources for pursuing some of the engineering aspects of building a practical system in more depth. As Rosse and Rosse suggest, not everything can be included in a single book. I have left out topics in bioinformatics and computational biology that appear to be well covered elsewhere and are somewhat far from the overall themes of this book. These include the more complex sequence analysis algorithms, searching sequences for motifs, and generating phylogenetic trees, to mention a few. Although I have included in Chapter 5 an introduction to simulation using state machines, I do not go into much depth about the details of systems biology markup language or the many projects that are active. The references in that chapter should be useful as a link to get more deep into these topics. Another notable omission is the vast subject of electronic medical record systems and the representation and use of clinical guidelines. Nursing and public health were in the original plan for the book, but time did not allow to develop and include examples from these areas, except for the use of a public health problem in Chapter 2. Finally, the topic of data mining, or machine learning, although growing rapidly in importance, is not covered here, in the interest of keeping the book of a manageable size and finishing it in a finite time.

Software Design and Engineering There is a crisis in biomedical software today. The NIH has recognized the importance of computing in biomedical research through the Biomedical Information Science and Technology Initiative (BISTI). The cost of building custom (one of a kind) programs of any scale for each research team is usually prohibitive. Yet, commercial software packages are often not adaptable to the specific needs of research labs, let alone the complexities of clinical and public health practice. It is certainly not a matter of taking advantage of existing technology that has been produced by computer scientists. The problems of data integration, design of extensible and flexible software systems and programming environments, and matching different data models and modeling systems are all important research questions in computer and information science. The emerging partnership that BISTI promises to promote is critical for the future of biomedicine. Beyond BISTI, the NIH is also calling for researchers to include plans for dissemination, education, and support to proposals that include substantial software development. This is an encouraging development, because few places can do such work without significant investment of staff time. Significant issues in biomedical informatics that are sometimes overlooked are code reuse and software engineering. While the enthusiasm for “open source” software development is growing rapidly, there is little discussion of best practices in software design, and the result is a large body of freely available code that is notoriously difficult to extend or modify. Many advocates of “open source” seem to believe that, this approach by itself, will produce (by some evolutionary process) high-quality software.

xx

Preface

This is insufficient for the crisis we face today, especially in critical safety applications such as clinical medicine. The examples I develop in Part II are intended to be exemplars of good software design as well as clear illustrations of the underlying principles. The challenge is even greater in health care than in biomedical research. Software inadequacies, errors, and failures have been shown to be directly or indirectly responsible for serious injury as well as death to patients . Regulatory agencies such as the US Food and Drug Administration (FDA) face a daunting job of dealing with this on the scale of very complex electronic medical record systems with huge numbers of hardware and software components. Vendors of medical software are not experienced in designing multiuser or real-time systems (computerized medical devices), and they are especially inexperienced at designing systems that are robust and safe to operate with connections over the open Internet. Chapter 10 explores these questions from the perspective that something can indeed be done to prevent or minimize the hazards. In this chapter, we explain the necessity of Internet connectivity for medical devices and systems, and address the dangers as well as some preventive measures in connecting computerized medical equipment and data systems to the Internet.

Programming Languages A language that doesn’t affect the way you think about programming is not worth knowing. – Alan J. Perlis

The main programming language used in this book is Common Lisp. Previous exposure to Lisp is not assumed. To help the reader familiarise with Lisp, Chapter 1 provides a introduction to the essential ideas, along with discussion of biomedical data and their representation. However, the reader who is already familiar with the general culture and tools of programming will have a much easier time than one who is not familiar with text editors (the best of which is, in my opinion, emacs), operating system command interpreters, file systems, and basic network operations and facilities. Previous experience with a specific programming language can be a help or a hindrance, depending on the reader’s willingness to see the programming idea in radically different ways (or not). In teaching this subject, I occasionally find that I have to help a student unlearn ideas picked up from an exposure to C or java, in order to learn very different styles of abstraction. A goal of this book is to refocus thinking about biomedical informatics programming, not as a technical skill for manipulating bits and bytes but as a natural, logical, and accessible language for expressing biomedical knowledge, much as how mathematics is used as the universal language for expressing knowledge in the physical sciences. Lisp is used in this work because it was designed for building these abstractions, higher level languages, and extensions. As bioinformatics moves from the data-intensive stage of searching and correlating massive amounts of raw data to the knowledgeintensive stage of organizing, representing, and correlating massive numbers of biological concepts, the expressive power and efficacy of Lisp will become even more important. From the very beginning of informatics research in medicine, Lisp has been a prominent choice of programming language. In medicine and biology, much of knowledge (as well as data) is nonnumeric. Lisp is particularly well suited to this. However, Lisp is also fine for numeric computation, user interface programming, web applications, and many other things. So, the importance of Lisp in biomedical informatics should not be underestimated by thinking of it as only the language people (used to) use for artificial intelligence research. Its power comes from the ability to easily create abstraction layers and programs that transform expressions before evaluating them. This makes it easy to define higher level languages in Lisp, which provide just the right tools for efficient problem-solving. Also in Lisp, functions can be manipulated as data: new functions can be written by other functions and then used. While this may seem mysterious and useless to a programmer new to Lisp, once you see how it works, you will wonder how people could write programs without it (cf. Graham [, Chapter 1]).

Preface

xxi

As biomedical data and knowledge become increasingly complex and the software to manage it grows in scale, it is almost a truism to emphasize how important it is to effectively use abstraction and layered design. Lisp is also important because it has proven to be best suited to these goals. I chose Common Lisp (one of the two major contemporary dialects of Lisp) because it has all the technical support to write “industrial strength” programs that perform as well or better than programs written in more popular programming languages such as C++, java, and perl. Common Lisp has a very solid and powerful object-oriented programming facility, the Common Lisp Object System (CLOS). This facility provides a flexible means to write extensible code; indeed, CLOS is built on its own ideas and includes a meta-object protocol (MOP), which provides ways to extend and augment CLOS itself without needing or modifying any CLOS source code. Common Lisp also provides a macro facility that makes it easy to write code that transforms expressions, that is, it supports writing interpreters for higher level (but embedded) languages for special-purpose tasks. Lisp is a fine general-purpose programming language. It has been shown to be easier to use than C or java, and compilers are available to generate code that runs as fast or faster than equivalent code written in C. It certainly supports higher performance than java. A recent study by Ron Garrett (formerly Erann Gat) demonstrated these and other important points. Some characteristics that distinguish the Lisp language include: 1. Lisp programs generally take fewer lines of code than other languages to solve similar problems, which also means less development time, fewer programmers, lower cost, less bugs, and less management overhead. 2. Lisp has lots of built-in tools and facilities for tracing execution of programs, testing small and intermediate components, and thus programs written in Lisp tend to be easier to debug than programs written in other languages. 3. Lisp has lots of libraries and a large freely available code-base, including support for high performance 3D graphics, user interfaces and network socket programming, plenty of support from Lisp software vendors, and a significant number of Lisp programmers. 4. Many myths about Lisp have circulated over the years but are untrue (for commentary on this, see , ). 5. Most importantly, Lisp provides a superb interactive programming and execution environment. Use of Lisp for solving problems in biomedical informatics has experienced slow but steady growth in recent times. There are many web sites and numerous code libraries and programs to perform specific tasks, but it remains daunting to a new informatics researcher and programmer to become familiar with the advanced programming ideas and the skills needed to utilize existing facilities and contribute to this field. Too often, the well-trodden but a less powerful path of programming in the conventional languages and styles is adopted and taught. This is done despite the availability of several good introductions and working environments. Fortunately, several good books are available. They are described in Appendix A.1.4. Some examples also use the Prolog programming language. Prolog is a programming language designed to represent logic systems, principally first order logic restricted to Horn clauses. Simple Prolog-like interpreters have been written in Lisp, and indeed Lisp has also been used for logic programming and constraint programming, but the availability of excellent (and free) Prolog systems also makes it attractive to use Prolog directly. Prolog is important for the same reasons as Lisp, because it provides a more abstract symbolic language to directly express biologic concepts rather than encoding them in more machine-like data structures. Many people have asked, “Why use Lisp and Prolog? Why not use java or perl (or Python or Ruby, etc.)?” The above answer should be sufficient, that the best language to represent abstract ideas is one that supports abstract symbols and expressions (lists) directly. It is possible to mimic some of this in java, perl, etc., but it is makeshift at best. I would ask (and have asked) the opposite question, “Why would anyone use java or perl, when Lisp seems more appropriate?” The responses always include exactly two reasons: first, everyone else is doing it, and second, there is a lot of support for these languages. This is not sufficient justification to make a technically inferior choice, especially

xxii

Preface

in view of the fact that there are plenty of choices of robust Lisp and Prolog implementations (both free and commercial) and a critical mass of users of both. Significant bioinformatics work is done with Lisp and Prolog. Appendix A, Section A.3, provides a brief summary of some of the more noteworthy projects with pointers to publications and web sites.

Biology, Medicine, and Public Health What should the reader know about biology, medicine, and population health? A basic background in modern biology will help considerably. Although many concepts are introduced as needed, the treatment is brief and not really a substitute for basic textbooks in molecular biology, genetics, anatomy, physiology, clinical medicine, or public health. The reader should be familiar with basic concepts of modern biology (genes, proteins, DNA, basic functions of living organisms), and have some experience with disease, treatment, and the health care system.

Mathematics Traditional mathematics does not play a prominent role, except in Chapter 3, which includes a modest introduction to statistics. As an excellent background for logical thinking and problem-solving, a basic understanding of Calculus is highly desirable. An understanding of the mathematical idea of a function in the abstract sense is of considerable help in understanding computer programs. The idea of procedural abstraction, or defining layers of functions, is essential to building large and powerful programs.

Notes on Typography In this book, code and data are distinguished from the rest of the text by using a different font. Blocks of code that define functions, classes, etc., are shown without a prompt. When the intent is to show a dialog, that is, to illustrate what happens at the interactive read-eval-print loop, a prompt is shown. Different Common Lisp implementations use their own style of prompt. Here, we follow the same convention as in Graham , the “greater-than” symbol >.

How To Use This Book My main objective in writing the book is to provide a principled exposition of the foundational ideas of biomedical informatics. It provides a solid technical introduction to the field and a way to gain deeper insights into familiar biomedical computing ideas and problems. I hope that experienced researchers and practitioners in biomedical and health informatics will find it a useful synthesis of the technical aspects of our field. The intended audience also includes: ●

●

biologists, clinicians, and others in health care who have little previous exposure to programming or a technical approach to biomedical informatics, for whom an introduction to symbolic computing and programming is provided as needed in the first few chapters, computer scientists, mathematicians, engineers, and others with technical backgrounds who have an interest in biomedical informatics but not much exposure to biology or medicine, for whom I have introduced some basic ideas in molecular and cellular biology, human anatomy, pharmacology, clinical medicine, and other biomedical areas, and

Preface

●

xxiii

students interested in biomedical informatics as a field of study and potential career, including undergraduates, medical and health professional students, graduate students in biomedical and health informatics, and related fields (computer and information sciences, basic biological sciences).

The book can thus serve as a text for a course in several contexts. It has been prototyped in a course I have taught for several years, “Knowledge Representation and Reasoning in Biology, Medicine, and Health.” The material in the book is too much to be reasonably covered in one quarter. Two quarters would be comfortable. The KR course covers the material in Chapters 1, 2, 3, and parts of Chapters 5, 6, 7, and 9. Topics in other chapters have been included in another course I taught, called “Life and Death Computing.” Other combinations are possible too.

Acknowledgments The idea for this book originated in a discussion with Pete Szolovits at the 1999 American Medical Informatics Association (AMIA) Fall Symposium. I had just started to teach a course in biomedical informatics to medical and health professionals and students who had no prior computing background. The regular introduction to programming taught by the computer science department was not a very satisfactory option. I learned from Pete that the biomedical informatics students at MIT took a version of the famous “Scheme” course 6.001, which was very challenging. We talked about the idea of having a book that introduced biomedical informatics along with programming in some suitable language (obviously Lisp), along the lines of Norvig’s AI text . Time passed and many discussions took place before that idea became concrete enough to attempting to write such a book. Pete not only encouraged me to do it but also provided significant example codes, lots of references, and continuous reassurance when the project seemed intractable. His editorial advice has been invaluable. My interest in computing started during my freshman year in college in 1961 when I learned that the Cornell University computer center provided free student access to its Burroughs 220 computer (the picture at the opening of the Preface shows me in 1962 at the operator’s console). I taught myself Burroughs 220 assembly language and began my first programming project. The goal of this project was to replicate some experiments in composing music automatically according to rules of harmony, voice leading, and some modern composition techniques. The experiments I wanted to replicate and build on were done by Lejaren Hiller and Leonard Isaacson , whose work resulted in a composition, “Illiac Suite for String Quartet,” named for the computer they used at the University of Illinois. I soon realized that neither assembly language nor languages like Algol and FORTRAN were suitable for this task. I did not know that a very powerful programming language called Lisp had just been invented to exactly express these kinds of symbolic, abstract ideas. I also did not know that this kind of programming was called “artificial intelligence.” Nevertheless, it was my start. It is a pleasure to thank my high school classmate, Eric Marks, who taught me music theory and got me interested in that project. It set the stage for my later interest in software, which led me to get involved in the development of radiation therapy planning systems, artificial intelligence in radiation therapy planning, and from there to biomedical informatics. Funding for this “Scholarly Works” project was made possible by Grant 1 G13 LM008788 from the National Library of Medicine, NIH, Department of Health and Human Services (DHHS). The views expressed in this book and any related written publication or other media do not necessarily reflect the official policies of the DHHS; nor does the mention of trade names, commercial practices, or organizations imply endorsement by the US Government. Illustrations noted as “courtesy of National Human Genome Research Institute” (NHGRI) are in the public domain and are from the NHGRI Talking Glossary web site.2 The illustration from the National

2. http://www.genome.gov/10002096.

xxiv

Preface

Institute of General Medical Sciences (NIGMS) is from the Protein Structure Initiative image collection web site.3 It is a pleasure to acknowledge the encouragement and advice of Valerie Florance, Deputy Director, Extramural Programs, National Library of Medicine, from whom I first learned about the NLM Publication Grant program, as well as many stimulating conversations with Milton Corn, Director, Extramural Programs, National Library of Medicine. Many other people have contributed ideas and code to the book. They are gratefully acknowledged here. However, any errors or inaccuracies are solely the responsibility of the author. The book is typeset using LATEX 2ε , . The figures showing the formulas for the molecules appearing in various chapters are produced with Shinsaku Fujita’s XΥMTEX package set , a system for typesetting chemical structural formulas. ●

●

●

●

●

●

●

●

●

Larry Hunter, Peter Karp, and Jeff Shrager provided much editorial advice, as well as encouragement. Larry is the source of the amino acid representations in Chapter 5. The biochemical pathway search idea and the cell cycle simulation in that chapter are based on Jeff Shrager’s tutorials on his BioBike web site . Ted Shortliffe, Michael Kahn, and John Holmes provided strong encouragement, especially in support of my application for the NLM Publication Grant that has supported much of the writing. Jesse Wiley suggested the example application of DNA sequence processing introduced in Chapter 1 and developed further in Chapter 5. Thanks also to Alberto Riva for permission to use code from his CL-DNA project , which provided some ideas on how to implement the examples. Mark Minie provided pointers to the NIGMS and MHGRI image collections as well as interesting and provocative discussions about the foundations and future directions of molecular biology. The chapter on the Foundational Model of Anatomy comes out of a long-standing collaboration with the UW Structural Informatics Group. Thanks go specifically to the Digital Anatomist project for providing the brain figure in Chapter 1 and the heart figure in Chapter 6. It is a pleasure to thank especially Jim Brinkley, Cornelius Rosse, and Jose L.V. (Onard) Mejino for help with the FMA and the CTV projects described in Chapter 9. Onard also contributed the figure in Chapter 6 showing the lymphatic tree parts. Thanks to Richard Boyce, John Horn, Carol Collins, and Tom Hazlet for permission to incorporate material from our drug interaction modeling project in Chapter 7. This work began as a simple class exercise where I taught biomedical programming (the Life and Death Computing course). Richard Boyce, then a Biomedical and Health Informatics PhD student, took it up, refined it, and added the idea of managing evidence by categorizing it and using a Truth Maintenance System. John Horn, Carol Collins, and Tom Hazlet contributed much pharmacokinetic knowledge as well as modeling advice. Thanks also to Richard Boyce for providing the example and introduction to decision modeling in Section 3.3.1 of Chapter 3. It is a pleasure to thank Dave Chou for the sample HL7 data in Chapter 8 as well as many helpful discussions about HL7, LOINC, and EMR systems. The design ideas as well as the implementation of the Prism DICOM System at the University of Washington were the work of Robert Giansiracusa in collaboration with the author as part of the Prism Radiation Therapy Planning System . What I present in Chapter 8 is a simplified version, with some variations, to explain the implementation. Appendix A includes a pointer to the original DICOM source code. The development of the DICOM code took place during my several visits to the Oncology Department at Soroka Medical Center, Israel, affiliated with Ben Gurion University. I owe a great deal of thanks to my host and friend, Yoram Cohen, for his kindness, encouragement,

3. http://www.nigms.nih.gov/Initiatives/PSI/Images/Gallery/.

Preface

●

●

●

●

●

●

xxv

and support. Many others at Soroka and BGU helped in this project, notably Drora Avitan and Yanai Krutman. The Prism project described in Chapter 9 had many contributors, but especially I would like to acknowledge the contributions of Jon Unger and Jon Jacky, who were co-authors of both the code and the documentation. Jon Jacky and I collaborated for approximately 20 years on three major radiotherapy treatment planning projects, of which Prism was the third. Jon Jacky was also a contributor to the DICOM system, which is a part of Prism. The ideas for modeling simple safety issues for radiation therapy machines in Chapter 10 also originated with Jon Jacky, as a guest lecturer in one of the classes I taught. It is a pleasure to thank Mark Phillips for help with the ideas in Chapter 3, and for being a wonderful colleague for many years, including working on Prism and related projects described in Chapter 9. The Clinical Target Volume project described in Chapter 9 is an ongoing project with many collaborators. In addition to Jim, Cornelius, and Onard mentioned earlier, Mary Austin-Seymour, George Laramore, Mark Whipple, Linda Shapiro, Chia-Chi Teng, Noah Benson, and Casey Overby deserve special mention. The Planning Target Volume project described in Chapter 9 was the work of Sharon KromhoutSchiro for her PhD dissertation in Bioengineering at the University of Washington. The UW Medicine IT Services Security Team has taught me a lot about hospital IT security, what works and what does not. It has been a pleasure to work with them all. Thanks to Brian Kalet for the cover design.

The support of the faculty of the Biomedical and Health Informatics program at the University of Washington is much appreciated, particularly Fred Wolf, Chair of the Department of Medical Education and Biomedical Informatics, Peter Tarczy-Hornoch, Head of the Division of Biomedical and Health Informatics, and George Demiris, Graduate Program Coordinator. Thanks also go to Wanda Pratt for her encouragement of this project and her willingness to make her DynaCat program available. I was not able to include the DynaCat program because of limits of space and time, but hopefully there will be a second edition. Thanks to George Laramore, Chair of my home department, Radiation Oncology, and to colleagues in Radiation Oncology for their encouragement and interest. Over the last few years, many students have read and commented on drafts of manuscript and, have been subjected to assignments that eventually became material in the book. Although there are too many to name, I greatly appreciate all their feedback and involvement with this material. Steve Tanimoto and Alan Borning welcomed me as an adjunct faculty member to the University of Washington’s Computer Science and Engineering Department in 1983. Their hospitality and that of their colleagues has been nothing short of wonderful. I would like to acknowledge the kind advice, support, and guidance of the late Peter Wootton, Professor of Radiation Oncology (Medical Physics), who was my mentor from 1978 when I joined the University of Washington as a postdoctoral fellow in medical physics, and a dear friend until his passing away in 2004. My advisor from graduate school, Marvin L. (“Murph”) Goldberger, has kept in touch over the years and offered valuable reassurance even though I did not stay with theoretical physics. His kindness is gratefully acknowledged. Finally, I would like to acknowledge the editors at Academic Press, Luna Han, Kirsten Funk, and especially Christine Minihane and Rogue Shindler, who helped enormously in pushing the manuscript to completion.

Part I

Foundations of Biomedical Informatics

For many centuries, biology and medicine have been organized principally as descriptive sciences, with much less emphasis on elaborate theories and deduction than on remembering and applying the right chunks of knowledge and experience to experimental or clinical problems. Now, that is changing, and a new era of biomedical science is here. This new era is not only one in which we are awash in a massive flood of data, but one in which deep computational power can be brought to bear on biomedical problems. It is the “coming of age” of a new intellectual discipline, Biomedical and Health Informatics. Essential to this new discipline is the application of formal ideas such as logic, probability, and computational methods for organizing and manipulating large-scale repositories of both data and knowledge. The data and knowledge take both numerical and symbolic forms. The organizational structure of data and knowledge is an essential part of the enterprise, not just a convenience. Biological data and knowledge are in fact sequences, tree structures, networks of relationships, and so on. For a biologist, clinician, or public health practitioner to deal with this, it requires substantial familiarity with a language for expressing

2

PART | I Foundations of Biomedical Informatics

computational ideas, formal structures, and procedures (algorithms), namely a programming language. For a computer scientist, mathematician, or statistician, it will require understanding biology, medicine, and population health data and knowledge, and how it can be expressed in computational language. A central goal of this book is to provide an exposition of these ideas and methods. Part I presents the principles and methods by which biomedical data and knowledge can be represented, organized, and used in computational form. Chapter 1 focuses on data in various forms, from molecular sequences to medical images. It includes a brief introduction to database principles and techniques as well as how to represent data with tags and hierarchical structures. Chapter 2 presents ideas for representing and reasoning with knowledge in symbolic form, while Chapter 3 introduces elementary probability and statistical methods for representing and computing with uncertain biomedical knowledge. Chapter 4 describes how information retrieval systems work and how to deal with the challenges of indexing and retrieving biomedical documents and other kinds of biomedical information. While text and biomedical images may seem to be polar opposites in terms of content, some of the same techniques can be applied to both. Part II develops applications in biology and medicine, and also includes some important topics in building safe and robust systems.

Chapter 1

Biomedical Data 1.1 The Nature and Representation of Biomedical Data 1.1.1 What Can Be Represented in a Computer? 1.1.2 DNA and the Genetic Code 1.1.3 Anatomy 1.1.4 Medical Laboratory Data 1.1.5 Medical Images 1.1.6 Metadata 1.2 Objects, Metadata, and Serialization 1.2.1 A Simple Solution Using Tags (Keywords) 1.2.2 An Object-oriented Design 1.2.3 A Better Solution Using Meta-objects 1.2.4 Medical Images: Incorporating Binary Data 1.3 XML 1.4 Database Systems and Ideas 1.4.1 The Relational Model 1.4.2 The Entity–Attribute–Value Model 1.5 Data Quality 1.6 Data, Information and Knowledge 1.7 Summary

Just the facts, ma’am… – Sergeant Joe Friday Dragnet TV series, circa 1956

It is a truism to say that biology, medicine, and public health are flooded with facts. The complete genetic sequences of many organisms from bacteria to human beings are now available. We also have many terabytes of data on the structures of the proteins in these organisms. The biomedical literature is rich with laboratory results, case studies, and clinical trial reports. Repositories exist that contain large amounts of public health surveillance and epidemiolgic data. Electronic medical record systems are being deployed in many hospitals. It is a wonderful time for research and for the potential improvement of health care practice, except for one big problem: there is no coherent system for relating all or even part of the data. Worse yet, every repository and source of information seems to have its own arcane

Principles of Biomedical Informatics Copyright © 2008 by Academic Press, Inc. All rights of reproduction in any form reserved.

3

4

PART | I Foundations of Biomedical Informatics

syntax and semantics for organizing and representing the data. It makes the Tower of Babel, with only 70 different languages,1 look like a simple problem. Biomedical data come in many forms. They include data about the fundamental molecules of life, the small molecules that are used by living organisms for energy and as building blocks for reproduction and growth, and the large molecules that encode all the information about molecular processes such as metabolism and regulation of cellular activity. At a higher level in complex organisms like humans, we have a large amount of data about physiological processes and the behavior of organs such as the heart, data about individual patients in hospital electronic medical record systems, and public health surveillance data, to mention just a few. In the area of public health especially, the potential for enriched data useable for surveillance, for epidemiologic studies, and for understanding the impact of public health planning and intervention is huge. The Physiome Project (http://www.physiome.org/) is a systematic effort to create comprehensive databases of data and models of physiological processes. The project web site defines the Physiome as follows: “The physiome is the quantitative and integrated description of the functional behavior of the physiological state of an individual or species.” Indeed, we now have the ability to accurately model components and in some cases whole organs. The sophistication of these models is sufficient in some cases to be useable for interactive simulation systems for teaching clinical cognitive skills [291, 292]. The ideas behind simulation modeling will be introduced in Chapter 5. As our understanding increases of the entities and processes these data describe, new possibilities will emerge. Discussions are already taking place about the eventual widespread use of DNA sequencing and other high-throughput data acquisition in the practice of clinical medicine. Much research is directed to identifying genetic markers that will help determine the prognosis of disease and guide selection of treatments. Medical imaging techniques are developing not only towards higher spatial resolution but also towards diversifying the kinds of information that an image represents. We already now have a variety of functional imaging techniques, such as positron emission tomography (PET), where the images indicate levels of certain kinds of metabolic activity rather than anatomical structure. To combine these data sources in a way that makes sense for medical decision-making is already a huge computational and conceptual challenge. The growth of capacity, speed, and availability of the Internet has also opened new challenges. For researchers, it has become imperative but very difficult to make large data sets available to other researchers and similarly to make it possible to compute correlations and combine data from diverse sources. For medical practitioners, integration of access to patient data in electronic medical record systems has been called for at the highest levels of medical community leadership and the US federal government. It remains an elusive challenge. Similarly, for patients to get access to their own information is widely acknowledged as very important, but systematic solutions are not forthcoming. The varieties of biomedical data have some biological and technical aspects in common. Some of the technical aspects include how to encode something that is not a numeric measurement (gene and protein sequences, organ names and relationships, descriptions of clinical findings, names of diseases, etc.), how to organize both numeric and nonnumeric data for easy retrieval and interpretation, and how to represent hierarchical relationships or groupings of data that have an a priori relationship (e.g., a collection of genes whose expression levels are being measured or a set of related blood tests). Some of the biological aspects include how to represent higher level phenomena (e.g., phenotypes, diseases, and therapies) in relation to lower-level ones (e.g., genotypes, cellular and organ level processes, and body structure), and how to systematically and consistently assign names and classifications to all the entities, processes, and relationships [276].

1. The story, in Genesis, Chapter 11, names the 70 nations descendant from Noah, initially all speaking the same language, but one could infer that the “confounding of language” that happened gave each their own language.

Chapter | 1 Biomedical Data

5

The representation and organization of biomedical data require consideration of three dimensions of ideas. Context: Data will need to be represented in the context of running programs, where the data are volatile. When the program terminates, the data disappear. In order to be able to preserve the results of data input and computations, it is necessary to have a second context, a representation of data in files or other forms of non-volatile storage so that they have long-term persistence and can be searched, retrieved, and updated. Finally, a third context is that of network communication, where the data need to be represented inside network messages. Many standards have been (and are being) developed for storing biomedical information in files and transmitting it over a network. Standards are needed for application programming interfaces (API) for access to biomedical information from within running programs. Encoding: The choice, for each data element, of how it will be represented in context in machinereadable form is called an “encoding.” Each encoding of information requires that some description exists, specifying the encoding. This can be implicit, that is, described in technical documents and implemented in the source code of computer programs. It can also be done with metadata, that is, the encoding and structure are specified in a data description language (which itself is implicitly specified). Another option is to create so-called self-describing data, where the encoding and structuring are at a sufficiently low level that the metadata can be incorporated with the data. The encoding problem has generated considerable effort at standardization as well as innovation. All of these strategies have a place in biomedical informatics. Structure: For each kind of data in the various contexts, the structuring or grouping of data elements into larger logical units and the organization of these logical units in a system need to be decided. Appropriate structuring of biomedical information depends (among other things) on its intended use. Many ideas are applied here, including tables consisting of records, each with identical structure and encoding, object-oriented styles of structure, with many complex data types, often hierarchically related, logical networks, logical expressions with symbols, etc. The organization of such structures ranges from relational databases to object-oriented databases to semi-structured systems of selfdescribing data as well as biomedical ontologies with their own external forms. In this chapter, we present a series of biomedical examples illustrating these dimensions. Depending on the design, the dimensions can be orthogonal (independent) or very dependent on each other. Work in all of these areas is guided by some considerations of ease of use, that is, is it easy to retrieve the data with a computer program on behalf of a user (through a suitable user interface)? However, another important consideration is to facilitate sharing of data between laboratories. For clinical practice, too, sharing of medical record data between different health care providers for an individual patient is important. The goal of a data interchange standard is to decouple the details of representing data in any particular computer program from the details of the storage format of a data source. An interchange standard enables data to be shared between different laboratories, even if they choose to use different local storage schemes. These are sufficiently difficult problems to occupy a significant amount of research effort in biomedical informatics. In the following sections, examples will show how to structure and use biomedical data, including symbols for atoms and molecules; sequences representing DNA, RNA, and proteins; and structures representing medical laboratory data and clinical data from electronic medical record systems. An example problem, representing patient data, serializing and storing it in files, and reconstructing the data from a file, shows how to represent metadata in various ways, starting with tags and values, then using declarative structures in program code (classes, in the usual object-oriented style), and using program code that itself is accessible from within a program. We then introduce the idea of tabular data and the relational database model. In all of these approaches, maintaining data quality is important. The chapter concludes with some observations about the relations among data, information, and knowledge.

6

PART | I Foundations of Biomedical Informatics

1.1 THE NATURE AND REPRESENTATION OF BIOMEDICAL DATA The first things to consider are the various forms of biomedical data, and how such data can be represented in a computer and manipulated by a computer program. Looking at a typical biology textbook, you will find a rich collection of photographs (including many taken using a microscope), diagrams, drawings, chemical formulas, and lots of description. Many medical textbooks have the same characteristics. The textual descriptions are about the attributes of biological entities such as cells, organs, tissues, fluids, chemical compounds found in all those and about the relations between these entities and their properties. Some of the properties of biological objects are numerical, for example, the concentration of certain chemicals in blood, the size of a tumor, and the pH (degree of acidity) in a cell, tissue, organ, or body fluid. Other properties are qualities that can only be named but not quantified. Examples of such qualities are the type of a cell or tissue, the protein(s) produced by gene transcription, the presence or absence of an organ in an organism, and the parts of an organ. These all have names, not numerical values. Examples of cell types include squamous cells, epithelial cells, muscle cells, and blood cells. These are further divided, as in blood cells, there are red cells and white cells, with several varieties of white cells. These categorical attributes are also related back to numerical values. Since we can count cells, it is possible to report for an individual the concentrations of different types of blood cells in the blood. This is done in a clinical laboratory, and the results are reported to the physician as an aid to decisionmaking for his/her patient. The type of a cell is represented by a name, not a number, since it does not mean anything to do arithmetic with cell types, that is, we would not add one cell type to another to get some third cell type. One of the most important classes of constituents of living organisms is protein. Many hundreds of thousands of proteins found in living organisms have been named, catalogued, and their properties recorded. These properties include the function(s) of the protein, the gene that codes for it, and diseases that may relate to its absence or mutation. Proteins have many different roles in cells and tissues. They can serve as enzymes to facilitate biochemical reactions, such as metabolism of glucose. They can regulate other processes by serving as signals. Proteins also are components of cell and tissue structure. Proteins are large molecules made up of long sequences of small units. In proteins, the small units are from a set of 20 different molecules called amino acids. Figure 1.1 shows the general structure of an amino acid and a specific example, Alanine. These molecules are called amino acids because of the presence of the NH2 group, an amine group, and the presence of a COOH group, which typically gives an organic molecule properties associated with acids. The COOH group is easily ionized, losing a proton (hydrogen ion). Such proton “donors” are acidic in behavior. For more background or a review, see any general chemistry textbook, for example [356]. Each amino acid can be symbolized by a name, which may be its full name, an abbreviated name, or a single letter, and so the amino acid sequence of the protein can be represented by a sequence of names or letters. This sequence is called its primary structure. It is not a sequence of numbers. One possible way to encode this information would be to assign a number to each of the 20 different amino acids, and then the protein would be a number sequence. However, it is meaningless to do arithmetic operations with these numbers. They are just names. It is meaningful to compare two sequences to see if they are similar, that is, they have the same or almost the same amino acids in the same order. This is a comparision operation between lists of named things or objects, not a comparision between numbers. Naturally occurring proteins are found in cells usually in a complex folded configuration. Sections of the sequence of amino acids can form helical structures, where successive amino acids form hydrogen bonds with each other. Such a structure is called an α helix. Another common structure is a β sheet in

R

C

FIGURE 1.1 The general structure of an amino acid is shown on the left and the structure for alanine on the right, with R replaced by a methyl group, CH3 .

NH2

NH2 H

COOH

CH3

C

H

COOH

Chapter | 1 Biomedical Data

7

FIGURE 1.2 A model of an enzyme, PanB, from M. tuberculosis (courtesy of National Institute of General Medical Sciences (NIGMS), Protein Structure Initiative). See Color Plate.

which the polypeptide forms a series of linear segments, folded back and forth in a weave-like pattern, again, held together by hydrogen bonds. Connections between such structures are called turns. These are all examples of secondary structure. Sets of such structures can form more complex aggregations called domains. These higher level structures, including structures of entire single protein units, are called tertiary structures. Finally, protein molecules can often be associated in pairs (dimers) or larger units, quarternary structures, that can then aggregate to form crystal structures. Figure 1.2 shows a diagrammatic illustration of protein secondary and tertiary structure. Large digital data repositories are available containing information about proteins, such as the UniProt / Swiss-Prot Knowledge Base, a project of the Swiss Institute for Bioinformatics. The UniProt data are downloadable in a variety of formats from the ExPASy web site (http://www.expasy.ch), maintained by the Swiss Institute for Bioinformatics. Figure 1.3 shows an abbreviated excerpt from a Swiss-Prot entry for the precursor protein from which human insulin is formed. In Chapter 5, we show how to extract sequence information from one such formatted file type and how to compute some useful things from the sequence data. Here, we are only considering what kinds of data may be found in the files. For a complete explanation of the individual field items, the reader should consult the documentation available at the ExPASy web site. Here, we describe just a few of these. The DR records are crossreferences, in this case to the Gene Ontology (GO). It is useful to be able to have a computer program look up these cross-references so that information can then be used in combination with the data shown here. The FT records are feature descriptions. Some of the features shown are the places in the amino acid sequence where different types of structures occur, such as α-helix structures, β strands, and turns. In this record, the locations of disulfide linkages are also reported. The names following the FT tags are the feature types. The numbers are the sequence start and end points for each feature. This particular entry describes a polypeptide that is a precursor for the insulin protein. The molecule folds up, forming the disulfide bonds indicated, and the section marked PROPEP in the FT records is spliced out, leaving the two PEPTIDE sections, linked by the disulfide bridges. Finally, the last part shown, the SQ section, contains the actual sequence of amino acids, one letter for each. Many proteins function as enzymes, chemical compounds that facilitate chemical reactions while not actually being consumed, that is, they are not reactants or substrates (the inputs to the reaction), and they are not products (the results of the reaction). However, many biologically important reactions do not proceed without the presence of the corresponding enzymes. So, an important piece of information about a protein is its function. Is it an enzyme, and what type of enzyme is it? If it is an enzyme, what

8

PART | I Foundations of Biomedical Informatics

ID AC DE GN OS DR DR DR DR DR DR FT FT FT FT FT FT FT FT FT FT FT FT FT FT FT FT FT FT FT FT FT FT SQ

INS_HUMAN Reviewed; 110 AA. P01308; Q5EEX2; Insulin precursor [Contains: Insulin B chain; Insulin A chain]. Name=INS; Homo sapiens (Human). GO; GO:0006953; P:acute-phase response; NAS:UniProtKB. GO; GO:0046631; P:alpha-beta T cell activation; IDA:UniProtKB. GO; GO:0008219; P:cell death; NAS:UniProtKB. GO; GO:0007267; P:cell-cell signaling; IC:UniProtKB. GO; GO:0006006; P:glucose metabolic process; TAS:ProtInc. GO; GO:0015758; P:glucose transport; IDA:UniProtKB. SIGNAL 1 24 PEPTIDE 25 54 Insulin B chain. /FTId=PRO_0000015819. PROPEP 57 87 C peptide. /FTId=PRO_0000015820. PEPTIDE 90 110 Insulin A chain. /FTId=PRO_0000015821. DISULFID 31 96 Interchain (between B and A chains). DISULFID 43 109 Interchain (between B and A chains). DISULFID 95 100 VARIANT 34 34 H -> D (in familial hyperproinsulinemia; Providence). /FTId=VAR_003971. HELIX 35 43 HELIX 44 46 STRAND 48 50 STRAND 56 58 STRAND 74 76 HELIX 79 81 TURN 84 86 HELIX 91 95 HELIX 105 108 SEQUENCE 110 AA; 11981 MW; C2C3B23B85E520E5 CRC64; MALWMRLLPL LALLALWGPD PAAAFVNQHL CGSHLVEALY LVCGERGFFY TPKTRREAED LQVGQVELGG GPGAGSLQPL ALEGSLQKRG IVEQCCTSIC SLYQLENYCN

FIGURE 1.3 An excerpt of an entry from the Swiss-Prot database of proteins.

reaction(s) does it facilitate? Figure 1.4 shows an example, a small excerpt from the Enzyme database, another resource provided by the Swiss Institute for Bioinformatics at the ExPASy web site. The line beginning with ID is the Enzyme Commission number, unique to each entry. The DE line is the official name, and the AN lines are alternate names or synonyms. This enzyme catalyzes the reaction that removes a carboxyl group from the malate molecule, leaving a pyruvate molecule, and in the process also converting an NAD+ molecule to NADH. The NAD+ and NADH molecules are coenzymes, molecules that participate in the reaction, change state somewhat, but are later reused in other reactions, and generally not consumed overall in the process.2 The reaction catalyzed by malate dehydrogenase is

2. These molecules are all variants in a family. The abbreviation NAD stands for Nicotinamide adenine dinucleotide. This molecule and its derivatives serve as hydrogen transporters in many different metabolic reactions (oxidation and reduction). More about NAD and its biochemical functions can be found in standard biochemistry [233] and molecular biology [5] texts.

Chapter | 1 Biomedical Data

ID DE AN AN CA CC PR DR

9

1.1.1.39 Malate dehydrogenase (decarboxylating). Malic enzyme. Pyruvic-malic carboxylase. (S)-malate + NAD(+) = pyruvate + CO(2) + NADH. -!- Does not decarboxylates added oxaloacetate. PROSITE; PDOC00294; P37224, MAOM_AMAHP; P37221, MAOM_SOLTU; P37225, MAON_SOLTU;

FIGURE 1.4 An excerpt of an entry from the Enzyme database.

described in a kind of stylized symbolic form on the line beginning with CA. The CC line is a comment, not meant for use by a computer program. The PR line is a cross-reference to the Prosite database, which has other information about proteins, and the DR line is a set of cross-references to entries in the Swiss-Prot database where the sequences corresponding to various versions of this protein may be found. So, it would be useful to be able to represent molecules and reactions, for example, to determine if a cell is able to process some starting substrates and produce from them the necessary products. Similarly, having the enzymes associated with the reactions, one can look up what processes would be blocked if an enzyme was missing, for example, because of a genetic defect or mutation. We will show how the data above can be put in a form so that we can do just such computations. Moving from the cellular and biochemical domains to the level of gross anatomy, bodies and organs and tissues also have a lot of data and knowledge associated with them. Organs, for example, also have names, lists of their constituent parts, location within the body of the organism, and possibly other information as well. This information is also symbolic and consists of items that need to be grouped together in lists or more complex structures. Figure 1.5 shows some information about the human heart, taken from the University of Washington Foundational Model of Anatomy (FMA). The FMA is described in detail in Chapter 6. Some of this information can be used for spatial reasoning about anatomy, as applicable to surgical procedures, consequences of bodily injury, etc. Information about the connectivity of the lymphatic system and lymphatic drainage of various organs and anatomic locations makes it possible to construct computational models for spread of tumor cells. This in turn helps to determine the target for radiation therapy for cancer, resulting in improved accuracy of treatment. This is described in detail in Chapter 9. Electronic medical records are rapidly becoming the standard of practice for managing clinical data, in medical offices and hospitals, small and large. Some of the information stored in these systems is numeric, such as the results of many laboratory tests. Examples include counts of the number of various types of blood cells (red cells, white cells and their subtypes), concentration of drugs, sugars, important proteins, etc. Some nonnumerical information is also important in these laboratory tests, for example, the units used for the tests as well as tests for the presence of bacteria and the identities of the bacteria (blood cultures and bacterial cultures from other parts of the body). Electronic medical record systems also include enormous amounts of textual information, such as a physician’s dictation of findings about the patient (history and physical examination). Gene and protein sequence data use a small “alphabet” of symbols, four for elements of gene sequences and 20 for the amino acids that make up proteins. This encoding problem is simple by comparision with the problem of representing clinical laboratory test data. Laboratory data are the results of tests that the clinical laboratory performs when a sample of a patient’s blood is drawn from a vein and put in a tube or tubes to be sent to the laboratory. Some examples of blood tests are red and white blood cell counts, hemoglobin, creatinine level, glucose level, etc. These tests are usually grouped into panels that can be ordered as a unit. Table 1.1 shows some values from a complete blood count for a patient, along with the standard (normal) range for each test. Note that the units in which the values are reported are different for the different tests. White blood cells (WBC) and red blood cells

10

PART | I Foundations of Biomedical Informatics

NAME: Heart PARTS: Right atrium Right ventricle Left ventricle Left atrium Wall of heart Interatrial septum Interventricular septum Atrioventricular septum Fibrous skeleton of heart Tricuspid valve Mitral valve Pulmonary valve Aortic valve ... PART OF: Cardiovascular system ... ARTERIAL SUPPLY: Right coronary artery Left coronary artery VENOUS DRAINAGE: Systemic venous tree organ NERVE SUPPLY: Deep cardiac nerve plexus Right coronary nerve plexus Left coronary nerve plexus Atrial nerve plexus Superficial cardiac nerve plexus LYMPHATIC DRAINAGE: Right cardiac tributary of brachiocephalic lymphatic chain Brachiocephalic lymphatic chain Left cardiac tributary of tracheobronchial lymphatic chain ATTACHES TO: Pericardial sac ... FIGURE 1.5 An excerpt from the University of Washington Foundational Model of Anatomy (FMA).

(RBC) are both counted, but there are so many more RBC that the number is reported in millions of cells per microliter rather than thousands as for WBC. Table 1.2 is another example of a panel and lists the names, values, and standard ranges for some of the tests in a comprehensive metabolic panel ordered on a patient. You can see by comparing the values with the ranges that all the values are within the standard ranges, except for the creatinine level. This is not cause for alarm in this case since the patient has only one kidney, and a slightly elevated creatinine level is not unusual for this patient. The creatinine level is an indicator of how well the kidneys are filtering the blood and getting protein breakdown products out of the body. Many other kinds of samples of body tissues also can be used to do tests, including urine and bits of material obtained by swabbing your throat, ear, nose, eye, etc. There are thousands of types of laboratory tests, each requiring its own identifier or code as well as its own conventions for representing

Chapter | 1 Biomedical Data

11

TABLE 1.1 Complete Blood Count Panel Component

Result

Standard range

WBC

6.14

4.3–10.0 thousand/μL

RBC

4.80

4.40–5.60 million/μL

Hemoglobin

13.8

13.0–18.0 g/dL

Hematocrit

40

38–50%

Platelet count

229

150–400 thousand/μL

…

…

…

TABLE 1.2 Comprehensive Metabolic Panel Component

Result

Standard range

Sodium

139

136–145 mEq/L

Potassium

4.1

3.7–5.2 mEq/L

Chloride

107

98–108 mEq/L

Glucose

94

62–125 mg/dL

Urea nitrogen

21

8–21 mg/dL

Creatinine

1.5

0.3–1.2 mg/dL

Protein (total)

6.8

6.0–8.2 g/dL

Bilirubin (total)

0.7

0.2–1.3 mg/dL

…

…

…

the test result itself. Tests can include determining what chemical substances are present in the sample and inoculating agar gel containers (called “cultures”) to determine if bacteria are present in the sample. Electronic medical record (EMR) systems are complex database systems that attempt to integrate and provide ease of access to all the data needed for care providers and patients in the medical setting. They include facilities for acquiring data from instruments, for data entry by practitioners in the clinic and on the wards, and generation of reports for use by managers and others. We have already touched on the complexity of representing such a huge and diverse data set in discussing laboratory data. Information such as pathology and radiology reports often take the form of dictated text. Although highly stylized, such reports are difficult to represent in as structured a form as laboratory tests. The core challenges in designing EMR systems are to come up with logical and consistent ways to organize the data on all the patients, procedures, facilities, providers, etc., ways to easily retrieve the particular subsets of data needed at different places and times in the health care setting, and ways to organize and present the information so providers and patients can easily use it. However, there is now growing interest in being able to compute some useful results from the information, not just retrieve it for human examination. For example, it may be possible to predict the onset of adverse events by applying logical reasoning procedures to data on a patient, or, alternately, to identify the onset of such events early on. If such things can be predicted or at least flagged early, then possibly the adverse events can be prevented or successfully treated by timely intervention before they happen. Some of the data and procedures will be numeric in nature, but others will be reasoning steps applied to symbolic information.

12

PART | I Foundations of Biomedical Informatics

One of the most difficult problems is to match up the various activities around health care practice with the proper codes for billing for services provided. The complex rules around billing procedures depend on accurately categorizing the diagnoses as well as the procedures. As a result, considerable research has been conducted to devise methods of automatically extracting structured data from free text reports, using natural language processing (NLP) techniques. Many other places exist in the EMR for such “free text” besides pathology and radiology. The encoding of patient data seems to be a good match to an “object-oriented” style of data modeling. A simple example of this is developed in Section 1.2.2. However, the more common approach is to create a tabular design for storing and accessing medical data, based on the relational database model. An introduction to databases in general and the relational model in particular is in Section 1.4. In some cases, the flexibility needed to store data with highly variable complex structure is gained from the Entity–Attribute–Value (EAV) model, described briefly in Section 1.4.2. Electonic medical record system design is evolving rapidly, and huge investments are being made in deploying commercial systems as well as in studying the effectiveness of different design approaches. Expenditures for EMR installations at medium-sized institutions can run in the range of 100 to 200 million dollars (2008). Along with the rapid deployment of institutional systems, there is a growing interest in “personal health records.” Although it is an unsettled legal question as to who actually owns the medical information about a patient, there are many initiatives to provide patients with ways to store, access and carry with them their own complete health record. At the National Library of Medicine’s (NLM) annual research training program directors meeting in July 2005, Donald Lindberg (Director of the NLM) commented on the future directions for institutional and personal health records, and what they should contain. He observed that the electronic health record should be a lifelong record, including some things that are not now part of existing systems. These are ● ● ● ●

genome analysis, family relationships (pedigree), ethical conventions, and the patient’s own observations.

It is also important to have EMR systems that can easily support anonymization of data for research use. The opportunities that widespread adoption of EMR systems present for discovery are enormous. In the domain of public health, too, we often have to deal with categorical or nonnumeric information. We collect information about disease prevalence and assign numbers to cities, states, and other geographic entities. These entities have names, and the data come from governmental or health care provider agencies, which also have names but are not themselves numerical values. For example, one might ask for a list of all the cities in Washington state that have seen an abnormal incidence of kidney cancer in order to test a hypothesis about carcinogens in the environment. The incidence rates are numbers, but the list of cities is a list of names of objects or entities. The basic science underlying much of public health practice is epidemiology, the study of the spread of diseases and environmental toxic substances throughout populations and geographic areas. In addition, public health studies the organizational aspects of health care practice and how it affects the health of populations. Many kinds of data are used in public health research and practice. Examples include ●

● ● ● ●

time series of various sorts, used for things like syndromic surveillance, outbreak detection, longterm trends in morbidity and mortality, etc., vital statistics, that is, birth and death records and other related data, immunization records, reportable disease records such as tumor registries and STD registries, risk factor data.

Chapter | 1 Biomedical Data

13

An additional example of data that are significant for public health is the FDA’s Adverse Event Reporting System (AERS). This system accumulates data on adverse events related to drug interactions. The subject of drug interactions from a strictly pharmacologic point of view is developed in Chapter 7. Like medical and biological data, these are diverse types, coming from many disparate sources. There are many unsolved problems around defining and using appropriate vocabulary, syntax, and semantics. The social and political issues around the organization of public health practice also strongly affect the success rate of informatics projects.

1.1.1 What Can Be Represented in a Computer? In order for computer programs to deal with biomedical data, the data must be encoded according to some plan so that the binary numbers in the computer’s memory represent numeric data or represent text, character by character, or possibly more abstract kinds of data. Many encoding schemes have been used for biomedical data. We describe a few here to give a flavor for how this might work. We also show how small programs can express or embody the encodings and in some cases convert from one encoding scheme to another. Examples include biomolecular sequence data (DNA and proteins), laboratory data from tests done on blood samples and other substances obtained from patients in a clinic or hospital, and medical image data. In addition, everyone needs methods for searching and sorting through the vast collections of bibliographic reference data now available such as the MEDLINE database of journal articles and other informational items. The entries in such bibliographic databases are definitely not numeric but are indexed by keywords, and the search methods used depend on being able to manipulate lists and complex structures. Chapter 4 illustrates how bibliographic information can be structured, retrieved, and organized. The digital computer has only one way to represent information, that is, in terms of collections of bits. A bit is a single unit of information, represented by the state of an electrical circuit component in the computer. This circuit can be either on or off, but no other value is possible. We talk about this in digital computer terms by assigning the “off” value the number 0 and the “on” value the number 1. With combinations of multiple bits, we can represent as many different things as we have circuits for. The collection of circuits is called the memory of the computer. It is usually organized into bytes, each consisting of 8 bits. With 8 bits, we can represent 256 different things. Each bit combination would stand for something, for example, we could decide that the combination 01101110 would stand for the category “squamous cell” and 01101111 would be “epithelial cell.” Clearly, 256 categories is not nearly enough to deal with what we know about biology, medicine, and public health. However, modern computer memories have many billions of bits, so we really can use this idea to encode lots of things. However, writing instructions for creating lists of such codes and sorting and comparing them are not very efficient, and so we instead have many layers of electronics and computer programs to create and manipulate these encodings in a more reasonable and abstract way. Since we are already familiar with natural language text, we use a method adopted centuries ago by mathematicians. We use letters and words as symbols that name the various biological entities. These symbols (whether their names are single letters or long words) can be manipulated by computer programs, in just the abstract ways we will need. So, we assign names (symbols) to each of the entities and their relationships, and we will see how to organize these so that we can compute interesting and useful things. We will start with proteins and then extend the ideas to the other biological molecules, especially DNA. Following subsections will then briefly describe some other kinds of biomedical data. We also need some way to represent sequences. We do this by writing the names of the amino acids in order, starting with a left parenthesis, separating each name by some space (one space character is sufficient, but any number is OK, including continuing on the next text line), and finally marking the

14

PART | I Foundations of Biomedical Informatics

end of the sequence with a right parenthesis. This structure is called a list. So, a sequence of amino acids that make up a (very short) protein might look like this:3 (tryptophan lysine aspartate glutamine aspartate serine) The parentheses conveniently mark the beginning and end of the protein sequence and spaces suffice to cleanly separate the names. Provided that we do not use spaces or other non-printing characters in the names, no other complex punctuation or syntax is needed. A biologist familiar with amino acids (only 20 different kinds appear in proteins) might prefer shorter names to be able to encode much bigger proteins in a more compact way. So, each amino acid also has a short name only three letters long, and a single letter code, both standardized by the International Union of Pure and Applied Chemistry (IUPAC).4 Table 1.5 lists the full names, short names, and single letter abbreviations of the standard amino acids. Using the short names, the above sequence could then also be written as (trp lys asp glu asp ser) or using the single letter codes as symbols for each (W K D E D S). Going further, the sequence of amino acids is not the only thing we know about a protein. Many proteins have known functions, such as serving as components of cellular structures, serving as enzymes for biochemical reactions, and as regulators of activity of genes in cells. These functions can also be given symbolic names, and we can then create a data structure, a collection of information about a protein, again just using the symbols and parentheses to group the symbols into lists. A list could certainly contain other lists in addition to symbols, so we can make up nested structures, which is a very useful way to keep things organized. Similarly, we could combine such symbolic information with numeric information by using the normal representation of numbers. Here is an example of how to encode the Enzyme database excerpt shown in Figure 1.4 in terms of symbols, strings, and lists: (enzyme (id "1.1.1.39") (name "Malate dehydrogenase (decarboxylating)") (sym-name malic-enzyme) (reaction (reactants s-malate nad+) (products pyruvate co2 nadh)) (prosite-ref PDOC00294) (swissprot (P37224 MAOM_AMAHP) (P37221 MAOM_SOLTU) (P37225 MAON_SOLTU))) Here we have used standard Latin text characters, chosen symbol names that would be somewhat familiar to practitioners, and used digits and decimal points to represent numbers. The fragments of text enclosed in double-quote (") characters are strings. A string is just text, to be read by people, printed, etc., while symbols, the words that are not enclosed in quotes, are like mathematical variables, names that a computer program can use and manipulate directly. Can a computer program do anything with this? Yes, certainly. We need to be able to represent the Latin letters and digits as binary codes. Such a representation is called character encoding, and the collection of characters that are assigned codes is called the character set. In the most commonly used character set, known as ASCII, each code is represented in the computer memory as a single byte. The first 32 codes are non-printable and are considered “control” characters. This dates from the use of these codes with teletype devices, where the teletype message needed special codes indicating start of message, end of message, and “carriage control” to indicate a carriage return, 3. In this book, to identify text that constitutes a computer program or part of a computer program or data, we use a different font than that of the main text. 4. IUPAC is an international scientific organization for advancement of the chemical sciences and their application to benefit humankind. For more information on IUPAC, see their web site, http://www.iupac.org/.

Chapter | 1 Biomedical Data

15

a line feed (advance the printer paper by one line), a form feed (advance the paper by a whole page length), and the like. These control characters are still in use and recognized by computer programs to have special interpretations, not exactly the same as with the teletype and (unfortunately) not even the same for every program. For example, “control-C” is often interpreted to mean “interrupt the currently running program,” but it also can be used to mean “end of transmission.” The printing characters begin with the value (decimal) 32 for the space character. Both uppercase and lowercase Latin letters are included. Table 1.3 shows a sampling of some of the codes. With this encoding, the characters of the text can be read by a program, usually from a disk file but sometimes from a keyboard or a network connection to another computer. Now an important step needs to take place. The symbols and lists represented by the characters need to have some representation in the computer program memory. Thus, the character sequences (text) need to be translated into a representation in the computer where each symbol has its own encoding, not as a sequence of the characters that make up its name. Similarly, it is necessary to have a representation of a list so that the list contents can be manipulated directly. This process of translating text into encoding that a computer program can manipulate is sometimes called parsing. For now, we will assume that we have an interactive computing environment, a computer program that can read such text, do the translation so that we can apply operations to the data and get results. Computer programs in the form we call “source code” are plain text, using character sets such as the printable characters from the ASCII character set. Character attributes such as font style, type size, or display attributes such as boldface are irrelevant. The meaning of the program is entirely in the plain text. Computer programmers typically use text creation and editing tools that directly display and TABLE 1.3 Table of ASCII Codes (only a sample shown) Decimal

Hexadecimal

Character

0

0

NUL (null)

1

1

SOH (control-A)

2

2

STX (control-B)

3

3

ETX (control-C)

...

...

...

32

20

(space)

33

21

!

34

22

"

...

...

...

48

30

0

49

31

1

...

...

...

65

41

A

66

42

B

...

...

...

120

78

x

121

79

y

122

7A

z

etc.

16

PART | I Foundations of Biomedical Informatics

manipulate plain text. These programs are called text editors. Two popular ones available for a wide range of operating systems (including Linux) are called vi and emacs. The emacs text editor also runs on just about any kind of computer or operating system available today, including Microsoft Windows PC and Apple Macintosh systems. Program source files are read by computer programs called interpreters or compilers, which translate the text into computer machine instructions that can be executed by the machine itself. Word processing document files contain a lot of other proprietary data that carry text formatting information and other information that interferes with the processing of the program text by the interpreter or compiler. So, the text of a computer program is really a set of symbols whose meaning can be understood by a suitably configured computer system. Humans can of course read such text also since we write it. Good text editors such as emacs provide some aids for specific programming languages, like Lisp, to make the text easy to understand. Examples are automatically coloring (in the text editor display window) some of the words that the editor program recognizes as special to the programming language and doing some display formatting specific to the programming language (automatically indenting some lines). Now that we have a way to represent each symbol and the various lists in a way that a computer program could operate on these things, what operations would we want to do? For the protein amino acid sequences, one thing we might do is to have a computer program count the number of amino acids (for larger proteins you would not want to do this by hand). Another important and more complex procedure is to count how many amino acids of each kind are in a particular protein sequence. Yet another problem is to extract particular items from the complex structures above. For simplicity, we will start with just the amino acid sequence. In order to describe and actually perform such computations, we need a computing environment in which we can create files containing the text representation of the above. We also need an interpreter or compiler program that can convert the text representation to an internal representation that the computer can use. We will start by describing an interpretive environment that can process symbols and lists like the ones we describe here. In this environment, you can use many built-in operations on such data and also create your own complex operations that you can then use as if they were built-in. The programming language best suited for the data and computations we will be doing is called Lisp, an abbreviation for “list processing” since its focus is exactly on representing and processing things represented as symbols and lists. Lisp is the second oldest computer programming language in use today.5 It was invented by John McCarthy in 1958 while he was on the faculty at Massachusetts Institute of Technology (MIT). McCarthy’s landmark publication [207] is well worth reading, not only for historical reasons but also for the insight it provides into the meaning of functions and computation. A session with a computer display, keyboard, and a Lisp interpreter will consist of typing expressions at the keyboard in response to a prompt that the interpreter displays on the screen, in a window, the interpreter window or command window. The interpreter translates the typed text into an internal representation of the expression, evaluates the expression, and prints out the result. Figure 1.6 shows a command window with a prompt, a typed expression and the resulting response, followed by a reprompt, another typed expression, the response, and a third prompt. An expression can be a symbol, a list, or some other type of data represented in text form. In addition to symbols and lists, numbers are included in the language, and operations can be performed on numbers. We will start with arithmetic since it is simple and familiar. Suppose we want to add together a bunch of numbers. After the interpreter prompt, we type an expression (a list) beginning with the name of an operation. The rest of the list contains the operands or inputs to the operation. The operators are usually functions in the mathematical sense that they are defined for some domain of valid inputs and produce results in some set called the range. Following is a more detailed explanation of

5. The oldest is FORTRAN, invented a few years earlier by John Backus at IBM, and first implemented in 1957. The focus of FORTRAN, by contrast, was on expressing numerical formulas and algorithms to do high speed arithmetic with large data sets.

Chapter | 1 Biomedical Data

17

> (+ 276 635 1138) 2049 > (/ (+ 182 178 179 183 182 181 181) 7) 1266/7 >

FIGURE 1.6 A command window running an interactive Lisp session.

the examples in Figure 1.6 (the first set of numbers are the number of calories in each of three meals eaten recently, perhaps by the author). The > is the interpreter’s prompt; the user types the expression.6 Then the interpreter looks up the name + to see if it is defined as an operator. It is, so the values of the rest of the list elements are provided to the + operator, it returns the result 2049, and prints it on the display, then redisplays the prompt, and waits for the next expression. This cycle of interaction with the interpreter program is called the read-eval-print loop. > (+ 276 635 1138) 2049 Lisp uses prefix notation with mathematical functions, just as with any other operators, that is, for any expression the operator is first and the operands follow. This contrasts with most other popular programming languages (FORTRAN, C, C++, Java, BASIC, perl, etc.), which use infix notation, more like mathematical expressions. In infix notation, operators appear between operands and thus need to be repeated to have expressions in which there are multiple operands even though the operator is the same. For example, to add up a bunch of numbers, the mathematical expression might be a + b + c + . . ., while in Lisp, it is (+ a b c ...), that is, operator first, then the inputs.7 Before the operation is performed, each of the inputs is also evaluated. A number evaluates to itself, that is, numbers are constants. We could, however, put yet another expression as one of the inputs. This evaluation of inputs makes nested expressions possible. Again, we use numbers to keep the examples simple. Suppose we want to compute the average weight of a person over some number of days. In this case, we want to divide the sum of the daily weights by the number of days. The expression we type has three items in the list. The first is the / symbol, the second is a list (an expression beginning with the + symbol and then some numbers), and the third is the number 7. > (/ (+ 182 178 179 183 182 181 181) 7) 1266/7 The inner expression was evaluated to give 1266, and then the result of the division was displayed as a ratio. Numbers in Lisp can be integers, ratios, so-called floating-point numbers and even complex 6. Many Lisp interpreter systems are available, both free and commercial, and each has their own style of prompt. For simplicity we just use >, following the same convention as Graham [94] and Norvig [238]. See Appendix A for information on how to obtain a working Lisp system. 7. This is sometimes also called Polish notation. The opposite, where the inputs come first and the operator comes last, is called reverse Polish notation, or RPN. This style or arrangement is used by Hewlett-Packard hand-held calculators. Infix is used by Texas Instruments calculators. Each has their proponents.

18

PART | I Foundations of Biomedical Informatics

numbers. The arithmetic operators do some amount of type interconversion automatically so that if we provide weights in decimal form, the result will be a decimal or floating point number, instead of a ratio. > (/ (+ 182.0 178 179 183 182 181 181) 7) 180.85715 Note that the type conversion happened for all the numbers even though only one was in decimal form. Now you might wonder, what about evaluating the numbers themselves? The interpreter does this. A number evaluates to itself, that is, the value is exactly the number you typed, represented in some appropriate way inside the computer system. So, the rule of evaluating inputs is uniform, with only a few exceptions. Exceptions to the input evaluation rule are called special forms or macros, and we will take this complexity up a little later in this section. Operators that are special forms or macros often also have the property that they cause side-effects, that is, they do not simply return a result like a function does but also cause some change in the computational environment. Symbols can also be used as inputs to expressions, that is, in place of the numbers above, if the symbols have values assigned to them. In addition to being names of things, symbols can be used as variables in the same way as variables in mathematics. Before we show how to do this, we will first consider just using the symbols by themselves, as names of things, since some of our biomedical data are not numbers, but symbols and lists. In this case, it would not make sense to do arithmetic on a list of names. What operations do we perform on them? For a sequence of amino acids making up a protein, we could ask, “what is the first amino acid in the sequence?” and indeed there is a built-in function, called first, that takes a single input, a list, and returns the first thing in the list. However, writing > (first (trp lys asp glu asp ser)) will cause an error. Following the evaluation rule, the interpreter will try to evaluate the expression (trp lys asp glu asp ser). It will look up the name trp to see if there is an operation by that name. Of course there is not. That is the name of one of the amino acids, but it is not the name of an operation. What we want the interpreter to do here is to take the list literally, not treat it as an expression. To do this, we need a special form, named quote. Any expression beginning with the symbol quote will not be evaluated but used literally as data. So, we need to write > (first (quote (trp lys asp glu asp ser))) TRP This works as we intended.8 The result is the symbol trp. This same special form, quote, is needed when we operate with symbols as well as with lists. Suppose we wish to construct a list containing the symbols for the amino acids. The list operator will take any number of inputs and make them elements of a list. But, > (list trp lys asp glu asp ser) would not work. Each of the symbols will be evaluated by the interpreter, that is, a symbol can be used like a variable in mathematics and be assigned a value. To evaluate the symbol, the interpreter just looks up its value, which is recorded along with the symbol’s name and other information about it. If no value has been previously assigned, an error occurs. Here, we do not want values of symbols, we just want the symbols themselves, so we use quote.

8. You might wonder about whether there is a distinction between uppercase and lowercase letters. There is, but in most Lisp environments, as the Lisp interpreter reads expressions, it converts any lowercase letters appearing in symbol names to uppercase. So, while the convention is that we write our programs using mostly lowercase, it all gets converted as it is read in.

Chapter | 1 Biomedical Data

19

> (list (quote trp) (quote lys) (quote asp) (quote glu) (quote asp) (quote ser)) (TRP LYS ASP GLU ASP SER) The quote operator is the first example of several such operators that do not follow the evaluation rule. There are only a few other important ones. As they are needed, they will be introduced. Some of these, like quote, are built-in primitives and are called special forms. Others are implemented as macros. A macro first performs some operations on its inputs without evaluating them and constructs an expression to be evaluated. The resulting expression is then evaluated. Ordinary expressions are just small programs that are run by the interpreter, while a macro is in effect an operator that first writes a small program and then runs it. We will also introduce macros as they are needed and even show how writing your own macros will enable you to describe and process biomedical data and knowledge at a very high level. This use of quote can get verbose as we see here. The quote special form is so often and widely needed, it is part of the Lisp standard to allow an abbreviated version of such expressions. Instead of an expression beginning with the quote operator, it is allowed to simply put a single quote ’ character in front of a symbol or list. So, the above expressions would be written as follows: > (first ’(trp lys asp glu asp ser)) TRP > (list ’trp ’lys ’asp ’glu ’asp ’ser) (TRP LYS ASP GLU ASP SER) It is almost exactly parallel to the natural language idea of quoting. When we refer to a person by name, we use the name, and it “evaluates” to the person himself, for example, we would write that the author of this book is Ira Kalet, not “Ira Kalet.” However, when we want to refer to the name itself, we quote it, for example, we would write that the author’s name is “Ira Kalet,” not Ira Kalet. The quoted form is the name, while the unquoted form refers to the actual person.9 In English typography, most often the double quote convention is followed, as here, but in Lisp, the abbreviation for the quote operator is the single quote character. In Lisp, the " or double quote character is used for a different purpose, to delimit strings or literal text data. So, "enzyme inhibitor" is a sequence of characters making up text data, not a symbol or list of symbols. We have been writing symbols by name using ordinary text characters. Aren’t they just strings? A string is a sequence of characters, and the characters are in turn available from some standard character set, usually the common Latin characters, but some Lisp systems also support more extended character sets, even Unicode. A single character is a different kind of datum than a one-character string, just as a symbol is different from a list containing one symbol. The difference between symbols and strings is that a symbol is a single indivisible unit that may have properties associated with it, such as a value, while a string cannot be assigned a value. Strings are constant values that evaluate to themselves, just as numbers do. It is also the difference between being easily able to do computation directly with meaningful concepts on the one hand and having to do complicated analysis of letter sequences to do even simple things with the meanings of the text. As an example, if the amino acid sequence was treated as text instead of a list of symbols, the operation of finding the first amino acid would be a matter of analyzing character after character until you found a blank space character, then assembling the characters up to that point into a separate string. The symbol and list representation eliminates that by providing a higher level language.

9. A much more entertaining version of this contrast can be found in the dialog between Alice and the White Knight, in Lewis Carroll’s famous work, Through the Looking Glass. A formal treatment can be found in [225].

20

PART | I Foundations of Biomedical Informatics

It is important to note that the operators *, +, etc., are also symbols, just one character long. They have predefined function definitions, just like the first function and others we have mentioned. There is no special syntax for arithmetic operators. In addition to the first function, there are also second, third, etc., up to tenth. However, if you need to look up a list element at an arbitrary position in the list, a more general function, elt, is available.10 This function takes two inputs because you need to specify which position you are looking for, as well as the list in which to look. Note that in Lisp as in many computer languages, indexing of sequential data-like lists starts at 0, that is, (first seq) is equivalent to (elt seq 0), and the following expression could also be written (fourth ’(trp lys ...)). > (elt ’(trp lys asp glu asp ser) 3) GLU A very useful function complements the first function, by returning the remainder, or rest, of the list, that is, the list containing everything but the first element. This function is called rest, as you might expect. > (rest ’(trp lys asp glu asp ser)) (LYS ASP GLU ASP SER) Lists are actually linked chains of two part structures called cons cells. The two parts are called the first part and the rest part.11 The first part in the cons cell is a pointer to the first element of the list. The rest part in the cons cell is a pointer to the rest of the list, that is, the next cons cell or the empty list (at the end). So, (rest ’(glu trp lys asp glu asp ser)) is the sequence consisting of everything after the first element, that is, it begins with trp in this example. Rounding out basic manipulation of lists, the cons function constructs lists.12 It takes two inputs. The first input becomes the first element of the list, and the second input becomes the rest of the list.13 You can think of cons as creating a new list by putting its first input on the front of the list that is the second input. > (cons ’glu ’(trp lys asp glu asp ser)) (GLU TRP LYS ASP GLU ASP SER) You might think that using cons to put back together the parts returned by first and rest would give back the original list. It is not quite the same. It gives a new list that looks like the original and shares a part (the rest part) but is not identical to the original. Each use of the cons function creates a new cons cell. If we wanted to do something with every element of the list, we could use the first function to get the first element, process it, then use the rest function to get the remainder (or rest) of the list, and just repeat (recursively) the same process on what is left. The only thing to be careful of here is to know when to stop. This requires a check to see if the list is empty. The last cons cell in a list must have the empty list as its rest part. The empty list is represented as () and is also represented by the symbol nil. The function null returns the value “true” (represented by the symbol t) if its input is the empty list. It returns “false,” if the input is anything else. The value “false” is also represented by the symbol nil.14 10. For lists, the nth function also does this, but elt is more general in that it will work with any sequence, including strings and vectors. 11. Originally, these were called car and cdr, respectively. The names come from the way in which the first Lisp implementation worked on an old IBM mainframe computer. In Common Lisp, these terms are no longer preferred, but they are still in use, notably in the other popular Lisp dialect, Scheme [1, 66]. 12. Strictly speaking, cons constructs conses. The rest part of a cons could be a symbol or number or some other structure other than nil or another cons. For a more thorough discussion, see [94, Chapter 3]. 13. If the second input to cons is a list, the result is a list. 14. What I describe here is actually a subset of the possible cons cells, those that form proper lists. Refer to [312, page 22] or [94, Chapter 3] for more details.

Chapter | 1 Biomedical Data

21

In addition to using symbols to name and refer to biomedical entities, we can also use them as variables, in the mathematical sense, that is, we can assign values to them and then put the variables into expressions where the value may vary, but the computation will always be the same. Assignment of a value to a symbol is done with another special form, using the setf operator. The setf operator takes two inputs. The first is the name of a place to put a value, for example, a symbol, which will not be evaluated, and the second is the value to put there (which will be evaluated). An expression using setf is still an expression and just returns its second input as the result. This causes the side-effect of assigning a value to the symbol or place named in the first input. For a symbol, we can find out its value by just typing it as input (without quoting) to the interpreter. > (setf polypeptide-1 ’(trp lys asp glu asp ser)) (TRP LYS ASP GLU ASP SER) > polypeptide-1 (TRP LYS ASP GLU ASP SER) Once a symbol is assigned a value, it can be used anywhere that the value itself would be used. The symbol is not preceded by a quote because we want the value, not the symbol itself. Symbols can also be reassigned values as a program proceeds in its execution. Another useful function for creating lists from other lists is the append function, which creates a new list from input lists. The new list contains all the elements of the original lists, in the same order as the originals. > (first polypeptide-1) TRP > (setf polypeptide-1 (cons ’lys polypeptide-1)) (LYS TRP LYS ASP GLU ASP SER) > polypeptide-1 (LYS TRP LYS ASP GLU ASP SER) > (setf polypeptide-2 (append polypeptide-1 ’(cys tyr tyr ala cys ser ala))) (LYS TRP LYS ASP GLU ASP SER CYS TYR TYR ALA CYS SER ALA) It is important to keep in mind that functions like list, cons, and append do not change their inputs. The lists they produce are new. To preserve a reference to the results for later use, it is necessary to use setf to make the result be the value of some variable or be stored in some other place where data can be referenced. Although assignment is familiar to programmers exposed to most languages, it is really unnecessary for many computations. Very large programs that do important calculations have no assignment expressions in them. They may have hundreds or thousands of functions defined, and when they are used, the user invokes one top-level function, which uses the results of the other functions by nested calls and finally returns a result. What other kinds of operations would be useful to be able to perform on data organized in lists? A useful operation is to search a list to determine if something is present. The built-in function, find, does this. For example, one might ask if a particular protein contains any instances of the amino acid, cysteine, because it has a -SH group, which can form a link with other cysteines in the sequence, and thus affect how the protein folds up into a 3D structure. These links are called disulfide bonds. > (find ’cys polypeptide-1) NIL > (find ’cys polypeptide-2) CYS

22

PART | I Foundations of Biomedical Informatics

The find function returns the first successful match, if found, or nil if no match is found. In addition to finding things, it is useful to know where in the list they are, and it would be especially useful to be able to locate all the occurrences of an item. The position function returns the index or position of the first match with an item if there is a match or nil if unsuccessful. > (position ’cys polypeptide-2) 7 How will we locate all the instances of cysteine? We will need to be able to locate the first one, then search the remainder of the sequence. The position function would be much more useful if we could provide a starting index for it so that it would not necessarily start at the beginning. This is so useful, it is indeed part of the standard definition of the position function. This function has optional inputs, specified by keywords. The idea of keyword arguments or inputs is that you provide a label for each input, rather than depending on the position of the input in the expression. These keyword arguments must come after all the regular required arguments, but they can be in any order since each one is a pair consisting of the keyword and the value. Keywords are symbols beginning with the : character. They have the special property that, like numbers, they evaluate to themselves, and their values cannot be changed. So, for example, the value of the keyword symbol :test is the keyword symbol :test, just as the value of the number 7 is just 7. Many functions, such as find and position, that take sequences (e.g., lists) as inputs have optional keyword arguments. Keyword arguments appear in the parameter list after required and optional arguments and consist of keyword–value pairs. For example, if we want to specify a different comparision for the find function instead of eql, we would provide an input labeled with the :test keyword. Here is an application of find to look up a topic in a list of name–topic pairs. It uses two keyword arguments to find, an alternate test, equal, and an alternate lookup, or key, function to apply to each item before comparing. In this case, instead of comparing the string "gene clinics" with each list, which would fail, it compares the string with the second element of each list. > (find "gene clinics" ’((ira "radiotherapy planning") (peter "gene clinics") (brent "ngi mania")) :test #’equal :key #’second) (PETER "gene clinics") The result of application of find is the entire item, not just the part used for the comparision. This extension makes find very powerful. Table 1.4 lists the standard keyword arguments that can be used with find, position, and several other functions.

TABLE 1.4 Standard Keyword Arguments in Sequence Functions Parameter

Purpose

Default

:test

function for comparision

eql

:key

“lookup” function

identity

:start

starting position

0

:end

ending position

nil

Chapter | 1 Biomedical Data

23

Using the result from the first call to the position function, above, to search for the next cysteine, we would specify starting at position 8, using the :start keyword argument. > (position ’cys polypeptide-2 :start 8) 11 There is no built-in function to accumulate all the positions where a given item appears in a sequence, but we could easily define one. This brings us to the next special form we will need, a means for defining our own functions. To do this, we need to be able to specify what the inputs should be to our function, by giving them temporary or local names, and we will need to specify what expression or expressions to evaluate to get the results for those inputs. A simple example is a function to compute the length of the hypotenuse of a right triangle, given the two other sides.15 We will call the sides x and y, and the function name will be hypotenuse. The operator that creates new function definitions and attaches them to names (symbols) is the defun macro (the name comes from “define function”). > (defun hypotenuse (x y) (sqrt (+ (x x) (* y y)))) HYPOTENUSE The result returned by defun is the symbol naming the new function definition. Usually, a Lisp program consists of a collection of such expressions using defun. Function definitions can use the names of other functions that are defined in this way, just as if they were built-in. So, one can build up a very large and complex program by defining functions that are useable as building blocks in more complex functions etc., until you have a few very powerful functions that you use directly to achieve significant results. This general approach of writing many smaller functional units and combining them to make bigger functional units is called layered modular design. A function defining expression starts with the symbol defun. The first argument (not quoted) is the symbol to be associated with the new function. In the example above, it is the symbol hypotenuse. The next argument or input to defun is a list containing symbols naming formal parameters that are inputs to the function. These symbols can be used in the expressions in the body of the function. They will have values assigned to them when the function is called. In the example above, there are two inputs, denoted by the symbols x and y. The list (x y) in our hypotenuse function example is called a lambda list. It not only specifies local names to use to refer to the inputs, it can also specify that the inputs are keyword inputs and other kinds of inputs as well. The function definition expresses an abstract idea, a computational procedure that can be performed on some kind of inputs. It encapsulates the details of the computation, just as a power tool incorporates complex mechanisms to achieve effects. The user of the power tool has to be careful, but does not have to build the tool over and over each time it is needed for different materials, as long as the materials are of the type for which the tool was designed. The remaining arguments are expressions to be evaluated as the body of the function. The value of the last expression is the value returned by the function. So, as you can infer, if there is more than one expression, all except the last are there to produce temporary or permanent side-effects. In the example above, there is only one expression, (sqrt (+ (x x) (* y y))), and its value is the value returned by the function when it is used. If the first of these expressions in the body is a string (and there are one or more expressions following), that string becomes the documentation associated with the function. This is not the same as a “comment” as used in other programming languages (Common Lisp provides for comments, too). The documentation string, if provided, can be retrieved by code in a running program. Thus, it is possible to provide interactive local documentation. The describe function, a built-in Common Lisp function, returns the documentation associated with its argument. Here is an example. 15. A right triangle has one angle that is a right angle (90◦ ). The hypotenuse is the diagonal, the side opposite the right angle.

24

PART | I Foundations of Biomedical Informatics

> (defun hypotenuse (x y) "returns the hypotenuse of the triangle whose sides are x and y" (sqrt (+ (* x x) (* y y)))) HYPOTENUSE > (describe ’hypotenuse) HYPOTENUSE is a SYMBOL. It is unbound. Its function binding is # which function takes arguments (X Y) Its property list has these indicator/value pairs: DOCUMENTATION "returns the hypotenuse of the triangle whose sides are x and y" Just as quote gives the symbol or list itself, the function operator gives the function object associated with the symbol or function expression. Just as quote is a special form that does not evaluate its argument, function is a special form as well and does not evaluate its argument. In the expression (function plugh), the symbol plugh will not be evaluated, so it should not be quoted. Instead, its function definition will be looked up and returned as a function object. As with quote, this idiom is used so often that it also has a special abbreviation, just as quote does; (function plugh) can be abbreviated as #’plugh. Now, we can implement a function to accumulate all the items. The idea we will use is recursion. In a recursive algorithm, we split the problem into a small piece and a remainder. We assume that the function we are defining can be applied to the remainder just as well as the original. The function will have to first determine if it is done, that is, there is nothing left to compute, in which case it returns a result. If there is work to be done, it does the small piece and then combines that result with the result of using the same (original) function on the remainder. We will start with a very simple example, the factorial function, again using numbers. The factorial function takes as an input a non-negative integer, and its value is the product of all the integers from 1 up to that integer, except for 0; the factorial of 0 is defined to be 1. In mathematical formulas, an exclamation point is sometimes used to denote the factorial of a number, that is, 5! is 120, and n! represents the product of all the positive integers up to and including n. This function is defined mathematically more precisely as follows: if n is 0, the result is simply 1 by definition, otherwise it is the product of n and the factorial of one less than n.  1 if n = 0 f(n) = nf(n − 1) otherwise This is doing the product in reverse, recursively, from n down finally to 0. Although this may be counter to a natural inclination to count up, such recursive definitions can solve very powerful computing problems, especially where the size or structure of the problem is unknown at the start and only becomes apparent when the computation proceeds. To implement the factorial function as a procedure in Lisp, we need to be able to test whether two numbers are equal, and we need to be able to evaluate different expressions depending on the result of such a test. The = function returns t or nil depending on whether its two inputs are numerically equal or not, and the if special form provides conditional evaluation. An if expression has three inputs, a test expression, an expression to evaluate if the test returns t (or anything else non-nil), and an expression to evaluate if the test returns nil. The implementation of the factorial function in Lisp follows. It is a literal translation of the mathematical definition above.16 16. From here on, we will not show the prompt of the Lisp interpreter with defun expressions but will assume that you can accumulate these in a file to become your collection of program code.

Chapter | 1 Biomedical Data

25

(defun factorial (n) (if (= n 0) 1 (* n (factorial (- n 1))))) Each time a function is called or used in evaluating an expression, some information is needed about that function and its inputs. The link to the function definition and the links to the inputs make up a stack frame. These stack frames are accumulated in a list called a stack. As more and more recursive calls are made, the stack becomes larger. When a function evaluation completes, the particular stack frame associated with that use of the function is erased, and the result is returned to the previous function invocation or caller. We can use the trace macro to see how this works. The trace macro takes a function name or list of function names and arranges for extra things to happen. When a traced function is called, the Lisp system will print on the screen the traced function name and its inputs. When the function finishes and returns a result, the result is shown on the screen as well. Using trace, we can see a visual record of the part of the computation that involves the traced function. > (factorial 5) 120 > (trace factorial) (FACTORIAL) > (factorial 5) 0[2]: (FACTORIAL 5) 1[2]: (FACTORIAL 4) 2[2]: (FACTORIAL 3) 3[2]: (FACTORIAL 2) 4[2]: (FACTORIAL 1) 5[2]: (FACTORIAL 0) 5[2]: returned 1 4[2]: returned 1 3[2]: returned 2 2[2]: returned 6 1[2]: returned 24 0[2]: returned 120 120 We will apply this same idea, recursion, to solve the problem of accumulating all the places where an item can be found in a sequence. The function, which we will call all-pos, will have to find the first position, from some starting point, and then use the same method to find the remaining instances by specifying the next position as the new start and recursively calling itself. Since the function will need to be able to start at different places as the search progresses, we include a third input, the place in the sequence to start. When we obtain the position of the next instance of the item, we will need to reuse it, so we make it the value of another local variable within the body of our function. This requires a way to create local variables within a function definition or generally within an expression. The let special form does this. In the following code, the symbol pos serves as a temporary storage or variable that has as its value the result of the position function expression. Finally, how will we accumulate the results? The recursive call should give us a list of the remaining positions, so the first one found should just be put on the front. We already have a function to do this, the cons function. (defun all-pos (item seq start) (let ((pos (position item seq :start start)) (if pos (cons pos

26

PART | I Foundations of Biomedical Informatics

(all-pos item seq (+ 1 pos))) nil))) Note that every recursive function must have some way to determine if it is done, otherwise it may run forever (or until it runs out of resources in the computing environment). In this case, the if expression checks if the position function returned nil, meaning that no more references to the item were found in the sequence. The function will return an empty list (nil) as the result for this case, and if it is a recursive call to the function, the empty list will then be the input to the cons function. So, the result is built up using cons as the recursions complete, just as the factorial function used the * (multiply) function to build up its result. We use all-pos by providing an amino acid symbol, cys for cysteine, to look for, a protein to search (polypeptide-2 on page 21), and we specify 0 as the start point. As expected, both cysteine locations are returned in a list. > (all-pos ’cys polypeptide-2 0) (7 11) A good example of the importance of disulfide bonds is the insulin molecule. Insulin is an important protein that regulates the metabolism of sugar. The disease known as diabetes is directly related to a deficiency in the body’s ability to produce insulin as needed. The stability of the insulin molecule depends on disulfide bonds that form in producing insulin from a precursor protein called proinsulin. The proinsulin folds up, forming the disulfide linkages, then a portion of the proinsulin is cut out by cleavage enzymes. If the disulfide bonds break, the insulin molecule splits into two pieces and cannot refold because the section in the proinsulin that enabled the folding is gone. Polypeptides similar to proinsulin that have the cysteines located differently will not fold up to make insulin. Before moving on to DNA and other data, we will look at two additional ways to implement a function like the all-pos function. These methods will be useful in other applications as well. The fact that the all-pos function requires as an input the starting position from which to search can be a useful feature, but in many cases, such parameters are not useful and almost always should start out with some fixed well-known value (e.g., 0 in this case). A simple way to handle this is to just write a wrapper function, that provides the fixed input. (defun all-positions (item seq) (all-pos item seq 0)) Sometimes, the inner function is really only needed locally for the wrapper to use, and it would be better not to globally define a separate function. In large programs with many functions, it can happen that the same name is used for different definitions in different parts of the program. This will cause serious errors and will be hard to track down. We need a way to define local functions, which have names that are only valid within a limited scope. The labels special form provides this capability. The labels form creates local function definitions with no effect on the outside environment. Thus, we can rewrite all-pos as a local function, which we will call all-pos-aux, and then call it, all within the new wrapper definition of all-positions. (defun all-positions (item seq) (labels ((all-pos-aux (item seq start) (let ((pos (position item seq :start start))) (if pos (cons pos (all-pos-aux item seq (+ 1 pos))) nil)))) (all-pos-aux item seq 0))) Now, we can make one more refinement that is often useful. Because we combine the result of the recursive call with the local value of pos, the recursive process will need to keep track of all the

Chapter | 1 Biomedical Data

27

stack frames as described for the factorial function on page 24. We can make a slight modification that allows the Lisp compiler to implement our function as an iterative process, where there is no need for the stack frames. We do this by rearranging so that the result accumulates on the way in instead of on the way out. Then, when the last call returns, the result is available without threading back through the previous calls. Since no computation is needed on the way out, all those stack frames are unnecessary. Such a function is called tail-recursive. To do this, the auxiliary function (the one defined locally as all-pos-aux) needs one more parameter, accum, a variable to hold the list of found positions, which starts out empty (nil). Thus, we have (defun all-positions (item seq) (labels ((all-pos-aux (item seq start accum) (let ((pos (position item seq :start start))) (if pos (all-pos-aux item seq (+ 1 pos) (cons pos accum)) (reverse accum))))) (all-pos-aux item seq 0 nil))) The only tricky part here is that accum accumulates the values in reverse order, putting each new one on the front of accum, so the result has to be the reverse of the contents of accum. The built-in function reverse does just what we need, taking a list as input and returning a new list, with the items in the reverse of the original order.

1.1.2 DNA and the Genetic Code At the beginning of this section, we introduced proteins as sequences of amino acids and stressed the important roles of proteins as units of control and significant parts of the structure of cells. One of the greatest discoveries in biology in the 20th century was that much of the key information that controls the operation of cells, the basic building blocks of living organisms, is in a huge molecule, generically called “DNA,” short for “Deoxyribo-Nucleic Acid.” One of the functions of DNA is to encode (and transmit to the next generation) information from which the cell can produce proteins. The information sections in the DNA that correspond to and encode for proteins are called “genes.” Some of these correspond to the genes of classical genetics though we now know that the operation of inheritance and expression of genetic characteristics are very much more complicated than the initial ideas discovered by Mendel much earlier. A review article [86] explains and discusses in more detail this question of what is a gene, the challenges of how to describe the workings of DNA. Like the proteins, DNA is itself a sequence of small molecules connected together in a kind of polymer. DNA is a long double-stranded helix, where each strand is a sequence of units called nucleotides. Only four different kinds of nucleotides are found in DNA. These nucleotides are composites of a sugar molecule (β-d-2-deoxyribose, see Figure 1.7), a phosphate (PO3 ) group, and one of four compounds called “bases,” from the purine or pyrimidine family. The bases are guanine, adenine, cytosine, and thymine, and the DNA sequences are typically described by letter sequences naming the bases at each position in one of the two strands making up the DNA molecule. The nucleotides themselves are sometimes also called bases because they are uniquely identified by which base each includes.

59 HOCH2 H H 39

OH

O H

H OH

H

FIGURE 1.7 β-d-2-deoxyribose, the sugar component of the nucleotide units of DNA, with labels to show the locations of the 3 and 5 carbon atoms, where the phosphate groups attach.

28

PART | I Foundations of Biomedical Informatics

FIGURE 1.8 The pyrimidine bases, cytosine and thymine, two of the four bases that are constituents of the nucleotide units of DNA.

H NH2

N

O

O

H

CH3

N

NH2

O N H

FIGURE 1.9 The purine bases, adenine and guanine, the other two bases that are constituents of the nucleotide units of DNA.

O N

N N

N

N H

H

NH2

N

N N

N H

CACTGGCATGATCAGGACTCACTGCAGCCTTGACTCCCAGGCTCAGTAGATCCTCCTACCTCAGCCTCTC GAGTAACTGGGACCACAGGCGAGCATCACCATGCTCAGCTAGTTTTTGTATTTGTAGAGATGAGGTTTCA CCATATTGCCCAGGCTGGTCTTGAACTCCTGGGCTCAAGCAAGCCACCCACCTTGGCCACCCAAAGTGCT FIGURE 1.10 An excerpt of a DNA sequence from the BRCA1 gene.

The “backbone” of the DNA molecule is a sequence consisting of alternating phosphate groups and sugar (deoxyribose) molecules. The phosphate group connects the sugar molecules together by bonding at the carbon atoms labeled 3 and 5 in Figure 1.7. The OH at the 3 carbon connects to the phosphate group (PO3 ), and the OH at the 5’ carbon connects to the other end of the phosphate group, splitting out a water (H2 O) molecule in the process. The bases connect to the sugar molecules at the 1 position, at the right in Figure 1.7. The chemical structures of the bases are shown in Figures 1.8 and 1.9. Nucleotides are labeled by the names of the bases that are attached to the sugar-phosphate “backbone” units. The pattern of nucleotide sequences is different in different kinds of organisms and even between different organisms in the same species, but these four units are the same ones used in the DNA of all living organisms. In most data sources, such as NCBI’s GenBank, a typical representation of a DNA molecule or sequence would consist of a sequence of letters (or symbols), using the four letters G, C, A, and T, to represent each of the possible four nucleotide (also called “base”) pairs that could appear in a doublehelix DNA strand. Although the DNA molecule is double-stranded, the bases are paired uniquely, A with T and G with C, so that only the bases on one strand need to be represented. Figure 1.10 shows a small fragment of the region around a well-known gene associated with breast cancer called BRCA1.17 The letters represent the nucleotides, the small molecules that are connected together in sequences that make up DNA molecules. The four nucleotides are labeled with the four letters, A, C, G, and T. Strictly speaking, DNA is double-stranded, but we are only presenting a symbolic representation of one of the two strands because the bases in corresponding positions in the two strands pair uniquely with one another, so specifying one strand determines the other.

The Fundamental Dogma of Molecular Biology The relation between DNA and proteins is called the “genetic code.” Each amino acid corresponds to one or more patterns of three nucleotides. For example, the nucleotide sequence GGA corresponds

17. Obtained from NCBI GenBank web site, contig NT_010755.15 starting at position 4859744.

Chapter | 1 Biomedical Data

29

TABLE 1.5 The Genetic Code by Amino Acid Letter

Abbreviation

Full name

Codons

A

Ala

Alanine

GCA GCC GCG GCT

C

Cys

Cysteine

TGC TGT

D

Asp

Aspartate

GAC GAT

E

Glu

Glutamate

GAA GAG

F

Phe

Phenylalanine

TTC TTT

G

Gly

Glycine

GGA GGC GGG GGT

H

His

Histidine

CAC CAT

I

Ile

Isoleucine

ATA ATC ATT

K

Lys

Lysine

AAA AAG

L

Leu

Leucine

TTA TTG CTA CTC CTG CTT

M

Met

Methionine

ATG

N

Asn

Asparagine

AAC AAT

P

Pro

Proline

CCA CCC CCG CCT

Q

Gln

Glutamine

CAA CAG

R

Arg

Arginine

AGA AGG CGA CGC CGG CGT

S

Ser

Serine

AGC AGT TCA TCC TCG TCT

T

Thr

Threonine

ACA ACC ACG ACT

V

Val

Valine

GTA GTC GTG GTT

W

Trp

Tryptophan

TGG

Y

Tyr

Tyrosine

TAC TAT

to the amino acid glycine, and TTC corresponds to the amino acid phenylalanine. Each combination of three nucleotides is called a codon. With four possible nucleotides in three places, there are 64 (4 × 4 × 4) codons altogether. Not all codons correspond to amino acids; there are three special codons that signal the end of a sequence, TAA, TAG, and TGA. For most of the amino acids, there are several codons that represent the same amino acid. For example, the amino acid lysine is represented by two codons, AAA and AAG, and leucine is represented by any one of six. Table 1.5 shows the standard correspondence between codons and amino acids. This correspondence is approximately the same in all known organisms. At the NCBI web site, in the taxonomy section,18 there is a tabulation of the Standard Code (shown here) and other known codes, many of which are used in mitochondrial DNA. Sections of DNA that code for proteins consist of genes, which, when activated, are transcribed (copied) into a similar kind of molecule, RNA, which differs only in that the base thymine is replaced by another base, uracil, denoted by the letter U and the sugar component, β-d-ribose, differs from β-d-2-deoxyribose in that the ribose form has an OH group instead of just an H in one of the ring positions. Figure 1.11 shows the chemical structures of β-d-ribose and uracil.

18. URL http://www.ncbi.nlm.nih.gov/Taxonomy/Utils/wprintgc.cgi?mode=c.

30

PART | I Foundations of Biomedical Informatics

FIGURE 1.11 The sugar, β-d-ribose, and the base, uracil, which are constituents of the nucleotide units of RNA.

H HOCH2

OH

O H

H H

H OH

O

N

O N H

OH

The codon for methionine, ATG, is also a “start” codon, indicating where the transcription of DNA into RNA will begin, so most proteins have a methionine at the beginning of their chains. The ATG by itself is not sufficient to initiate transcription (copying of DNA into RNA) or translation (synthesis of a protein using the encoding in a strand of RNA). It is also necessary to have a promoter region where a protein called RNA polymerase can bind to the DNA strand. Identifying promoter regions and other elements of the transcription process is a challenging problem. In prokaryotes (cells without well defined nuclei), the process of mapping from DNA to RNA to proteins is simpler than in eukaryotes (cells with nuclei enclosed by nuclear membranes). In prokaryotes, the RNA strand containing coding information that is transcribed from the genetic DNA is translated directly into an amino acid sequence. In eukaryotes, much of the DNA in the region of so-called genes actually does not code for proteins. The RNA that is transcribed consists of a sequence of coding regions and non-coding regions. The coding regions are called “exons” (because they are external or expressed), while the non-coding regions are called “introns,” since they are internal and not expressed as protein sequences. The identification of genes, that is, where along a DNA strand the transcription starts, is a very hard problem, about which much knowledge exists, but for which there is no single algorithmic method. Similarly, distinguishing between exons and introns is also a very difficult problem. The initial RNA that is produced in the transcription step (in eukaryotes) is spliced to remove the introns. The resulting “mature” RNA, which then leaves the nucleus, is called messenger RNA or mRNA. However, some of the RNA strands generated in the transcription process are important molecules by themselves. In particular, there are special RNA molecules called transfer RNA (tRNA), whose function is to provide links in the construction of proteins from the mRNA. Each amino acid corresponds to at least one tRNA. For some amino acids, there are several tRNA types. The tRNA molecules are highly folded into a more or less double-ended shape. One end has a codon that is complementary to the codon in the mRNA that will be translated to an amino acid, and the other end binds the specific amino acid corresponding to the codon. The mRNA molecule is picked up in the cytoplasm of the cell by a ribosome, a complex structure that mediates the translation of the mRNA into a protein. As the ribosome moves along the mRNA, the right tRNA binds to the next codon in the sequence. The tRNA molecules are rather like jigs or tools that hold together parts on an assembly line so that the parts can be joined together. Once the join of the new amino acid is made to the existing chain, the tRNA disconnects, and the ribosome moves on to the next codon to be translated. This process is shown diagrammatically in Figure 1.12. The proteins in turn regulate many of the activities of the cell, including the expression or activity of transcription and translation. Some aspects of the transcription and translation process can be modeled by simple computations. This is described in Chapter 5. The complete DNA sequence for a given organism is called its genome. The genomes of many organisms contain over a billion such nucleotides. Biologists have determined the genomes (partially or completely) for hundreds of organisms. Moreover, much information is now available for hundreds of thousands of individual genes and proteins, including how they interact with each other and how activity levels of genes and proteins vary with different experimental conditions. More background on molecular and cellular biology can be found in an article by Larry Hunter in the AI Magazine [117] and the opening chapter in an earlier book [116] on which the article is based. A broader treatment of this subject will be available in a forthcoming text by the same author [118]. For the ambitious reader, standard textbooks such as [5] go into even more comprehensive detail.

Chapter | 1 Biomedical Data

31

FIGURE 1.12 Illustration of the process of transcription and translation from DNA to mRNA to proteins (courtesy of National Human Genome Research Institute, or NHGRI).

DNA

mRNA Transcription

Mature mRNA

Nucleus

tRNA Transport to cytoplasm for protein synthesis (translation) mRNA

Cell membrane

Representing DNA in Computer Programs To illustrate how to use a simple encoding to compute useful things from such data, consider a sequence of nucleotides, as described earlier. In a typical computerized encoding, each letter is represented by its ASCII code, and so each occupies 8 bits in a text file (although ASCII is a 7-bit code, it is usual to use 8 bit “bytes”). We can represent base sequences as letter sequences or long strings. Another way to represent such sequences is to represent each nucleotide (or base) as a symbol in a list. The entire sequence in Figure 1.10 then becomes a list of symbols and looks like this: (C T T G T G A

A C C C T G G

C C G T C G T

T C A C A C G

G A G A C T C

G C G G T A G C C A C A T)

A C A T T A

T T C A A G

G C T G T C

A A G T T A

T G G T G A

C T G T C G

A A A T C C

G G C T C C

G A C G A A

A T A T G C

C C C A G C

T C A T C C

C T G T T A

A C G T G C

C C C G G C

T T G T T T

G A A A C T

C C G G T G

A C C A T G

G T A G G C

C C T A A C

C A C T A A

T G A G C C

T C C A T C

G C C G C C

A T A G C A

C C T T T A

We will use such a representation to count the number of occurrences of the various symbols, as a way of computing the percentage of each of the four nucleotides in any given DNA sequence. Here is a function that counts the number of Gs that appear in a DNA sequence such as the BRCA1 excerpt above. (defun count-g (dna) (if (null dna) 0 (if (eql (first dna) ’g) (+ 1 (count-g (rest dna))) (count-g (rest dna)))))

32

PART | I Foundations of Biomedical Informatics

This function checks if the sequence, named dna here, is an empty list. It does this by calling the null function. The null function returns t if its input is nil and returns nil if its input is not nil. If the sequence is empty, there are certainly no Gs, so the function returns 0 as its result. If the list is not empty, a nested if expression checks the first base in the list, and either adds 1 or does not add 1 to the result of computing the Gs in the rest of the list. We do not need to know how long the list is. When the program reaches the end of the list, it does not go any further, that is, there are no more recursive calls. Now, it turns out that counting items in a list is so useful that there is a built-in function in ANSI Common Lisp, called count, so another way to do the above is simply to use this built-in function. Instead of (count-g seq), we would write (count ’g seq), where seq has a value, which is a list of the bases in a DNA sequence. The code for count-g is valuable anyway to introduce you to the idea of being able to write your own counting functions. This will be very important for more complex situations where there is no pre-existing facility. The DNA in a cell normally consists of two complementary strands in which each of the bases in one strand is bound to a corresponding base in the other strand. Adenine binds to thymine, and guanine binds to cytosine. This pairing occurs because adenine and thymine each have two locations where a hydrogen bond is readily formed, and they match each other, while guanine and cytosine each have three such locations that match up. Thus, one would expect that G–C bonds will be somewhat stronger than A–T bonds. This is important in biological experiments involving the determination of the sequence of a DNA strand. In many cases, the biologist has a DNA sample that does not have enough copies of a DNA strand to be able to determine its sequence. In this case, a very clever method called the polymerase chain reaction (PCR), is used to amplify the DNA so that enough is available for the next steps. In each step of the PCR process, each of the two complementary strands is replicated by synthesizing a new complementary strand for each, thus doubling the number of strands. Many doublings are possible. After only 30 doublings, the number of strands are increased a billion times.19 The way the complementary strands are generated is to provide short sequences of nucleotides, called primers, that bind to the right starting places on each of the original strands. Since we want high efficiency, choosing binding sites and primers that are high in GC content usually is preferred. So, it is useful to be able to compute the percentage of the sequence that consists of G and C. It is again a simple counting problem. We used recursion to count the Gs in the earlier example. Here, we need to accumulate multiple results. While this can be done by calling the count function four times, it will involve traversing the sequence four times. By customizing, we can reduce this to a single traversal, accumulating counts of all four bases simultaneously. There is no built-in function to do this, but we can easily write this function, using other built-in facilities of Common Lisp. This time, rather than recursion, we will write the process in terms of iteration. Common Lisp includes iteration operators since this is very useful. The dolist function will iterate over a list, setting the value of a local variable (in this case, the symbol base) to each successive element in turn. Four local variables created by a let expression will hold running counts of the four bases, and we will use the incf operator to count up for each base we find. The incf operator takes as input a symbol or other name of a place where a numeric value is stored and increases it by one. Like setf, incf modifies the value associated with the place name it gets as input. One approach would be to selectively count the G and C symbols while keeping a running total of all the bases. However, it is just as easy to count each of the four bases and then compute the ratio from that. To count all the bases in a list such as the one above, just go through one by one, using four variables that accumulate the numbers. (defun dna-count-simple (seq) "does an explicit count of the G A C and T in seq" (let ((ng 0) (na 0) 19. Such is the simple power of exponential growth: 230 is about a billion.

Chapter | 1 Biomedical Data

33

(nc 0) (nt 0)) (dolist (base seq) (case base (g (incf ng)) (a (incf na)) (c (incf nc)) (t (incf nt)))) (list ng na nc nt))) The symbol base is a local variable within the dolist expression. For each element of the list, seq, the variable base is assigned that value, and the body of the dolist is executed. In this particular function, the dolist body uses the case operator to determine which one of the four counters, ng, na, nc, or nt, to increment, depending on the value of base. The result is a list of four numbers in a predetermined order, number of G, number of A, number of C, and number of T. To compute the GC ratio from a list of four numbers in the order returned by dna-count-simple, divide the sum of the first and third numbers by the sum of all four. This function in mathematical notation is as follows, where R is the GC ratio, T0 , T1 , etc., refer to the elements of the list, zero indexed, and the means add up all four T numbers. T0 + T 2 R(T) = 3 i=0 Ti You might think we can do a straightforward translation into Lisp, as follows: (defun gc-ratio (freq-table) (/ (+ (first freq-table) (third freq-table)) (+ freq-table))) However, we cannot just write (+ freq-table) because the value of freq-table is a list, and we need the numbers as individual inputs, not a list, that is, we need (+ 23 65 13 45), not (+ ’(23 65 13 45)). The apply function arranges for this. The inputs to apply are a function and a list of arguments.20 The apply function will rearrange its inputs so that the list, the second argument to apply, becomes the rest of an expression in which the function appears in the right place. In order to do this, we need to be able to treat functions as pieces of data, as inputs to other functions. Thus, we need the function whose name is the + symbol. There is a special form for this, called function. The expression (function +) evaluates to the function whose name is +, and we can then pass that function as input to another or use it with apply. Then, (apply (function +) ’(23 65 13 45)) will be the same as if we wrote just (+ 23 65 13 45). Now, we can create lists of arguments, assign such lists to variables, and use the lists where otherwise we would have no way to write out the individual elements in the right form. So, if the variable freq-table had the list of base counts and we want to add them up, we write (apply (function +) freq-table) and it gives the desired result. Passing functions as arguments is so often needed that the function special form has an abbreviation that is widely used, just as there is an abbreviation for the quote 20. Actually, apply, like many other built-in operators, has a much richer semantics than described here. To learn more about this and other functions, standard books on Common Lisp such as [94, 312] are highly recommended.

34

PART | I Foundations of Biomedical Informatics

special form. We write (function x) as #’x, so the expression above would become simply (apply #’+ freq-table). In the rest of the book, we will use the #’ notation, rather than writing out the function form. So, here, we use the #’ notation to specify that we intend the function named + as the first input to the apply function.21 (defun gc-ratio (freq-table) (/ (+ (first freq-table) (third freq-table)) (apply #’+ freq-table))) To do the entire operation, we compose the two functions, that is, the result of one function will be the input to the other, and of course we need a way to read the data from a file and convert it into a list of symbols. That file reading problem will be solved later. For now, just imagine that we have already written a function called get-data that takes a filename as input and returns the kind of list we have described above. Then, here is a function that combines the operations into one. Given the filename, it returns the GC ratio, a single number. This illustrates the idea of functional composition in which we build up powerful complex functions from layers of simpler functions. (defun gc-ratio-from-file (filename) (gc-ratio (dna-count-simple (get-data filename)))) A more general solution to the problem of counting occurrences of items like bases would add table entries as new items are found in the list. That way, the same code can be used to count frequencies for bases, for amino acids in polypeptides, or any other sequences. Each item’s entry in the resulting table would be a pair, with the item first, then the number of occurrences. If a table entry already exists for the item, just increment it, otherwise add a new entry with the initial count set to 1. Here, we just use a list to hold the pairs. Each pair is a list containing the item (usually a symbol) and the running count. This code illustrates that the incf operator can increment any number stored in a named place. Here, the expression (second tmp) is used as the name of the place where the count is stored, and it is directly altered. (defun item-count (seq) "returns a frequency table of all the items in seq, a list of items, tagging the count by the item itself" (let ((results nil)) (dolist (item seq results) (let ((tmp (find item results :key #’first))) (if tmp (incf (second tmp)) (push (list item 1) results)))))) Now, we show how to implement get-data. It reads a file containing only the letters of the sequence, possibly with some whitespace characters and numbers labeling the lines in the files. Actually, the files typically available from bioinformatics databases such as GenBank and Swiss-Prot are more complex. These files contain additional data about the sequences, such as who submitted them, what functions or identification might be assigned to them, cross-reference identifiers to other databases, and other properties of the biomolecule that the sequence represents. There are many formats in use, and the databases have overlapping but not identical structure and content. Extracting information from such files and converting data from one form to another takes up a large percentage of the programming effort in developing bioinformatics software. For now, we will ignore all these issues. In Chapter 5, we will, however, add a little more code to be able to read one of the simpler file formats, the so-called

21. The Common Lisp standard allows just the quoted symbol as well, but in my opinion, if you intend to provide a function, using this notation makes the intention so much clearer.

Chapter | 1 Biomedical Data

35

FASTA format, named for a sequence alignment package first developed in 1985 by David Lipman and William Pearson [197, 248]. A straightforward recursive implementation to read a sequence from a file would be to read a single character, make it into a string, turn it into the corresponding symbol, and put it on the front of a list that is returned by recursively reading the rest of the file. The resulting list is built up from the end back to the beginning as each recursive call returns a successively larger list. The final resulting list is in the same order as in the file (you should walk through the code by hand with a small example to convince yourself that the order is right). The string function returns a one-character long string from its input, and the intern function creates or just returns the symbol whose name is the string that is the input. You could just create a list of characters instead of converting them to symbols, but it is a good idea to get used to using symbols to represent abstract entities. For more complex operations that we will want to perform later, characters or strings will not be suitable. (defun naive-read-from-file (strm) (let ((char (read-char strm nil :eof))) (if (eql char :eof) nil (cons (intern (string char)) (naive-read-from-file strm))))) This function takes a stream as input. A stream is a source of (or sink for) sequential data, with indefinite length, that is, you can keep asking for more items with each successive access or keep writing items out to it. Files are typically opened for reading and writing as streams. Data can be written to a stream (using the print function and others) as well as read from it. The read-char function reads a single character from a stream that is an open connection to a text file. In the above example, the variable strm is the open stream, the nil argument specifies that reaching the end of the file should not be treated as an error, and the :eof symbol specifies what the read-char function should return in case the end of the file is reached.22 As explained earlier, for each recursive function call, a stack frame must be allocated to hold the information for that invocation of naive-read-from-file. Space for the stack is large but limited in most computing environments. Even in very large programs, this is not a problem since most functions will do their work and return a result without too much calling of themselves or other functions. However, for big files, this particular function will fail because the number of stack frames required is so large that the program will likely run out of stack space. As an example, the full BRCA1 file downloaded from NCBI has a sequence of about 200,000 bases. A list of 200,000 cons cells is not very big and easily accommodated in most any Lisp working environment. But, a stack that has to grow to 200,000 stack frames is a very large demand because each stack frame is much larger than a cons cell, and typically much less space is available for the stack than for working data in a program. This is another example like our first attempt at finding all the positions of an item in a sequence (see page 27) where recursion is logically sound and an elegant solution but impractical. However, as befores, by rearranging the code so that the list is built on the way in, rather than on the way out, a good compiler can turn the recursive code into an iterative process. As before, the result list is in reverse order from what is in the file, so we have to return the reverse of the accumulated result. (defun read-from-file (strm accum) (let ((char (read-char strm nil :eof))) (if (eql char :eof) (reverse accum) (read-from-file strm (cons (intern (string char)) accum))))) 22. Symbols that begin with the colon (:) character are constant symbols. Like numbers and strings, they evaluate to themselves, so the value of the symbol :eof is the symbol :eof. Unlike ordinary symbols, their values cannot be changed by assignment, just as you cannot change the value of the number 7.

36

PART | I Foundations of Biomedical Informatics

One other wrinkle with this tail-recursive function, read-from-file, is that it takes two parameters, the input stream and an accumulator. In most uses, the accumulator variable, accum, should start with an empty list and accumulate items onto it as the recursive calls proceed. Here is how the read-from-file function would typically be used: (defun get-data (filename) (with-open-file (strm filename) (read-from-file strm nil))) The with-open-file operator opens the file named by the variable filename, whose value should be a string or pathname and assigns the resulting stream as the value of the variable strm. That stream is then the input to the read-from-file function defined previously. When read-from-file finishes, the with-open-file operator closes the stream and the file. Finally, the file may contain space characters, end-of-line or newline characters, or other punctuation, beyond the basic G, C, A, and T. As well, we might want to read files that have either uppercase or lowercase base letters. So, we just add a line to check what character was read in, and if it is one of those we are looking for, we retain it, otherwise we skip it. A single character by itself will be interpreted as a symbol with a one-character name, so we need a way to designate a character as a character data type. The way this is done is to precede it with a prefix, #\, so the character c is denoted as #\c, etc. Uppercase characters are distinct from lowercase, and so we list both. Thus, the final version of read-from-file has to handle three conditions, and we replace the if expression with one using cond. The cond operator is similar to if but instead of alternatives, it has a series of clause forms as its inputs. The first expression in each clause is evaluated, until one evaluates non-nil, or the end of the cond expression is reached. The first clause with a non-nil first expression result is then examined and if there are any further expressions they are evaluated in sequence, and the value of the last one is the result of the cond. The remaining clauses are ignored. If no first expressions evaluate non-nil, the result of the cond is nil. The three conditions are 1. end of file reached, so just return the result, 2. a valid character was read, so add it to accum and continue via a recursive call, 3. a non-valid character was read, so just continue with the recursive call. and the code then follows the description. (defun read-from-file (strm accum) (let ((char (read-char strm nil :eof))) (cond ((eql char :eof) (reverse accum)) ((member char (list #\g #\c #\a #\t #\G #\C #\A #\T)) (read-from-file strm (cons (intern (string-upcase (string char))) accum))) (t (read-from-file strm accum))))) In Chapter 5, we show how to read an entire file of several hundred thousand records, the UniProt Knowledge Base FASTA file, downloadable from the ExPASy web site (http://www.expasy.ch) of the Swiss Institute for Bioinformatics. From such a file, one can then process the sequences to get some theoretical characteristics of the proteins, such as molecular mass. We also show how to compute the percent amino acid content of each sequence and compare them for closeness of match. More sophisticated variants are left as exercises, for example, reading through until you find a record with a specified accession number or reading records until a partial sequence match is found with some unknown sequence. Section 2.5 of Chapter 2 introduces the idea of searching through networks or

Chapter | 1 Biomedical Data

37

complex structures. The methods of search can be used to solve the sequence matching problem, and that application is also described in Chapter 5.

1.1.3 Anatomy The process of mapping out the structure of the human body has been going on for several thousand years. As early as 1600 B.C.E., the ancient Egyptians apparently knew how to deal with a considerable range of injuries by surgical procedures as well as other basic medical knowledge, such as the role of the heart in circulating body fluids. This was documented in an ancient artifact called the “Edwin Smith Surgical Papyrus,” discovered in Egypt, translated by James Henry Breasted [32], and currently held by the New York Academy of Medicine. It is one of several such documents that record much knowledge of anatomy. The ancient Greeks, in the 5th and 4th centuries B.C.E., continued to study anatomy as well as physiology. Prominent contributors were Aristotle, whose work on logic was a starting point for the symbolic logic to be developed in Chapter 2, and Hippocrates, to whom we owe one of the widely used oaths taken by graduates of medical schools at the time of conferring of their medical doctor degrees. In the 2nd century C.E., Galen practiced and wrote about surgery and anatomy. A well-known system of nomenclature for biomedical concepts and entities is named after him and will be described also in Chapter 2. The study of anatomy continued in Europe and the Middle East through the Middle Ages, and now worldwide, through modern times.23 A huge boost technologically was the development of X-ray imaging at the beginning of the 20th century, and even more so, the development of cross-sectional imaging using X-rays [the computed tomography (CT) scanner, and later the magnetic resonance imaging (MRI) scanner]. The ability to produce images of living animals (including humans), without invasive surgical procedures, has revolutionized diagnostic medicine as well as opened new possibilities for visualization of anatomy for teaching purposes. The Visible Human Project of the NLM [226, 229] has provided 3D image data for two entire human bodies, male and female, for use in both research and teaching. Two separate but related kinds of information about anatomy are useful to represent in computerized form. First, the logical relationships discovered in ancient times, and revised many times, express what kinds of things are contained in a human body and how these things are related. This is the kind of information found in the FMA and excerpted in Figure 1.5. The representation of these anatomic entities and their relationships in the FMA is based on the idea of frames, which will be developed in Section 2.3 of Chapter 2. Access to the FMA contents, including searching and traversing its many relationships, will be covered in Chapter 6, and an application of the FMA to prediction of the spread of cancer cells is described in Section 9.3.1 of Chapter 9. The essential idea here is to be able to represent symbols and use lists to group them into entities, attributes, and relations. Thus, the heart information could become a list structure with the attributes labeled by symbolic tags and the values implemented as lists of symbols, as follows: (heart (part-of cardiovascular-system) (contained-in middle-mediastinal-space) (has-parts (right-atrium left-atrium right-ventricle left-ventricle mitral-valve tricuspid-valve ...)) (arterial-supply (right-coronary-artery left-coronary-artery)) (nerve-supply ...) ...)

23. A brief history of the development of the science of anatomy may be found in Wikipedia under “history of anatomy.”

38

PART | I Foundations of Biomedical Informatics

In addition to the logic of anatomy, however, two additional very important kinds of data need representation as well. One of these is the image data mentioned earlier, both X-ray projected images and cross-sectional images, and also photographic images, for example, of skin lesions or open views into a body during surgery. Microscope images provide views of anatomy at the tissue and cellular level. So, we need a representation and methods for computing with (and display of ) image data. Images are usually represented as arrays of numbers, with each number or set of numbers corresponding to a color or gray level for a particular spot or pixel in the image. The image is then considered to consist of a rectangular array of such spots. If the resolution is high enough, a considerable amount of detail can be discerned. In Section 1.1.5 we show how to represent cross-sectional images, do gray-scale mapping, and compute sagittal and coronal images from a set of transverse cross-sectional images. Section 1.2.4 illlustrates how to store and retrieve image data in a relatively simple system using a combination of text and binary files. Finally, the anatomic objects that appear in image data sets often need to be identified and delineated with their exact shapes represented, for purposes of illustration, and more importantly to perform measurements on these organs and other components (e.g., tumors). The exact location of such objects in a particular cancer patient’s body is crucial information for designing and delivering accurate and effective radiation treatment. This is further developed in Chapter 9. Here, it will suffice to say that some kind of 3D coordinate system, with X, Y , and Z axes and a well-defined origin point, is needed. Typically, organs and tumors are represented as collections of planar contours or polygons. A simple but effective representation of a contour is a list of points, where each point in the polygon is a two-element list consisting of the X coordinate and the Y coordinate, assuming that the points all are in the same Z plane. To make the data more self-contained, we can include the Z value along with the list of points, in a larger list, using symbols to label these two components. The points are non-redundant, that is, it is assumed that in rendering the contour or computing area or volume from it, the last point is connected back to the first. (contour (z 2.0) (vertices ((-3.41 (-3.87 (-2.91 (-1.68 (-2.55

6.15) 7.51) 8.33) 7.79) 6.10)

(-3.87 (-3.87 (-2.41 (-1.64 (-3.00

6.47) (-4.01 7.61) (-3.46 8.20) (-2.05 7.10) (-2.00 6.06))))

7.01) 8.11) 8.15) 6.47)

These polygons are usually created from the images manually, using a computer-aided drawing tool. This is an extremely time-consuming process but is so important that many decades of research have been devoted to the development of algorithms for automating this delineation of objects from images, usually called image segmentation. Many such algorithms are in use today in clinical systems though there is still much room for improvement in accuracy, success rate (sometimes the algorithm simply fails to find a contour), and speed. Making useable tools based on successful algorithms is also challenging and a subject of research in human computer interaction.

1.1.4 Medical Laboratory Data Here is a way to represent laboratory results such as those in Tables 1.1 and 1.2, for example, the red and white cell counts in the blood of a patient. (cbc (wbc 6.14 thou-per-microltr) (rbc 4.80 mill-per-microltr) (hemoglobin 13.8 grams-per-dl) (hematocrit 40 percent) (platelets 229 thou-per-microltr))

Chapter | 1 Biomedical Data

39

This expression encodes part of the results of a complete blood count (labeled by the symbol cbc) and consists of the white cell count, with its symbolic label, wbc, the numeric value, and the units, thousands per microliter, represented by the symbol, thou-per-microltr, along with a red cell count, similarly encoded. Here, again, we have used standard Latin text characters and chosen symbol names that would be somewhat familiar to practitioners and used digits and decimal points to represent numbers. To make this encoding easy for people to read, I have started the inner lists on separate lines and indented them slightly, just as for the enzyme data on page 14. For the laboratory tests, one would want to look up a particular value by name, for example, the white blood cell count, which will give some indication of the presence of infection. Although it would seem that these laboratory tests are all numerical values and have a certain regularity, in fact, there are thousands of such tests, many with nonnumeric result types and with highly variable structure. Moreover, although the names above seem straightforward, they leave out a lot of important information about the test, for example, how it was performed, under what conditions, and what constitutes a normal range of results for the particular laboratory. In a typical clinical laboratory, the instruments produce results in digital form, and these results are stored in computers running clinical laboratory system software. These systems have in the past been made accessible through local area network access but that required clinicians and other staffs on the wards to learn how to use the specific laboratory system software and, of course, required the clinical laboratory to manage access by issuing user IDs and passwords to everyone. The next step in evolution was to provide some way to transmit the laboratory data to another system, the electronic medical record, which (it was hoped) would provide an integrated view of all the sources of medical data as well as provide a central system for registration of patients, scheduling clinic visits, tracking inpatients, accepting orders for medications, and generating the bills to the patients or their insurance plans. At present, the only generally accepted standard for constructing, sending, and interpreting messages with this data in them is the Health Level 7 (HL7) standard, developed and managed by a consortium known as (oddly enough) HL7. In Chapter 8, Section 8.3, we show how network communication of medical data works and provides some details about the HL7 standard. The HL7 standard does not specify the names, encoding of values, grouping of tests into panels, or other low-level details. Many systems have been put into use, and the definitions of these panels may vary from one institution to the next or even from one device manufacturer to the next. So, to integrate many such systems even in a single institution, it is necessary to translate one set of definitions into the others. Electronic medical record systems cannot, therefore, be standardized and simply installed. Each hospital needs to define its own tables of tests, conventions for displaying results, and display screens that organize the data the way it is needed for that institution. To exchange data between institutions is of course very much more difficult. To achieve meaningful data interchange, one of the first steps needed is to create a standard system of nomenclature for the tests and for the encoding of the test result values. A well-known scheme for labeling and encoding laboratory test results is the Logical Observation Identifier Names and Codes (LOINC)24 system [208]. The LOINC system proposes a set of names and codes for labeling laboratory results and clinical observations. This involves achieving agreement about the type of a datum, its external representation, the units in which it is measured, and other factors that affect the interpretation of the result being reported. The goal of LOINC is to assign unique codes and names to each of the thousands of observations and laboratory tests in use in clinical practice so that the associated data for a particular patient can be labeled in a computerized message transmitting the data between various electronic medical record (EMR) systems and other application programs using medical data. Similarly, these same codes can be used by an electronic medical test order entry system to identify what a care provider has ordered for a patient. Although LOINC started out with a focus only on the clinical laboratory, today it encompasses a broad range of tests and observations throughout medical practice. The current set of identifiers has over 50,000 entries.

24. “LOINC” is a registered trademark of Regenstreif Institute, Inc.

40

PART | I Foundations of Biomedical Informatics

The LOINC table is available from the Regenstrief Institute as a text file. The entries are organized into one record per line of text where lines are delimited by a two-character sequence. Within a record or single line, individual fields are delimited by characters, used as separators, so that two successive characters indicate a blank or omitted field. Strings are represented as text surrounded by double-quote characters, as in Lisp. The few fields that are not strings are integers. This makes it easy to read in the LOINC codes into a list for processing in a program, except for handling the characters, which is a little tricky. This problem of reading data files in various formats and transforming the data into data structures that can be used by computer programs is widespread throughout biomedical informatics. Tab-delimited text is used frequently enough to warrant writing some code that handles it in general and the LOINC file in particular. The strategy will be to write a function, parse-line, that takes as input a line of text containing tab-delimited data and returns a list of the individual items. We will assume that the items are readable by the Lisp read function, that is, we would not deal with parsing or interpreting the items themselves. Then, the parse-line function will be applied a line at a time to each line in the LOINC file by another function parse-loinc. The strategy for parse-line will be to write an inner function (in a labels expression, of course) called read-items, which just processes a single item at a time, puts it on an accumulator list, and calls itself recursively to process the rest of the items. The tricky part is in handling the tab characters. Our recursive inner function starts out the same way all such functions do, which is to check if it is at the end of the line, in this case the input variable, str. The variable pos is the position of the next character to be read, so if it is greater than or equal to the length of the string, we have reached the end. In this case, if the previous character read was a tab character (i.e., tab is t), it means there is a blank or empty field at the end of the line, so we add a blank string to the accumulator, accum, otherwise we return the accumulator value as is (actually it returns the reverse of the accumulator list since it has been built backward). If we are not at the end, there are several possibilities. Either the first character to be read is a tab or it is not. If it is, we are going to recursively process what is left. If the previous character read was a tab, here too, we have to add in a blank string since two successive tab characters indicate an empty field. If the first character is not a tab, we have some data to process. The built-in Common Lisp function read-from-string can read this data and convert it into an internal Lisp item, for example, a string or a number. We need to specify as inputs not only the string to read (the variable str) but also that read-from-string should not signal an error when it reaches the end of the string, and it should start at a position not necessarily the beginning (this is the value of the pos variable). We need back from read-from-string two things, the result of reading the data item and the position at which the next character should be read. Indeed, the read-from-string function provides exactly those two values. Until now, we have been using and writing functions that each return a single value. The read-from-string function is an example of a function that returns multiple values. To use them, we use the multiple-value-bind operator to make them the values of local variables. It is like let, in that these variables can be used within the scope of the expression, but not outside. The item variable contains the item that was read or the symbol :eof if the end of the string was reached. If it is :eof, then the function read-items will return the accumulated list of items to that point (actually the reverse of the list as we noted earlier). If the end was not reached, the item is put on the accumulator and a recursive call is made to process what remains. In the recursive call, the value for the position variable, pos, is the value of next since that is the next character to process. Once we have the inner function, read-items, the main function just calls it, with an empty accumulator, starting at position 0. The tab variable starts out with a value of t because we are going to start by processing a field, that is, if the line starts with a tab, it means the first field is blank.

Chapter | 1 Biomedical Data

41

(defun parse-line (line) "parses tab delimited text, assumes no other whitespace between objects" (labels ((read-items (str accum pos tab) (if (>= pos (length str)) (reverse (if tab (cons "" accum) accum)) (let ((first (char str pos))) (if (eql first #\Tab) (read-item str (if tab (cons "" accum) accum) (1+ pos) t) (multiple-value-bind (item next) (read-from-string str nil :eof :start pos :preserve-whitespace t) (if (eql item :eof) (reverse (if tab (cons "" accum) accum)) (read-items str (cons item accum) next nil)))))))) (read-items line nil 0 t))) Now, to deal with a multi-line file, we just need to open the file and process records until we reach the end of the file. The following code will handle the LOINC data file available from Regenstrief and process it into a list of lists, one list per record, with each field a separate string in the list. Once again, we define an inner tail recursive function, this time called read-loinc-records, to process a record and check for end of file. If at the end, it returns the reverse of the accumulated records, and if not at the end, it adds the new record result to the accumulator list and recursively processes the rest of the file. The main function opens the file and calls read-loinc-records starting with an empty list as the accumulator. It is not quite that simple because the first record in a LOINC file is a list of column labels, so a separate call to parse-line gets that data, and then the parse-loinc function calls read-loinc-records. The result is a two-element list, the column headers and a list of the records.25 (defun parse-loinc (filename) (let ((n 0)) (labels ((read-loinc-records (strm accum) (let ((line (read-line strm nil :eof))) (format t "Reading record ˜A˜%" (incf n)) (if (eql line :eof) (reverse accum) (read-loinc-records strm (cons (parse-line line) accum)))))) (with-open-file (strm filename) (list (parse-line (read-line strm)) (read-loinc-records strm nil)))))) These two functions use tail recursion, so it should be possible for the compiler to generate very efficient code. Indeed, it turns out that compiling is necessary to avoid stack overflow. 25. The parse-loinc function here uses format, a Common Lisp facility for producing character (text) output to text streams, that is, a terminal window or a file. The first argument to format is the output stream, where t means *standard-output*, and nil means just return a string. The rest is a format control string and data for it. Rather than explain it here, the reader is referred to Graham [94, Chapter 2] and for a complete reference on formatted output, Steele [312, Chapter 22].

42

PART | I Foundations of Biomedical Informatics

The following is a convenience function for printing the LOINC data after it is processed into a big list. For each item in a LOINC record, this function prints the label for each field together with its value. In this representation, each record is a list of strings, and each field is a string delimited by double-quote characters, with the field name, an =, and the field value. Where the field value is a string, it is not further surrounded by double-quote characters, but just printed literally. Here what we want to do is take a function that will print a header label and an associated item, and iterate it over a list of header labels and a list of corresponding items. There are many ways to do this. One commonly used idiom is the idea of mapping. The mapcar function takes a function and some lists, and applies the function to items from each of the lists in turn, until it reaches the end. As it goes through, it accumulates the results of the function in a new list. Here instead of defining a named function and then using it in mapcar, we use a lambda expression, which is an anonymous function.26 (defun print-loinc-record (headers record) (mapcar #’(lambda (hdr item) (format nil "˜A = ˜A" hdr item)) headers record)) Figure 1.13 shows an excerpt of the contents of one record in the LOINC table of test names and descriptions, reformatted from the original file. This is exactly what is produced by print-loinc-record when applied to a single LOINC table entry. Some fields are blank because the LOINC system has not yet assigned a value, or for a particular test there is no relevant value for that field. Every LOINC test name is assigned a unique identifier, the LOINC_NUM field. It consists of a number, a hyphen, and a check digit. The COMPONENT field is part of the LOINC name for the test. This name consists of subfields separated by carat (ˆ) characters. This and the next five fields together comprise the complete LOINC name. The standard specifies that these fields are combined into a composite name by adjoining them with the colon (:) character, so none of them should contain the colon (:) character. The SHORTNAME field is provided for use in HL7 messages. The test described in Figure 1.13 is a common test for glucose blood level using a glucometer. A computer program that processes a message containing a test result labeled with the LOINC system can then look up information about that test from its label and have branching code also to decide how to display it. However, this is rarely useful or practical, not only because of the need to interface systems that do not use LOINC but also because of the lack of context. The test label by itself does not have sufficient information for the practitioner to interpret the result. Other information is needed, including the normal range limits, which may be institution- or population-specific as well as specific information about the patient, that may not be on the same display screen as the test result.

1.1.5 Medical Images The use of X-rays to obtain images of the internal structure of the human body has a venerable history, dating from the discovery of X-rays by Wilhelm Conrad Roentgen [272]. In recent years, the availability of small detectors for X-rays, and mathematical methods for computing 2D data from one-dimensional projections, has made possible the direct production of digital images by the CT scanner [114]. As detector technology advanced, it became possible to directly produce digital X-ray images that were previously done with planar sheets of film (computed radiography). Other kinds of digital imaging techniques as well were developed during this period, the last three decades of the 20th century. The repertoire of the modern radiology department now also includes MRI (Magnetic Resonance Imaging),

26. The special form, lambda, is used to tag a description of an anonymous function. The expression, #’(lambda (x) (* x x)), for example, is an unnamed function that takes one input and returns the result of multiplying it by itself. Anonymous functions can be used anywhere that named functions can be used.

Chapter | 1 Biomedical Data

43

("LOINC_NUM = 14743-9" "COMPONENT = Glucose" "PROPERTY = SCnc" "TIME_ASPCT = Pt" "SYSTEM = BldC" "SCALE_TYP = Qn" "METHOD_TYP = Glucometer" ... "CLASS = CHEM" "SOURCE = OMH" "DT_LAST_CH = 19980116" "CHNG_TYPE = ADD" ... "CLASSTYPE = 1" "FORMULA = " "SPECIES = " "EXMPL_ANSWERS = " "ACSSYM = CORN SUGAR, D GLUCOPYRANOSE, D GLUCOSE, D GLUCOSE, DEXTROSE, GLU, GRAPE SUGAR," ... "RelatedNames2 = Glu; Gluc; Glucoseur; Substance concentration; Level; Point in time; Random; Blood; Blood - capillary; Blood cap; Blood capillary; Bld cap; Bld capillary; cap blood; cap bld; Capillary bld; Capillary blood; Quantitative; QNT; Quant; Quan; Glucomtr; Chemistry" "SHORTNAME = Glucose BldC Glucomtr-sCnc" "ORDER_OBS = BOTH" ...) FIGURE 1.13 An except from a record in LOINC.

ultrasound imaging, PET (Positron Emission Tomography), and various kinds of nuclear isotope scans. A good introduction to the physical aspects of medical image production and processing is Hendee and Ritenour [108]. Digital images consist of two kinds of information. The most apparent is the image itself, consisting of an array of numbers, which can be integer or decimal. Each number represents a picture element or pixel. At that spot in the image, the display may show a monochrome brightness corresponding to the value of the number or a color with brightness, hue, and saturation qualities (or equivalently, a mixture of red, green, and blue intensities). The size of the array may vary for a given modality. For CT images, an array of 512 rows by 512 columns is common. The array may not be square; computed radiographs that correspond to chest films are typically portrait style, with more pixels in the vertical dimension than in the width, which corresponds to the typical viewport shape of an X-ray film. The second kind of information associated with a digital image is the descriptive data that specifies what kind of image it is, how it was obtained, who the subject (patient) is, where in some patient or machine-centric coordinate system the image is located, its orientation, and many other possibly useful items. These are encoded in many different ways. Further, images may be aggregated into sets, and the set of images may have its own attributes, which apply in common to all the images. One very important concept is that of a position-related set, where all the images share the same coordinate system, and are oriented and located in that coordinate system, relative to each other. This allows the possibility that the set of 2D images can be reformatted

44

PART | I Foundations of Biomedical Informatics

FIGURE 1.14 A CT image of a person’s head, showing the cerebellum, sinus cavities, and nose.

to provide 2D images in other planes through the volume that the set represents. The images can be coalesced or interpolated to form a regular 3D array of image data. Solid models or surfaces that represent the 3D structures seen in cross-section in the images can then be computed from it. The advent of X-ray transaxial CT scanners in the 1970s marked the beginning of the digital era of medical radiology. The first scanners produced transverse cross-sectional images of heads, an example of which is in Figure 1.14. These images are produced by projecting a very thin “fan” X-ray beam through a patient’s head, from each of many angles. The transmitted X-ray intensities are measured by photon (X-ray) detectors on the opposite side of the patient from the X-ray tube. Each intensity is related approximately to the integral of the X-ray linear attenuation coefficients of the tissues along the line from the X-ray source to the detector. The attenuation coefficients are in turn related to the tissue densities since the attenuation of the X-rays is mostly due to Compton scattering, which depends only on the electron density, not on the composition of the tissue. The image data, or, equivalently, the tissue densities can be reconstructed from the projected data, using a method called filtered back-projection. This method relies on a property of the Fourier transform called the projection-slice theorem, which relates the one-dimensional Fourier transform of the line integral data mentioned above to the 2D Fourier transform of the original function. So, if you can measure the projections in all directions, you can recover the original function. For a detailed discussion, see [108, 269]. The first person to demonstrate the effectiveness of this idea as a practical medical device was Geoffrey Hounsfield [114] for which he was awarded the Nobel Prize. Hounsfield’s research and development was supported by EMI, the same company that produced and marketed the first commercial CT scanner. This company was also the publisher of the music of The Beatles. It has been noted27 27. In a presentation by Dr Ben Timmis, Consultant Radiologist at the Whittington Hospital, in the UK; see URL http://www. whittington.nhs.uk/default.asp?c=2804.

Chapter | 1 Biomedical Data

45

FIGURE 1.15 A sagittal cross-section through the midline of the same person, constructed from a series of 80 transverse images.

that the CT scanner is the Beatles’ greatest legacy since Hounsfield’s work was funded by EMI’s profits from the Beatles’ phenomenal record sales. The images are 2D arrays of numbers representing the image intensity; the spots in the image that the numbers represent are called pixels (for “picture elements”). In a typical CT image, each pixel may represent a 1 to 2 mm square cross-sectional region. The image pixel numbers represent average tissue densities over some thickness (in the direction perpendicular to the image), roughly the width of the fan-shaped X-ray beam used to produce the data from which the image is computed. This width is called the slice thickness. When the slice thickness is large, it will be difficult to detect small spots, as they will be averaged with the surrounding tissue and not stand out so much in contrast. As the ability to produce images with thinner and thinner X-ray beams developed, it became possible to get high resolution in the direction perpendicular to the image plane, and this made it possible to construct images in orthogonal planes from the transverse images by selecting pixels from a series of transverse images as if they were stacked into a 3D array and reorganizing them for display. Figure 1.15 shows a sagittal cross-sectional image constructed in this way.28 Later in this section, we will develop the explicit code for this. In order to properly display the image data, a computer program needs substantial information about the image pixel array and the image it represents. This includes such things as the dimensions of the array (how many pixels are in a row, how many rows are in the image), and what the image pixel numbers represent (what numbers should correspond to maximum brightness, where should the midrange be, etc.). To reorganize the transverse image data into sagittal images like the one shown, it is also necessary to know the table index of each image so that the pixels from that image can be placed properly along the perpendicular axis. In the image shown, the successive transverse images are about 5 mm apart, but the pixels represent spots about 1.5 mm in size, so the pixels are replicated

28. This image set is rather old and does not represent the kind of resolution achievable today.

46

PART | I Foundations of Biomedical Informatics

FIGURE 1.16 A lung cross-section with window and level set to show some details of lung tissue. With the right settings and careful comparision between adjacent images, it is possible to detect very small lesions as distinct from bronchial trees and blood vessels.

to form strips, representing the thickness of the X-ray beam (which usually but not always corresponds to the inter-image spacing). Other information that is important of course is the name of the patient and other identifying information, as well as the reason for getting the images. Different techniques will be used (e.g., different X-ray tube voltages and use of intravenous contrast) depending on whether the problem is to look for signs of pneumonia or small lesions that might be tumors or evidence of a broken bone. The array of numbers has a wide dynamic range, with much more granularity than can be discerned by the human eye as gray intensities. Image display programs include facilities for the user to control how the image data are converted or mapped into gray levels displayed on the screen. The two most common controls are called window and level. The level setting is the pixel number that will be displayed as a half-intensity gray spot. The window specifies the range of pixel values that are mapped from black to full white. For example, a window of 400 and a level of 1100 will show all pixels below 900 as black, all above 1300 as white, and everything between will be displayed proportionally at intermediate gray levels. To see details in the lungs, the lower range, near 0, should be in the gray range, as in Figure 1.16, while to visualize bone details, the level must be set somewhat higher since bone pixel values are more in the range from 1500 on up. One use of cross-sectional images is to construct organ models and identify tumor locations for radiation therapy planning (RTP) (see Chapter 9 for more on this). Much work has been done on image processing algorithms to automate the process of finding organ boundaries so that 3D models can be constructed. Figure 1.17 shows a cross-section of an abdomen, where the patient’s left kidney can easily be identified (the view is from feet to head, and the patient is on his/her back, so the patient’s left is to your right). However, the boundary between the right kidney and the liver is very blurred as the two organs are very close in density at the points where they touch. The current state of practice in radiation therapy today is a combination of automatic and manual techniques, with much research remaining to be done.

Chapter | 1 Biomedical Data

47

FIGURE 1.17 A cross-section of a patient’s abdomen, showing the left kidney pretty clearly (on your right), while the liver and right kidney appear fused as if they were a continuous entity. The vertebral column is plainly visible at the bottom center as well as the stomach on the patient’s left side, shown half full of contrast material. The small bright spots in the upper middle of the image are metal surgical clips that were put in during surgical removal of a large tumor.

Typically, the image pixel values are represented in files and in computer programs directly as binary numbers, not as text. This saves space and is also important because image processing algorithms do arithmetic on these data. Later in this chapter, we will show how image data can be represented in files and programs and read in (and written out) efficiently. Radiology departments today are almost completely filmless. The development of high-resolution X-ray detector arrays has made digital radiography (DR) a reality. In addition, many other digital imaging systems are part of the standard of practice, including ultrasound, MRI, and various systems using radioisotopes, such as PET. Although it is not possible to give even a short survey here, we will delve a little into the question of representation and manipulation of image data in computer programs, using CT images as an example. The image pixel values for a CT image are typically small integers in the range from 0 to 4095 or sometimes larger up to 65,535 (i.e., they can be represented in 12-bit or 16-bit binary words). A typical image consists of a 512 row by 512 column 2D array of such numbers. A simple way to encode these is as nested lists of lists, that is, a list of numbers for each row of pixels and a list of such lists for all the rows of an image. Columns correspond to the individual elements of the row lists. > (setq image-5 ’((0 0 5 6 0 3 678 737 929 ...) (0 0 0 4 3 2 734 456 ...) ...)) ((0 0 5 6 0 3 678 737 929 ...) (0 0 0 4 3 2 734 456 ...) ...) One could use the elt function described earlier to access any pixel. To get the pixel value at column 233, row 256, we would use elt twice in nested expressions. > (elt (elt image-5 256) 233) 1037

48

PART | I Foundations of Biomedical Informatics

We could even create abstraction layers by writing named functions and hiding the fact that these arrays are implemented with nested lists. However, access to arbitrary elements of lists is very slow. In effect, to get to the 233rd element of a list, you have to look up the rest part of each cons cell, following the chain until the right place. Since computer memories are actually arrays and organized so that each location is directly addressable, it would make sense to have a more efficient way to represent arrays. Of course there is, and Common Lisp has a built-in data type, the array, which can be constructed to take advantage of the computer’s direct addressing and give very high speed of access. Most programming languages have this kind of facility since many other kinds of data besides images also take this form. An array is constructed by the function make-array, which just requires that you specify the size (dimensions) of the array. To create an array which we can fill with image pixel values, we would specify two dimensions, each of size 512. > (setq image-5 (make-array ’(512 512))) #2A((NIL NIL NIL ...) (NIL NIL NIL ...) ...) Since we did not specify the initial values for the array elements, they are all set to nil. To look up a value in an array, the function aref is used. It needs the array and the index values, as many as there are dimensions of the array. So, to do the same lookup as before, we have > (aref image-5 233 256) NIL Of course we get nil this time, because we have not set any values. To set a value in the array, you combine aref with the setf macro. Although we have mainly used setf to attach values to symbols, it is really a general purpose assignment operator. Its inputs are an expression naming a place that can have a value and a value to put there. So, to set the pixel (233, 256) to the value 1037, we evaluate the following expression: > (setf (aref image-5 233 256) 1037) 1037 Now, that value is stored in that place in the array. Now, we consider the construction of the sagittal image in Figure 1.15. Suppose we have a list of transverse images that is the value of a variable, image-list. We want to pick out the 256th column of each transverse image and make it a column in a new image array. We will need to iterate over the list, with dolist, and we will need to iterate over the rows in each image, picking out the 256th pixel from every row and making it a column value in the sagittal image. The dotimes function is similar to dolist. It takes a local variable, the index variable, starts it at 0 and evaluates the body of the dotimes expression, then increments the index by 1 each time through until it reaches the end or stop value. We also need to keep a count of how many columns in we are, which is the same in this simple example as how many images we have processed. (defun make-sagittal-image (image-list) (let ((new-img (make-array ’(512 512))) (image-num 0)) (dolist (image image-list) (dotimes (i 512) (setf (aref new-img i image-num) (aref image i 256))) (incf image-num)) new-img))

Chapter | 1 Biomedical Data

49

The order of indexing in aref for 2D arrays can be thought of as row index first and then column index. It really does not matter which you choose, as long as you are consistent throughout your program.29 The code above assumes that each image in image-list is only one pixel thick, otherwise the proportions of the sagittal image will not be square. It is left as an exercise to solve the problem of thick transverse images. In this case, one needs an additional parameter, the thickness, or spacing (in pixels) of the transverse images. You would use this parameter to determine how many identical columns of pixels must correspond to a single column from the transverse image set, for example if the pixels were 1 mm square, and the slice thickness 5 mm, each column computed must have four adjacent copies, for a total of five, to make the image proportions right. Real image data sets include the spatial sizes in actual patient space, in mm or cm, for all the data, so you must also be able to keep track of conversion between pixel numbers and positions in real space. Arrays are the right way to represent the mapping of the pixel numbers to gray levels, too, as mentioned earlier. In a typical computer display system, there are no more than 256 gray levels though we indicated earlier that the image pixels can range over much larger values. The window and level mapping described earlier is also a relatively straightforward operation on an image array. We take a single image array as input, along with a window and a level, and create a new array with values in the reduced range of 0 to 255. The way we will do this is to create a short mapping array of a specified number of elements (called range-top here, either 4095 or 65535, or perhaps some other upper limit), and each entry in this array will be the gray value for that pixel value. Then, to get the gray value for a given pixel value, we just look it up in the map array.30 (defun make-graymap (window level range-top) (let* ((map (make-array (1+ range-top))) (low-end (- level (truncate (/ window 2)))) (high-end (+ low-end window))) (do ((i 0 (1+ i))) ((= i low-end)) (setf (aref map i) 0)) ;; black (do ((i low-end (1+ i))) ((= i high-end)) (setf (aref map i) (round (/ (* 255 (- i low-end)) window)))) (do ((i high-end (1+ i))) ((> i range-top)) (setf (aref map i) 255)) map)) The low-end variable is the value below which all pixels will be displayed as black, and the high-end variable is the value above which all pixels will be white. So, up to the low-end location in the map array, the values will all be 0; from low-end to high-end, they will be proportional, up to 255; and from high-end to the end of the map array, the values will all be 255. This code uses a more general iteration, the do macro, because we are not always starting from 0, so dotimes is too simple. The do macro creates any number of local variables (here, we are just using one, i), gives them initial values, and then assigns them new values each time through the iteration. 29. In terms of efficiency, when optimizing the code for high performance, one would actually consider which index will be varying most, that is, if you are iterating over both indices. Optimization is a complex subject and is discussed in more detail in Section A.1.3 of Appendix A. 30. Note that let* is like let except that it initializes the variables sequentially instead of in parallel so that you can refer to a variable in the initialization expression of a variable that comes after it. In this case, we are initializing high-end by using the initial value of low-end.

50

PART | I Foundations of Biomedical Informatics

The execution terminates when the test expression is satisfied, which is in a list following the local variable forms. Now that we can make a map array for any value of window and level, we can use the map to convert an image to a mapped image. This is simple. Just iterate through every pixel, making the new image pixel value be the entry in the map array whose index is the value of the original pixel. So, if the value in the image pixel is 1246, the new image will have the value in the 1246th location of map, which will be a number between 0 and 255. (defun map-image (raw-image window level range) (let* ((x-dim (array-dimension raw-image 1)) (y-dim (array-dimension raw-image 0)) (new-image (make-array (list y-dim x-dim))) (map (make-graymap window level range))) (dotimes (i y-dim) (dotimes (j x-dim) (setf (aref new-image i j) (aref map (aref raw-image i j))))) new-image)) We are using the number that aref looks up in raw-image as an index for the aref that looks up a value in map. It is simple and can be made to run very fast.31 There is one new generalization in the above code. In make-sagittal-image, we explicitly did arrays of dimension 512 by 512 (and computed the sagittal image through the midline of the transverse images), but here, we arranged to handle arrays of any dimension. The array-dimension function will look up the dimensions of an array, so we can write code that handles arbitrary sizes. The dimensions are indexed starting at 0, up to a maximum limit depending on your Lisp system, but in no case less than 7, that is, you can be sure to have support for up to seven-dimensional arrays, and each dimension can have a large number of elements, also implementation dependent. Later, in this chapter, we will show how to store image data in files and retrieve it as part of a very general method for serializing medical and other kinds of data. In Chapter 8, you will see how to send and receive image data over a network connection using the DICOM protocol, and in Chapter 9, there is a little more discussion of the uses of image data in RTP.

1.1.6 Metadata In the previous sections, we showed several ways to organize biomedical data, including the use of tags to label items and the use of structure to organize data. Although the tag representation seems appealing and is easy for a person to read and understand, the tags have no particular meaning to a computer program. Data are meaningful only when accompanied by some interpretation that defines what the symbols mean. While this may seem obvious, it is easy to overlook in the rush to create repositories of “self-describing data.” For example, what does the following list of numbers mean? 5984107 8278719 2214646 8220013 5433362 31. Actually, the code here will not be fast unless some optimizations are included. However, once you have written code you are sure is correct, it is easy to make it run fast. It is much harder to do this in reverse, that is, to write very fast but broken code, and expect to fix it later to run correctly. In Section A.1.2 of Appendix A we show how to optimize this code as well as use optimization techniques more generally.

Chapter | 1 Biomedical Data

51

4274566 ... Are they telephone numbers? Perhaps they are patient identification numbers assigned by a hospital. They might also be identification numbers assigned to terms in a terminology system such as GO (see Chapter 5) or the FMA (see Chapter 6). They could equally well be a series of pixel values in a medical image, a microscope image, a packed, encoded representation of expression array data, or a very compact encoding of laboratory test data. Some conventions are needed as well as labeling to clearly identify the meaning.

Tags as Metadata The description, interpretation, or identification of the meaning of a particular set of data can take many forms. The data set above may be accompanied by a written document specifying the meaning and format of the data. Another approach is to include with the data some identifying tags that label the elements, so-called self-describing data. Here is how the numbers above might appear using such a scheme: 5984107 8278719 2214646 8220013 5433362 4274566 ... Now, we can see that indeed they are telephone numbers, and they are organized so that numbers belonging to a single person or entity are grouped together. Of course, there must be some agreement as to the meaning of the tags, which is still outside the context of the data and tags. The words “phone numbers” and the other tags have no intrinsic meaning to a computer program. This idea of grouping items and providing tags is such a powerful way to organize information that an internationally popular (and rather complicated) syntax called XML was invented to support the idea. We will deal with it later in the chapter, in Section 1.3. The XML standard provides two methods for specifying the structure of the data labeled by a tag, XML data type definitions (DTD) and XML Schemas. One might then say, “We just include schemas or DTD that define the meaning of the tags.” Such schemas do not define the meaning of the tags. These only define the allowed or expected syntax or structure of the data. A computer program can use a schema or other such “metadata” to check if a document or data structure is correctly constructed, but it cannot discern what to do with the data. In any case, there must be some external document describing the agreement on the meaning of the elements of the data type description language. And so it goes. There is always some boundary beyond which a separate documented agreement about meaning must exist. The ongoing debate about self-describing data is not about whether data should be self-describing (which is impossible), but about where this boundary will be, and what description languages will be created for use inside the boundary (and documented outside the boundary).

52

PART | I Foundations of Biomedical Informatics

In order for a computer program to process the data, the program itself must recognize the tags, so the meaning of each tag (at some level) is encoded in the program. Using human readable tags can mislead the person unfamiliar with how computer programs work. A computer program does not understand the meaning of the phrase “phone numbers.” It can be written to take some particular action when it encounters that text string as a piece of data, but the way it recognizes the tag is by comparing with some other information containing the tag. So, a computer program is also in a sense a data description. The designer(s) of such systems and data repositories will have to choose how this matter is addressed. Computer programs are notoriously intolerant of misspellings or other variations. A slight change in the tag creates an entirely different distinct tag. Humans have the ability to handle variant words and phrases, but, in general, computer programs do not. If the tag read “phone number” (with the “s” left out), a program written to process the tags used above would likely break. A program can be written to handle a range of such variations, but that too must be completely and precisely specified, and the resulting more sophisticated program will also have brittle boundaries.32

Source Code as Metadata The data that describe the tags, that is, how their associated data elements should be used, what are the allowable value types, etc., are called “metadata,” that is, data about data. Similarly, if a record structure is defined without tags, in which the data follow some fixed conventions for format and encoding, as in DNA and protein sequence data, there may still be metadata. In a relational database, the kind of data stored in each field of a record is specified by a statement in the standard relational database language, SQL.33 This SQL statement also is a piece of metadata. The distinction is important in designing systems. One can design a system that has a high level of generality by making the system use the metadata as a guide to how to handle the data. This idea makes a database system possible – you write a description of your data in SQL, and the database system interprets the SQL to facilitate entry, storage, and retrieval of your data, using the tags you specified. The use of structured data types in ordinary programming languages is an even more generalized version of the same thing. However, in this case, we are referring to parts of the program itself as metadata although normally we think of structure definitions as code. The distinction between code and data in a program is not always as one conventionally learns in introductory C or java programming. The code that defines structures in a program becomes metadata when the program can actually use it explicitly during execution. The possibility that a piece of code in a computer program can itself be metadata is very important, as we will see later in this chapter.

Data, not Variables, Have Types In a conventional programming language, data items are stored in memory locations associated with variables. The variables are declared to have values of certain types, and the storage allocated for each variable’s value is associated with that type, perhaps something like four bytes for integers, one byte for each character in a string, etc. When your program runs, it must have the right instructions to process these bytes because the bytes themselves have no information about what type of data they represent. Sometimes, a program has errors in it or data get brought into a running program that are ill-formed, and a mysterious malfunction occurs. For example, a floating point arithmetic instruction attempts to 32. An impressive early step in the direction of expanding the boundary and making programs able to be self-correcting is the DWIM facility for Interlisp, an earlier version of Lisp designed by Warren Teitelman when he was at the XEROX Palo Alto Research Center. The DWIM facility, when it encountered a name for which a function definition was needed but absent, would look through the symbols to see if there was one that might be the right one, that is, it could guess how to fix spelling errors and some other problems. Some of DWIM’s fixes were a bit arcane, and the facility was sometimes described as “Do what Warren, not I, would Mean.” 33. Later, in this chapter, we introduce the Relational Model, relational databases, SQL, and related ideas.

Chapter | 1 Biomedical Data

53

operate on a 4-byte sequence that is not a valid floating point number but was a valid integer. The error message generated by the system will be quite obscure. The 4 bytes do not have information saying they are an integer instead, and a C program would not use such information anyway. In this example, the program can signal an error because some binary numbers are not valid floating point numbers. In a worse scenario, the data are simply mistaken for the wrong type, just processed without notice, and a very inappropriate result is obtained, without any idea why the strange results happened. Manifestations could be things like garbled text appearing in a display of patient data, a graph having strange anomalies, or colors coming out wrong. Alternately, the internal binary representation of data in a running program could carry with each piece of data a (binary) tag, identifying its type. The running program could then use these tags to determine what to do with the data. It makes possible the idea of “run-time dispatch,” that is, an operator can have many different implementations, one for each type of input it might receive. When it executes, it checks the type of the data and chooses the right method for that type of data. For functions with multiple inputs, there could be methods for all the combinations of different types for each of the inputs. Such functions are called generic functions because their source code is organized to perform a generic operation but with different details depending on what kind of data are input. In a system like Lisp, where data have types associated with them, we can still have variables. Symbols can serve as variables because they can have values or data items associated with them. However, the value that a symbol is assigned can be any type. All the symbol does in this context is hold a pointer to the actual data item. Symbols can even have values that are other symbols, as we have seen, and of course in that case, the type of such a datum is symbol. A system where the data themselves carry type is the basis for key ideas of object-oriented programming. The association of types with data is consistent with the idea of a type hierarchy, with general types, subtypes, sub-subtypes, etc. The specialized types inherit the properties associated with their parent types. A generic function method applicable to a type will also be applicable to all its subtypes. You will note that we have not said anything about classes here. The ideas of object-oriented programming depend on having type hierarchies and user-definable types that extend the type hierarchy. The role of the idea of classes is that classes are a way to implement user-defined complex types with component parts. Finally, you might be wondering if this handling of type information in a running program is very inefficient. It is, so implementations have ways to cache information and generally optimize the operations to make the efficiency higher. In general, this is adequate, and the additional computation time is not going to be noticeable, but the savings in ease of writing the programs is often enormous. In those rare cases where performance is extremely important, a good object-oriented programming language provides type declaration capabilities to help the compiler do an even better job of generating efficient code. This is discussed in more detail in Section A.1.2 of Appendix A.

1.2 OBJECTS, METADATA, AND SERIALIZATION The code we develop in this section will show how to store (in files) and represent (in a program) patient data that might be found in a typical electronic medical record system. The examples use text files for external storage and tags (also called “keywords”) to label the data items. The patient example developed here is simple and unconventional, but it illustrates some ideas that can help to manage complexity. Many electronic medical record (EMR) systems are built on relational database technology. The conventional wisdom is that a relational database is currently the most efficient, scalable architecture. However, the complexity of medical data suggests that the relational model may not the best fit. The challenge is to be able to store and retrieve heterogeneous collections of data that have highly variable structure. Although the implementations we show here might be hard to scale up, they illustrate important ideas which can guide a more scalable design. Later, in this chapter, we will also examine the relational model to see how it compares with these methods.

54

PART | I Foundations of Biomedical Informatics

Three methods will be developed to show how structured data may be encoded and manipulated. The first is a simple arrangement of tagged data, where the structure of a complex record is represented by hierarchical grouping of items in nested lists. The second method, using standard object-oriented programming ideas, shows how the class definition facilities of typical object-oriented programming languages provide the abstraction layers that had to be done explicitly in the first method. The third method, using meta-objects, shows how you can use the implementation of the object-oriented system itself to write even more abstract (and therefore more powerful and general) procedures and programs. In this chapter, we are representing and manipulating data, but the structures that describe the data could well be argued to be a representation of some knowledge about the data. Later, in this chapter (Section 1.3), we will introduce the syntax and semantics of XML, which provide methods and vocabulary for tagging data and representing structure in a standard way. In Chapter 2, we introduce RDF (Resource Description Framework) and OWL (Web Ontology Language), which use XML syntax along with some standard tags that represent some forms of knowledge, such as the idea of classes and logical relations between classes. These are important because, like the examples we develop in the next sections, they use plain text (e.g., ASCII) and thus are a means for encoding data and knowledge for export and import from one system to another. Further, the syntax of XML has become very popular, so there is now a large code base of programs that implement XML generators and parsers. We will illustrate the use of such code to store and retrieve information from such external formats.

1.2.1 A Simple Solution Using Tags (Keywords) Patient data are a good match to hierarchical representation, where structures include elements which themselves have structure. Using symbols, strings, numbers, and lists, we can organize information about a patient in terms of keyword–value pairs. (Here, we are using “keyword” to mean the tag that labels a datum, which could itself be structured as a list of tagged elements, etc.) Here is an example of an information record on a single patient. (patient (name "John Q. Smith") (hospital-id "123-45-6789") (age 72) (address (number 211) (street "Willow Street") (city "Browntown") (zip-code 90210)) (diagnosis (name "prostate cancer")) (lab-tests (psa (("23-Aug-2003" 4.6) ("12-Mar-2004" 7.8)))) ...) This keyword–value representation is easy for a person to read, especially with the indentations. The indentations and line breaks have no impact on the logical structure. Neither does the amount of space between items (though at least one space character is needed, it does not matter how many there are). The extra “whitespace” is simply to make the data more easily human readable. Although earlier we mentioned XML as a syntax for defining tags and structure, it is complex. Parentheses and symbols are much simpler to read and much simpler to process in a computer program and will suffice for now. For this simple example, we represent all the data as text in a file consisting of nothing but printable characters. If the data above appeared in a text file, a single call to the Common Lisp read function would return a list structure exactly as shown, which could be examined by a computer program, by standard list operations, for example first and rest. Rather than having to define data structures and access

Chapter | 1 Biomedical Data

55

methods, and then decode and parse the input to assign the values to the right places in the data structures, the above text representation is already a valid representation of a Lisp data structure. This format takes advantage of the fact that the Lisp reader and printer can do some of the work for us. All elementary Lisp data types have well-defined external or printed representations, even including user-defined structured types (defined with defstruct) and arrays. For reading and writing these simple data types from/to files, we can just use read and print. We do not need to do any lexical analysis of the text on input or pay much attention to formatting on output (though some formatting would enhance human readability of the data). However, writing a program to manipulate the above structure could get tedious. Some work would be involved in creating abstraction layers so that the code that works with data elements goes through accessor functions, for example, to get the diagnosis, we would define an accessor, named diagnosis. (defun diagnosis (patient-data) (find ’diagnosis (rest patient-data) :key #’first)) and similarly for each of the other fields and subfields. Like the Swiss-Prot files and other keyword labeled records, this scheme has the advantage that records do not need to have uniform structure, and so the structure does not need to be predefined. This is workable if we impose some restrictions on the structure of the data, that is, that certain items are always found at the top level of the list of data for the patient. Additional assumptions or restrictions must be made about items that themselves have structure. A disadvantage of this approach is that changing the structure of the data, perhaps by adding another field or subfield, could require changing many of the accessors. However, it confines the problem to rewriting the accessors, not rewriting explicit code scattered throughout a large program. The design of such abstraction layers comes up in so many software systems that it seems reasonable to build an abstraction layer for support of abstraction layers. What this means is to have some functions or operators that can create the abstraction implementations without you, the programmer, being concerned about how the implementation actually works. This is just an extension of the idea of a high-level programming language like Lisp. A high-level programming language is a way to describe your computations without being concerned about how the abstractions actually translate into binary numbers that represent basic computing machine operations. To create these structure abstractions, many programming languages provide a way for you to define your own structured types. So-called object-oriented programming languages (including Lisp) go further and provide yet higher level entities called classes. In the next section, we show how this works in the Common Lisp Object System (CLOS), and then how you can effectively use the metadata of CLOS to write structured data to files and read it back to reconstruct equivalent instances in programs.

1.2.2 An Object-oriented Design In using a simple scheme with tags, we had to write lots of accessor functions and also keep in mind some definition of the structure of the patient record. This work will be required for each kind of structure we introduce into our medical record system. An object-oriented programming language provides a standardized collection of syntax and semantics that make this work much easier. We can write definitional expressions that specify the structure and the names of the accessors, and the object-oriented programming environment automatically generates the support code. In effect, we are creating an abstract model of medical information about patients, and letting the modeling system translate the formal model into lower level code. When the model changes, the program need not change except to accomodate the specific additions or deletions. Aggregated data units become, in a typical object-oriented programming language, instances of classes, whose definitions represent the model implemented in an actual program. Figure 1.18 is an example of a part of an object-oriented model for patient information. The figure uses a notation called entity-relationship (ER) modeling. Each box in the figure represents a class specification, including the class name and the names of the attributes of that class. Each instance of a class can have different values assigned to

56

PART | I Foundations of Biomedical Informatics

schedule-entry date participants location appointment-type icd-code cpt-codes ...

patient name addr ... diagnoses follow-ups bills

provider name main-clinic other-cl. ...

follow-up entry-date primary ...

diagnosis

billing-item origin maker cpt-code ...

t-code m-code ... FIGURE 1.18 An entity-relationship model for a subset of patient data.

the attributes. The lines connecting the boxes represent relationships between classes, indicating that one class is a subclass of another or that an attribute of one class can have values that are instances of another class. The connections between the boxes represent the typical kinds of relationships found in objectoriented models. A more thorough discussion of object-oriented design may be found in [283]. The model can be implemented with a set of class definitions. For each box, we have a class, and we implement families of classes using inheritance. In such families, some classes are defined directly as subclasses, or specializations, of a parent class. Thus, in the patient data model, the patient entity and the provider entity could each be defined as a subclass of a more general entity, person. As a first try, we use structures as a simple version of the idea of user-defined types. For each entity, we define a structure type. The defstruct macro creates structure definitions. Its inputs are the name of the structure type, a list of possible “supertypes” of which this structure will be a subtype, and then the names of the slots that will appear in any instance of the structure type. The idea is that each instance will have these named slots, or fields, to which values can be attached. Such user-defined structures are a way to create complex objects with attributes (the slot values) and treat each such object as a single entity. (defstruct person () name birthdate telephone email ...) The defstruct macro does more than just record a definition for the structure. It also creates several new functions and adds them to the working environment of the program. These functions are as follows: ●

A constructor function that can be called to create a new instance of the structure. By default, it is called make- where is the name you specified. In the above example, the constructor function will be called make-person.

Chapter | 1 Biomedical Data

●

●

57

Accessor functions for the slots, each named with a prefix using the structure name; in the above example, the accessors will be person-name, person-birthdate, etc. There will also be setf methods so that expressions like (setf (person-email x) ), where x is a person instance, will also work. And others (see Graham [94], Chapter 4, Section 4.6 for details).

Instead of just specifying the name of the new structure type, you can specify that this structure is a subtype of another (already defined) structure. This is done by making the structure name into a list, with an :include option, naming the parent structure type. Here are examples. (defstruct (patient (:include person)) diagnosis appointments ...) (defstruct (provider (:include person)) specialty title office patients ...) Specifying that patient and provider are subtypes of person will automatically make any slot defined in the person type also be present in both the patient type and the provider type. This is one aspect of inheritance. These specializations also add their own slots to the inherited ones. Similarly, any accessors for person are inherited and applicable to both subtypes. Here are some example functions that might be made available through some user interface in an EMR. Although in a real system, one would store records in some kind of database; here, we just keep a list of patient structures in a global variable, *patients*, and similarly a list of providers in a global variable, *providers*. (defvar *patients*) (defvar *providers*) The add-provider function adds a new physician, nurse practitioner, or other patient care provider, given this person’s name, specialty, and title. The other information would be updated later. (defun add-provider (name specialty title) (push (make-provider :name name :specialty specialty :title title) *providers*)) Here is how one might look up the specialty of a provider, given the name. The find function does the lookup, using the person-name function as a lookup key. This function is applicable since a provider is also a person. Note that the accessor for specialty is provider-specialty, not person-specialty, since that slot is particular to the provider structure type. (defun lookup-specialty (name) (provider-specialty (find name *providers* :key #’person-name :test #’string-equal))) Here is how updates can be done to any field in a structure. Once again, we use a lookup key function, and this time we can also use the more general person-telephone accessor since the telephone field is defined in the person structure; however, we have a specific function for patients (and would need a separate function for providers) since we need to know in which list to look. The name by itself does not specify which kind of record. One cannot just look in both lists since a provider can also be a patient at the same institution, so it is best to keep separate records for these roles.

58

PART | I Foundations of Biomedical Informatics

(defun update-patient-phone (name phone) (let ((record (find name *patients* :key #’person-name :test #’string-equal))) (setf (person-telephone record) phone))) Inheritance in relation to the type/subtype relationship provides a way to build a program system incrementally and reliably. Adding the subtypes takes advantage of all the support code that is already written for the parent types and does not in any way impact or require revision of code that supports the parent types. This “code reuse” has been one of the most attractive aspects of “object-oriented programming.” The idea is not without its problems and limitations. In an electronic medical record system that supports appointment scheduling and billing as well as recording clinical data, the provider class might have a slot for a list of patient instances, the provider’s patients. The model is complex because a patient typically has a relation to multiple providers and vice versa. In principle, one only needs to represent one relation and the other can be computed, but this would be very inefficient for a large hospital or clinic. For efficiency, redundant references should be maintained in the system. However, this makes updating entries more complex because the redundant information has to be kept consistent. For example, when a patient sees a new provider, multiple modifications are made to the patient record and to the provider record. Similarly, when a relationship ends, the relevant information should be removed everywhere, so the system has to have code to do the removal in all the redundant locations. What is really needed is a transaction system layered on this structure model so that the entire history of relationships can be recorded somehow. This does not really solve the problem of what the currently valid relationships are, but it is necessary to meet requirements for record keeping in a medical setting. Managing this kind of complexity is a big challenge for system designers as it requires the implementation of consistency constraints and results in a system that is no longer made of relatively independent parts. Designing such systems involves considering the trade-offs among simplicity, reliability, efficiency, and ease of use. Structured types have been a part of many programming languages, including Pascal [140], C [170], and their successors. They do not implement the full capabilities of classes. The idea of classes is to extend data type ideas even further in abstraction. A significant difference between structures and classes is that structures provide an efficient but very restricted system for defining slots, accessors for slots (functions that return and set the slot values), and other properties of each structure, but classes provide a much wider range of possibilities. In particular, the accessor for a slot is named uniquely for each structured type, even if the slot has the same or a related meaning for different structures. We may have several kinds of things in our program, each part of a human body, and each is a structure, for example, heart, kidney, tumor, etc. Each will have a location (of its center, perhaps), specified by coordinates x, y, and z. (defstruct heart () size beat-rate x y z ...) (defstruct kidney () side x y z ...) (defstruct tumor () size grade tissue-type x y z) The accessors, however, will be named differently, that is, heart-x, kidney-x, tumor-x because the storage arrangement for each may differ, and there has to be some way to distinguish what to do in each case. So, you have to write different codes for each type to get and store the data.

Chapter | 1 Biomedical Data

59

One might think that defining a parent or base type with these shared slots would solve this problem. First, it becomes a design nightmare because any time you use a name, you would need to check to see if it is defined in some base type, before defining a duplicate base type. Moreover, structures are limited to single inheritance, that is, a structure type can have no more than one parent type. So, it is not possible to use such base types to solve the problem when the shared slots are not the same set in every case. In Common Lisp, classes provide a nicer way to handle this problem.

Object-oriented Programming in Lisp Implementation of an object-oriented design can be done with most any programming language [127, 129], but the work is facilitated by using a programming language with the right abstractions already built-in. The essential abstractions are the generalization of types to include abstract (or structured) data types (including user-defined types) that have attributes, the idea of inheritance or specialization of types, and the idea of type-based dispatch in implementing functions or procedures. Usually, the idea of having different blocks of code to execute for different types of inputs is described by saying that functions are implemented as collections of methods, where a particular method is associated with a particular type of input (or inputs). Here, we provide a brief introduction to these ideas as implemented in CLOS. A concise introduction to the basic ideas of CLOS may also be found in Graham [94, Chapter 11]. A more complete and detailed discussion is in Steele [312, Chapter 28]. Types, Structures, and Classes Every programming language provides some way to represent types. A type definition specifies what kinds of values a variable or entity of that type may have. The types that are supported by most all programming languages include numbers of various sorts, characters, and strings (sequences of characters). More complex types, such as arrays, enumerated types, and user-defined structures are supported by many programming languages. Lisp is distinguished by supporting symbols, lists, and functions as built-in types, in addition. Numbers are usually subdivided into subtypes, such as integer, rational, float, complex, etc. There is no need in Lisp for what are called “enumerated types” in other languages, where one defines a sequence of names to be allowed values of a type. An example of this would be to define the names of colors as forming an enumerated type called “color.” In Lisp, we would just use symbols naming the colors, and there would be no need for a statement defining them. In Lisp, the types are arranged in a type hierarchy so that any datum belongs to the overall type, Lisp object, sometimes referred to as type t and may belong to a series of successively more specialized types. For example, the number whose text representation is 3.14159 is of type single-float, which is a subclass of float, which is a subclass of real, which is a subclass of number, which (finally) is a subclass of t. Similarly, in Lisp, strings are implemented as character vectors; thus, the string type is a subclass of vector, which is a subclass of array, which is a subclass of t. The hierarchy of types is important for defining inheritance and for dealing with function dispatch. User-defined types are created using either defstruct or defclass. We have already seen examples of how defstruct creates structure types, and they become a part of the type hierarchy just as if they were built-in. Similarly, defclass creates user-defined classes, which also become part of the type hierarchy. Each of these facilities provides a way to create a “record-like” structure, in which a datum contains named components, called slots, each of which can be referred to by name, rather than relying on the position of the component in an array. A structured type may have different kinds of values in different slots. The programmer need not be concerned with how the data are actually stored in memory. In most discussions of object-oriented programming, the focus is on user-defined types, so one might get the impression “object-oriented programming = classes,” but this is most certainly not true. In the Smalltalk programming language, everything is an instance of a class of some sort, and the built-in classes are treated the same as the additional user-defined classes. This is also true in Lisp. On

60

PART | I Foundations of Biomedical Informatics

the other hand, although in java, it is claimed that everything is a class, in reality much of java’s syntax and semantics are about managing namespaces. User-defined types (defined either by defstruct or defclass) share the possiblity of utilizing inheritance. Built-in types also exhibit inheritance, where there is a type–subtype relation, as for numbers and sequences, for example. The type system and the idea of a class are closely integrated in Common Lisp. Every type corresponds to a class, and every class definition results in a type definition as well. There are three kinds of classes in Common Lisp: built-in classes, structure classes, and standard classes. The built-in classes have restricted capabilities and cannot have user-defined subclasses. Many of the standard Common Lisp types correspond to built-in classes, for example, number and its subtypes, array, sequence, cons, etc. Each structure type defined by defstruct corresponds to a structure class. Similarly, classes defined by defclass define types that are subtypes of standard-object, which is a subtype of the general type t or Lisp object. When using “class” to refer to a built-in class or structure class, the context should make the meaning clear. Generic Functions and Methods The idea of a generic function is that the function’s body (the code that executes when the function is called) is made up of methods (defined by defmethod). Each method is identified with a particular combination of the types of the arguments to the function. So, the same function call with different types of inputs will result in different methods being used. A program can add methods to any generic function though one should not do this unless the generic function’s author has specified how this should be done. If a function has been defined using defun, it will be an ordinary function, and one cannot subsequently define methods for it. An example from the author’s radiation treatment planning system, Prism, will illustrate the idea. The Prism system provides interactive control panels and graphic visualizations of patient-specific anatomy, radiation treatment machines, and the radiation dose distributions that the machines produce with various settings of the controls. The program calculates the dose using well-known formulas. A snapshot of a Prism screen is showin in Figure 9.2 in Chapter 9. The program can produce several kinds of cross-sectional and projected views of the anatomy and other objects. The renderings are computed by a generic function called draw. The draw function takes two inputs, an object to draw and a particular view control panel in which to draw it. For each combination of a type of object and a type of view (coronal, transverse, sagittal, or beam’s eye view), there will be a method. As new kinds of objects were added to Prism, new draw methods were written. Similarly, as new kinds of views were added, new methods needed to be written. To insure against errors that could occur if the program attempted to draw objects in views where the particular combination had no method, a fall back or default method was included. Here it is. (defmethod draw ((obj t) (v t)) "DRAW (obj t) (v t) This is a default or stub method so we can build and use the various functions without crashing on not yet implemented draw calls." (format t "No DRAW method for class ˜A in ˜A˜%" (class-name (class-of obj)) (class-name (class-of v)))) The defmethod macro has a form similar to defun, except that any of the inputs can have a type specifier, as illustrated. In the case above, the type specified is type t, which is also the default. Any type can be a type specifier, not just the name of a class. The defmethod macro associates methods, or code blocks, with an existing generic function, or if no generic function of that name exists yet, one is created, and the body becomes a method for it. If an ordinary function already exists with the same name, it is an error. Any other method for the draw function must have the same inputs, an object to

Chapter | 1 Biomedical Data

61

draw and a view to draw it in. The details of what happens will vary, but any more specific method that the programmer provides will supersede this method. This method uses two functions that are part of CLOS. One, class-of, returns the class of its input. The class is an actual piece of data in the system, not just a name that appears in your code. Classes are objects created by the defclass macro, or in some cases, are built-in classes that are predefined. The class-name function takes a class (NOT an instance) as its input, and returns the class name, usually a symbol. We will use this idea that classes are actual objects in the system, not just definitions in source code that are used by a compiler. This is part of the CLOS Meta-Object Protocol (MOP). In CLOS, methods are associated with functions, not with classes. This is different from some other object-oriented programming languages in which methods are associated with classes. Those object-oriented languages implement the capabilities of operations with instances of the corresponding classes. However, that makes it very awkward to have functions that dispatch based on the type of more than one argument. In CLOS, dispatch can be based on any number of function arguments. You just write a method for each combination of argument types. Since classes are just an extension of the Common Lisp type system, one can write generic functions with methods for any types, whether those types are built-in, defined by defstruct or defined by defclass. Thus, one could define a generic function that performed an abstract operation on a variety of data types, implementing that abstract idea with different methods according to each data type. It is not necessary for the classes that specialize methods to have a common “base class” in CLOS since everything already is a subclass of the class t. Some of the built-in functions of Common Lisp are actually generic functions, and you can augment them for new data types or classes that you defined to provide any special behavior needed. Often used examples include CLOS initialize-instance function, which your code should never call (it is called by make-instance), but for which you can provide a method to do extra work of initializing new instances of a class you have defined. See Graham [94, Chapter 11] for more details. Generic functions support inheritance, just as classes and slot definitions do. So, if a generic function has a method for some combination of input types, that method will also be applicable for any combination of input types in which each argument is a subtype of the type for which the method was defined. Here is an example. The Prism radiation treatment planning system (described more fully in Chapter 9) provides a wide variety of control panels for drawing anatomy, positioning radiation beams, viewing the simulation geometry, etc. There is a generic-panel class, with a method for the generic function destroy. Each panel is a subtype of generic-panel, so this method is applicable to each of them. This is a simple consequence of the fact that if an entity belongs to a certain type, it also belongs to all the parent types, so an instance of a beam-panel is also an instance of a generic-panel. This can be seen by the results returned by the two built-in functions, type-of, which returns the most specialized type an entity belongs to, and typep, which returns t if an entity is of a specified type. The following example also illustrates that the ideas of type and class apply to the entire type hierarchy, not just the complex types defined by defstruct and defclass. > (type-of 3.14159) SINGLE-FLOAT > (typep 3.14159 ’number) T > (class-of 3.14159) # As you can see, the type-of function returns a symbol that names the type, while the class-of function returns the actual class object itself, not just the name of the class. This is also true of structure classes and standard classes as well as built-in classes.

62

PART | I Foundations of Biomedical Informatics

Finally, an important element of Lisp that is not found in most other programming languages is that functions are also data, and the type function is also part of the type hierarchy. Thus, one can have variables whose values are function objects, and your program can store function objects anywhere you might store anything else. Furthermore, one can write functions that create new function objects, which can then be used just as if they had been there all along. This will be particularly important as we move from data to knowledge in Chapter 2.

A Redesign Using Classes Here is a rewrite of the organ examples, with classes instead of structures. Note that the slots need some additional specification to have the accessors created. The accessors of slots in a class defined by defclass are not provided automatically as for structure definitions, but these accessors can be generic functions, that is, they can share a common name and have different methods depending on the type of the object. (defclass heart () ((size :accessor size) (beat-rate :accessor beat-rate) (x :accessor x) (y :accessor y) (z :accessor z) ...)) (defclass kidney () ((side :accessor side) (x :accessor x) (y :accessor y) (z :accessor z) ...)) (defclass tumor () ((size :accessor size) (grade :accessor grade) (tissue-type :accessor tissue-type) (x :accessor x) (y :accessor y) (z :accessor z) ...)) In this case, a single generic function, x, can retrieve the x coordinate of any instance of these objects. Just as defstruct automatically created accessor functions for each structured type, defclass will create methods for the generic functions named as the accessors. However, the names can be shared among classes.34 Now, we can define a patient class, analogous to the patient structure, with slots that will hold the individual attributes for each patient that is an instance of this class. Here, we follow the ER diagram, Figure 1.18, though it would be a better design to include the person class and implement patient and provider as subclasses of person. 34. It would seem reasonable to have defclass provide such accessors by default, but there are potential complications when the same slot is declared in a subclass. Should a new method be created by default? I do not have a proposal worked out for this.

Chapter | 1 Biomedical Data

63

(defclass patient () ((name :accessor name :initarg :name) (hospital-id :accessor hospital-id :initarg :hospital-id) (age :accessor age :initarg :age) (address :accessor address :initarg :address) (diagnosis :accessor diagnosis :initarg :diagnosis) (lab-tests :accessor lab-tests :initarg :lab-tests) ...)) Note that the address and diagnosis slots will contain instances of structured objects. We define classes for them too. These kinds of objects will appear in other parts of the medical record too. (defclass address () ((number :accessor number :initarg :number) (street :accessor street :initarg :street) (city :accessor city :initarg :city) (zip-code :accessor zip-code :initarg :zip-code)) (defclass diagnosis () ((name :accessor name :initarg :name) (evidence :accessor evidence :initarg :evidence) ...)) This definition of the diagnosis class does not correspond exactly to the ER diagram. The fields t-code and m-code are specific to cancer and are part of a disease classification system. The classification systems for tumors are not uniform, so it is a challenging modeling problem to determine how in general to represent this information. We would like as before to store the information on a patient or series of patients (instances of the patient class) in a file, in a “serialized” form. By reading the file appropriately, we should be able to reconstruct an object that is equivalent to the original instance in our program. The read and print functions will not work for data that are instances of classes defined by defclass. The Common Lisp print function does not print an instance of a class in a way that it can be reconstructed. We could make an instance of this class and try to print it. > (setq temp (make-instance ’patient :name "Ira K" :hospital-id "99-2345-6" :age 63) # > (print temp) # This instance of the patient class is printed as an unreadable object (the #< reader macro denotes an unreadable object, followed by the class name and some implementation dependent information). We will need to provide some extension to support serialization of class instances, including classes where slot values are themselves class instances. A seemingly elegant solution is to use the CLOS facilities themselves to extend the print function’s capabilities. According to Steele [312, page 815], the printing system (including format) uses the standard generic function, print-object. We can, therefore, write specialized methods for it, corresponding to each class we define in our program, so that when instances of those classes are printed using any print function, they will be handled by the specialized method, and not the system generic method. To print something readably, we start by defining a method for print-object when the object is a patient.

64

PART | I Foundations of Biomedical Informatics

(defmethod (format (format (format (format

print-object ((obj patient) strm) strm "(Patient ˜%") strm " :name ˜S˜%" (name obj)) strm " :hospital-id ˜S˜%" (hospital-id obj)) strm " ...etc. ) ˜%" ...))

Now, when we try to print our instance, it will use our specialized method instead of the system default. This will happen because the built-in print function calls the generic function, print-object, to do the actual work. >(print temp) (Patient :NAME "Ira K" :HOSPITAL-ID "99-2345-6" ...etc. ) This can also get tedious, verbose, and error-prone when a program has many different classes. It does have one nice property. The calls to format will be implemented through the print-object generic function, so if a slot value is another class instance and there is a corresponding print-object method, the information will be printed properly nested logically. The resulting text file will not be formatted nicely for the human reader, however. This output can be read as input to recreate an instance equivalent (equal) to the original. We get the entire list with one call to read, and then hand it to make-instance using apply. Unlike print-object, there is no built-in function read-object for which we can write methods, so we define one here. (defun read-object (stream) (apply #’make-instance (read stream))) Unfortunately, unlike print-object, if there is a slot whose value is an instance of a class, the read function will simply fill that slot with the list that was written out, instead of creating an object from it. So, this read-object function only works for classes whose slots do not themselves have values that are instances of classes. It would seem that we could solve this problem by writing out the call to make-instance in the file. Then, the nested objects would be created along with the top level one. This is essentially a program that writes a program out to a file, to be executed later. However, the read function will just return a list representing an expression to evaluate. So, the read-object function becomes (defun read-object (stream) (eval (read stream))) or another way is to just call the load function. But, this must be considered extremely bad practice. In essence, instead of writing data to a file to be later processed, we are writing an entire program to a file, later to be executed. We have not even begun to look into searching files, which would be very difficult with this arrangement, and one can imagine how inefficient and inflexible the whole scheme might become. Changing the class definition even slightly would involve editing a file or files, in perhaps thousands of places, because all the repeated calls to make-instance would change. Another tempting way to design read-object would be to make it a generic function, like the built-in print-object. Then, you might think you would be able to write methods for read-object for all the relevant classes. For a class that has a slot with a value that is itself an object, the method for that class would need to make an explicit recursive call to read-object. This simply would not work at all. The input to read-object is a stream, not an object instance, so there is no way to determine which methods are applicable. Even preceding it by a call to read first would not work

Chapter | 1 Biomedical Data

65

because the whole point of this design is to generalize the read function to handle objects that are otherwise unprintable and unreadable, so using read first is circular. Aside from the problem of slots whose values are themselves objects, the above scheme has the additional burden that it requires a lot of writing of explicit methods for writing the object data out to files. This is because we are putting the slot names into the files. In most programming environments, the slot names are part of the source code but not available to a running program. If the program code could examine its own definitions, this burden might be relieved. In most programming languages, it is impossible, but you will see in the next section that in Lisp, this is easy to do.

1.2.3 A Better Solution Using Meta-objects While conventional object-oriented programming is nice, it still requires a lot of work for each new class that you add to the system. What if the information about each class was available to the running program? Then, instead of writing explicit code for printing and reading instances of each class, we could write a function that gets the information about the class of the object it is printing or reading and uses that information. If this worked, we could write one general function that would work for all defined classes, and we would not need to write extra code when adding a new class to the program. The idea that a running program can gain access to information about its own data structure definitions has been present in Lisp for a long time, and is just now attracting attention in newer programming languages and environments. It is sometimes called “reflection.” In Lisp, your code can check on the type of an object, retrieve its class, and retrieve properties of classes and objects. Thus, the programmer can indeed write code that can access class data, such as the class name, the superclasses (parent classes), lists of slot names, and other information about a class. The way it works in Lisp is that the CLOS itself is implemented using the same machinery that the application programmer uses. The way classes are implemented is that they are themselves objects, instances of a “higher level” class (a metaclass) called standard-class. The class standard-class is called a metaclass since its instances are “class” objects. This and the classes created by our code are examples of “meta-objects.” CLOS has other meta-objects as well, for example, generic functions, which are instances of the standard-generic-function class. This is known as the CLOS Meta-Object Protocol (MOP). Kiczales et al. [175] explain the idea of a Meta-Object Protocol (MOP) by showing how to build a somewhat simplified version of the MOP. The actual CLOS MOP specification is reprinted in Chapters 5 and 6 of their book. It is not yet adopted as an ANSI standard but is implemented in most Common Lisp systems. Here, we show how the MOP can help solve the problem of storing complex medical data in the style of keyword–value pairs, without writing a lot of extra code. Our plan is that the code will use the class definition itself as metadata to decide what to read and write. We will define a function, slot-names, that returns a list of symbols naming the slots defined in a class. Applying this to the patient class instance on page 63, we should get > (slot-names temp) (NAME HOSPITAL-ID AGE ADDRESS DIAGNOSIS ...) The MOP idea we will use here is that a class is an actual data object in a program, not just a source code construct. Classes have properties that a program can look up when it is running. In particular, it should be possible for a running program to find out what the names are of the slots for a class. The MOP function class-slots gives us a list of the slots (actually the slot-definition meta-objects, which describe the slots), including inherited ones from superclasses that are available in any particular class. Their properties can be examined using accessors, just as for other objects. From the slot-definition objects, we can get their names (as symbols), which we can then use with slot-value to read the value stored in each slot, and with (setf slot-value) to write a value in a slot (as when restoring an object from the serialized data in a file). The MOP function

66

PART | I Foundations of Biomedical Informatics

class-slots requires as input a class, which is easy to obtain. For any object, the MOP function class-of returns its class (the actual class meta-object, not the name of the class). Since slots are implemented with meta-objects, we can use the MOP function slot-definition-name to obtain the name of a slot, given the slot itself. To get a list of all the slot names in a class, we iterate over the list of slot definitions using mapcar. (defun slot-names (obj) (mapcar #’slot-definition-name (class-slots (class-of obj))) The functions slot-definition-name and class-slots may be in a different package than the common-lisp package, but these are the names defined in the MOP documentation.35 Applying this to the patient class instance on page 63, we get what we expected. > (slot-names temp) (NAME HOSPITAL-ID AGE ADDRESS DIAGNOSIS ...) Thus, the MOP gives a way to find out about a class’s slots, iterate over them, writing the contents of each, and recursively doing the same for anything that is itself a class instance rather than a Lisp type that already has a standard printed representation. This can be done in a way that is human readable and allows a symmetric function for reading the data back in and constructing an instance equivalent (equal) to the original. These slot name symbols can be used as input to the standard CLOS functions slot-value and (setf slot-value) to read and set data in the slots of an object. The standard constructor function in CLOS for creating instances of classes, make-instance, also can take a symbol as input that is the value of a variable, so one can write code that creates and manipulates class instances without having any class names or details about the class explicitly written in the code. Now, we will build the code that can read and write a representation of the patient data described above. The serial representation we will use is still based on the idea of keyword–value pairs, something like that of the previous section. Each keyword will be either a class name or a slot name, but we will not use parentheses to group data, except when they are a simple Lisp expression that should go into a particular slot. We will, therefore, need some way for the reader function to determine that the end of the slot name/value pairs is reached for a given instance. We will use the convention that the keyword36 symbol :END is never the name of a class or a slot, so it can be used to indicate that there are no more slots for the current instance being read. This simple scheme should work fine for simple objects, whose slot values are printable Lisp data. Just as with our previous attempts, it will be problematic for slots that themselves have objects in them or lists of objects. However, in this case we will be able to solve that problem with only a small addition to the supporting code and framework. One might think that XML solves this problem by requiring beginning tags and ending tags. However, the problem here is not to decide where an entity begins and ends but to distinguish between tags that name classes and tags that name slots of classes. The get-object function will read from a data stream that looks like this (the ellipses just mean “lots more keyword–value pairs”): PATIENT NAME "Ira K" 35. In Allegro CL™ , a commercial Common Lisp implementation from Franz, Inc., these functions are external in the CLOS package. In CMUCL, an open source Common Lisp system, a more complex accessor is needed in place of slot-definition-name and class-slots is in the PCL package. In CLISP, another open source Common Lisp implementation, the name corresponding to slot-definition-name is slotdef-name; this and class-slots are internal in the CLOS package. Other implementations may have other versions since the MOP is not yet standardized. 36. Note that here :END is a keyword in the technical sense that it is in the Common Lisp keyword package. Elsewhere in this section we are using the term “keyword” in the generic sense of “label.”

Chapter | 1 Biomedical Data

67

HOSPITAL-ID "99-2345-6" AGE 63 ... :END The indentations and appearance of each slot on a separate line are ignored by the Lisp read function, but this formatting makes it easier for human inspection. The get-object function starts by reading the first symbol in the input. It expects that this will be the name of a class that has a class definition already in the system. Then, it reads slot-name/value pairs, repeating until the :END tag is encountered instead of a slot name. Indefinite iteration (loop) is used here because the code cannot “look ahead” to see how many slots are present in the file or in what order they appear. This implementation of get-object will handle any ordering of slot data. Not all slots need to be specified in the data file (some might have suitable default values), but any slot appearing in the data file must be included in the class definition. Since the class definition is separate from the data in the file, we would say that the data are not “self-describing,” but we are using the class definition as metadata. (defun get-object (in-stream) (let* ((current-key (read in-stream)) (object (make-instance current-key))) (loop (setq current-key (read in-stream)) (if (eq current-key :end) ;; no more slots? (return object) (setf (slot-value object current-key) (read in-stream)))))) Note that the get-object function will work for any class defined in our program because it uses the class definition rather than having explicit names here. We do not have to write any methods for anything. It does not even have to be a generic function itself since the same exact code executes for all classes. Thus, the class definition serves as the metadata. In an industrial strength program, we might add some error checking to detect malformed or unrecognizable input to make the code more robust. One problem certainly is that the code will signal an error if it encounters a symbol naming a non-existent slot for the class being read. Similarly, an error will be signaled if at the beginning a class name is encountered for which there is no class definition. However, in well-controlled circumstances, this may not be necessary. In the author’s RTP system, the code described here has been used for over 10 years to plan radiation treatments for over 5000 patients, and that system includes no error-checking code. Error checking is not needed because these data files are only created by the same program and do not come from any other source. The program code can guarantee that the syntax and semantics are correct, as defined here. In order to create these files, we need a complementary function to write the data to a file in the format shown. This function, which we call put-object, works with the same machinery we described above. It uses the slot-names function defined previously to get a list of the slots, and iterates over them writing out the contents of each. (defun put-object (object out-stream &optional (tab 0)) (tab-print (class-name (class-of object)) out-stream tab t) (dolist (slotname (slot-names object)) (when (slot-boundp object slotname) (tab-print slotname out-stream (+ 2 tab)) (tab-print (slot-value object slotname) out-stream 0 t))) (tab-print :end out-stream tab t))

68

PART | I Foundations of Biomedical Informatics

The tab-print function provides the indentation and new lines when needed to keep the file reasonably human readable. It puts in as many leading spaces as specified by the tab parameter, and includes a trailing space so that keywords and values will be separated. (defun tab-print (item stream tab & optional (new-line nil)) (format stream "˜A˜S " (make-string tab :initial-element #\space) item) (when new-line (format stream "˜%"))) This set of functions can now write and read back any collection of CLOS class instances, with arbitrary class definitions, even if mixed together in a single list of instances. Adding new classes does not require adding any new code. The class definition itself, through the MOP, provides the details for reading and writing. This works fine if all the slots have values that are simple Lisp objects, that is, can be printed readably by the standard printing system (including lists, arrays, and structures). However, it will fail if the slot value is itself an object (instance of a class) or contains objects, for example, in a list. In the example on page 54, the diagnosis slot actually contains a structured object, an instance of the diagnosis class. It would fail because format, like print, will not have any way to deal with an instance of a user-defined class. This is exactly the same problem we encountered in Section 1.2.2. This time, however, we can extend the metadata to enable the code to handle slots whose values are class instances and other ordinarily unprintable data. A straightforward way to extend get-object and put-object to handle this case is to make them recursive, that is, if the slot content is an object, then make a recursive call to read or print it. Similarly, if the content of the slot is a list of objects, an iteration over the list will be needed. (Iteration is not needed for a list of simple Lisp data since the Lisp system can handle it directly.) In order to decide which kind of slot contents we are dealing with, we will need a new function, slot-type, which will return one of the three keywords: :simple, :object, or :object-list. The slot type :simple means that the content of a slot is a printable and readable Lisp data type, one that has a well-defined pr