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 printed form. The slot type :object indicates that the content of the slot is an instance of some kind of object, and therefore cannot be read by the standard Lisp function read. In this case, as noted, we just make a recursive call to get-object. The slot type :object-list means that the slot contents are a list of objects, which will require an iterative call to get-object. There is no such function in Common Lisp, CLOS or in the MOP. We will write this additional code a little later in this section. For now, we will just assume it exists and show how to use it. A case form takes care of the three cases, depending on the value returned by slot-type. The case operator has as its first input an expression to evaluate to obtain a key. The remainder of the case expression contains clauses like cond but instead of evaluating test expressions, each clause has a key or list of key values. The key resulting from the first input is used to find the first applicable clause. If it is found then the rest of the clause is evaluated in sequence. If the key is not found, case returns nil. Here is get-object with these recursive and iterative calls added. The expression after case, the call to slot-type, is expected to return one of the three keywords. Whichever it is, the following expression will be the one that is evaluated and the others are ignored. (defun get-object (in-stream) (let* ((current-key (read in-stream)) (object (if (eq current-key :end) nil ;; end of object list (make-instance current-key)))) (loop

Chapter | 1 Biomedical Data

69

(setq current-key (read in-stream)) (if (eq current-key :end) ;; no more slots? (return object) (setf (slot-value object current-key) (case (slot-type object current-key) (:simple (read in-stream)) (:object (get-object in-stream)) (:object-list (let ((slotlist ’()) (next-object nil)) (loop (setq next-object (get-object in-stream :parent object)) (if next-object (push next-object slotlist) (return (nreverse slotlist)))))))))))) Indefinite iteration is used also in the inner loop because the code has no way of determining in advance how many objects there might be, if the slot value is a list of objects (in the file). We need a way to indicate the end of the list, and here again, the keyword :END serves the purpose. If :END is detected where a class name should be, it signals that there are no more objects, so get-object should return nil, which terminates the loop when next-object is tested. Similarly, for put-object, we add a case form to handle each of the three possible slot types. Here is the expanded implementation. (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)) (case (slot-type object slotname) (:simple (tab-print (slot-value object slotname) out-stream 0 t)) (:object (fresh-line out-stream) (put-object (slot-value object slotname) out-stream (+ 4 tab))) (:object-list (fresh-line out-stream) (dolist (obj (slot-value object slotname)) (put-object obj out-stream (+ 4 tab))) (tab-print :end out-stream (+ 2 tab) t))))) (tab-print :end out-stream tab t)) In put-object, the iteration over the list in a slot containing an object list can be definite iteration using dolist or mapc since the list is available at the outset (the object already exists and the slots have values). These two ways to do iteration over a list are equivalent, and it is a matter of style which you might prefer. Note that the recursive calls to put-object and tab-print include increments to the amount of whitespace to indent so that objects that are values in slots get nicely pretty-printed in the data file. The choice of 4 and 2 for the incremental amount of whitespace is arbitrary but seemed to work well in the author’s RTP system.

70

PART | I Foundations of Biomedical Informatics

One detail remains. Since there is no built-in function slot-type, we have to write it. This function should return a keyword identifying the contents of the slot as :SIMPLE for readable and printable Lisp objects, :OBJECT for an instance of a user-defined class, and :OBJECT-LIST for a list of such instances. It is the one element that needs to be defined for each class, if the slots are expected to contain other objects or lists of objects. In a typical application of this code, most classes will have simple slots, and we only need a default method. For more complex classes, it is not hard to write a method that just returns the non-simple slot types as compared with writing a method for print-object, which would be many times larger. Here is the default method: (defmethod slot-type ((object t) slotname) :simple) Note that in this method, the input variable slotname is not used. Most Lisp compilers will flag this by issuing a warning. It is not an error but the intended behavior. The definition of the function includes this input, but this particular method does not use it.37 For the patient class, the address slot and the diagnosis slot both contain instances of objects defined by the CLOS class definitions. For the patient class, we might then have the following method: (defmethod slot-type ((object patient) slotname) (case slotname ((address diagnosis) :object) (otherwise :simple))) In the otherwise clause, if this class is a subclass of a big class or is several layers down in a class hierarchy, it might be onerous for the programmer to look up all its parent classes, so all the slots can be accounted for. Since there is always a default method, one only needs to put in the case form any new non-simple slots. A simple way to handle the otherwise clause is to use the standard CLOS function call-next-method, which will then use the previously written methods to look up any inherited slot. The call-next-method function can be used in any method. It finds the next most specific applicable method after the one from which it is called, runs that code with the same inputs as the original function call, and returns whatever that next most specific method returns. Here is a version of slot-type for the patient class, using call-next-method. (defmethod slot-type ((object patient) slotname) (case slotname ((address diagnosis) :object) (otherwise (call-next-method)))) An alternative way to write these methods would be to write a method for each value of slotname, using eql specializers. This is much less desirable because it requires that any slot with a given name (possibly used in many different classes) must have the same meaning in terms of content type. This restriction creates global constraints on names, making it more work to add new classes. Finally, one might consider that this information should be encoded in type declarations. This is inappropriate for several reasons. The slot type categories we are using here are not the same kind of thing as the type hierarchy in the Common Lisp system itself. In general, type declarations are optional for variables and locations since type is a property of what is stored there. One could indeed expand on CLOS and define new slot-definition meta-objects, with support for declaring and even enforcing restrictions on what is stored in those slots. Such extensions are found in the large and powerful frame systems developed for knowledge representation as opposed to data. In Chapter 2, we will develop the idea and a simple example of a frame system, with pointers to some available implementations. 37. The compiler warning can be eliminated by using a declaration, (declare (ignore slotname)), but this is not required. The code is still correct without it.

Chapter | 1 Biomedical Data

71

The get-object and put-object functions only handle one object at a time. However, it is simple to write a next layer of input and output functions that handle a file of many such records on input, or an entire list of objects on output. The input function will be called get-all-objects and the output function will be called put-all-objects. The get-all-objects function opens a file whose name is the value of the input variable filename, and iteratively calls get-object to accumulate a list of all the objects found in the file, until the end of the file is reached. It returns the list of object instances. If the file does not exist, it returns nil. (defun get-all-objects (filename) (with-open-file (stream filename :direction :input :if-does-not-exist nil) (when (streamp stream) (let ((object-list ’())) (loop (cond ((eq (peek-char t stream nil :eof) :eof) (return object-list)) (t (push (get-object stream) object-list)))))))) The put-all-objects function takes as input a list of objects whose class definitions exist in the environment, and a filename, opens a file whose name is the value of the variable filename, and iteratively calls put-object on successive elements of the list object-list. If a file named filename already exists, a new version is created. (defun put-all-objects (object-list filename) (with-open-file (stream filename :direction :output :if-exists :new-version) (dolist (obj object-list) (put-object obj stream)))) Other enhancements are possible, for example, adding a :BIN-ARRAY type for large binary data arrays stored in separate files. To handle such files, we could create a function read-bin-array for reading such files and a companion write-bin-array for producing them. Since the binary data are in another file, the text file should contain information for how to read that file, that is, the filename and the array dimensions. Medical image data, discussed in Section 1.1.5, are an example of the need for this. In Section 1.2.4 we show how to implement these two functions. Although it would seem that this is an inefficient solution to storing patient data, it has been used successfully for over 10 years in the author’s RTP system, Prism [149], which has been in clinical use at the University of Washington Medical Center as well as at several other clinics.38 Over 50,000 complete records of patient data and radiation treatment plans are kept online from the first day when the system was put into clinical use in 1994. Index files help to find individual patients’ data, and retrieval is fast enough for clinical use. Each patient case instance is stored in a separate file in the file system, with a unique filename generated by the system. Thus, each file is small and access is quick, requiring only a lookup of the filename in the index and the opening and reading of a relatively small file. It is possible that a relational database back end could be used in this application, but it is not at all clear that this would perform better.39 A brief introduction to relational database ideas is in Section 1.4. An object-oriented database would be a good match here, but no reasonable implementations were 38. A brief introduction to cancer, radiation therapy, and radiation treatment planning may be found in Chapter 9, which describes other applications of the principles and methods of Part I to problems of cancer treatment. 39. A commercial RTP product in the mid-1990s tried this, but their system had very unsatisfactory performance.

72

PART | I Foundations of Biomedical Informatics

available in the early 1990s when Prism was designed and implemented. In Section 1.4.1, we give a brief introduction to the ideas of object-oriented databases.

1.2.4 Medical Images: Incorporating Binary Data So far, in the patient record example, we have considered only data that are easily and logically stored as text. Medical image data, on the other hand, are not efficiently represented as character code sequences. As noted earlier, the image pixels are represented in a computer program as a 2D array of numbers, where the number at a pixel location represents the brightness (or color) of the image at that spot. The pixel array is understood to represent samples of image data on a regular rectangular grid. The numbers can be integers in the range 0 to 4095 (typically) for CT images and small decimal numbers for PET images. Such numbers, when represented in the form of text, will take up four or more bytes (one for each digit) plus space or other delimiters. In the case of CT and magnetic resonance (MR) images, only two bytes are required to represent each number in binary form (because the range of values is limited by the machine design to 16-bit signed or unsigned integers). When reading binary numbers into a computer program data structure, no conversion is necessary. By comparision, reading a character (digit) representation will require some parsing and conversion. So, for image data, the bytes (or multi-byte sequences) should instead be written and read directly as binary numbers representing numerical data, image pixels. A 2D array of pixel numbers would be useless unless we knew something about the image and the pixels. As described earlier, it is important to know the slice thickness to construct sagittal and coronal images and other renderings from the transverse image data. In order to interpret the images, the radiologist (and radiation oncologist) needs to know the position inside the patient corresponding to the image as well as other data about the machine settings (the X-ray tube voltage, whether or not the patient had received injection of contrast dye, etc.). Medical image data sets, therefore, include “annotation” data or information about the images. Typically, they include the patient’s name (a character sequence or text), birth date (also text), the inter-pixel spacing of the grid (cm) (may be binary, floating point format rather than simple integer or fixed point), and many other attributes. So, the parsing of an image data file can be very complex since the interpretation of the byte stream is mixed and arbitrary according to some software designer’s choices. These choices vary widely among the different manufacturers of medical imaging systems. The difficulty of dealing with such arcane file formats led eventually to the creation of a network protocol for exchanging image data, called DICOM (see Chapter 8). The DICOM protocol still presents the problem of parsing an arcane sequence of heterogeneously encoded data items. The advantage of DICOM is that you only need to learn and implement this one protocol, which is vendor and system independent. The DICOM protocol only addresses the exchange of data between client and server programs, but not how the individual applications should store it. This allows the application software designer to choose a storage scheme that is best for her application. After presenting a little background about medical images, we show how to extend the keyword–value pair representation to support medical images in binary form.

Representing Image Data A typical encoding of an image as a data structure in a computer program is as an instance of an image class. The following code shows how such a class might be defined:40

40. In this class definition, we have included a new element, documentation for each slot, and for the class as a whole. In Common Lisp, documentation strings are part of the program and are accessible to a running program, unlike comments in source code, which are ignored by compilers and interpreters and not available to the program itself.

Chapter | 1 Biomedical Data

73

(defclass image () ((uid :type string :accessor uid :initarg :uid) (patient-id :accessor patient-id :initarg :patient-id :documentation "The patient id of the patient this image belongs to.") (image-set-id :accessor image-set-id :initarg :image-set-id :documentation "The image set id of the primary image set the image belongs to.") (position :type string :accessor position :initarg :position :documentation "String, one of HFP, HFS, FFP, FFS, etc. describing patient position as scanned (Head/Feet-First Prone/Supine, etc).") (description :type string :accessor description :initarg :description) (origin :type (vector single-float 3) :accessor origin :initarg :origin :documentation "Origin refers to the location in patient space of the corner of the image as defined by the point at pixel array reference 0 0 or voxel array reference 0 0 0.") (size :type list ;; of two or three elements, x y z :accessor size :initarg :size :documentation "The size slot refers to the physical size of the image in each dimension, measured in centimeters in patient space.") ;; ...other slots ) (:default-initargs :id 0 :uid "" :patient-id 0 :image-set-id 0 :position "HFS" :description "") (:documentation "The basic information common to all types of images, including 2-D images, 3-D images.")) This general class is then specialized to image-2d and image-3d, which have further special attributes. An image-2d depicts some 2D cross-sectional or projected view of a patient’s anatomy and is typically a single CT image, an interpolated cross-section of a volume, or the result of ray tracing through a volume from an eyepoint to a viewing plane. Here is the image-2d subclass: (defclass image-2d (image) ((thickness :type single-float :accessor thickness :initarg :thickness) (x-orient :type (vector single-float 3) :accessor x-orient :initarg :x-orient :documentation "A vector in patient space defining the orientation of the X axis of the image in the patient coordinate system.") (y-orient :type (vector single-float 3) :accessor y-orient :initarg :y-orient :documentation "See x-orient.") (pix-per-cm :type single-float :accessor pix-per-cm :initarg :pix-per-cm)

74

PART | I Foundations of Biomedical Informatics

(pixels :type (simple-array (unsigned-byte 16) 2) :accessor pixels :initarg :pixels :documentation "The array of image data itself."))) The pixels slot for an image-2d contains a binary 2D array in which the value at each location in the array refers to a sample taken from the center of the region indexed, and values for images with non-zero thickness refer to points midway through the image’s thickness. The origin of the pixels array is in the upper left-hand corner, and the array is stored in row-major order, so values are indexed as row, column pairs, that is, the dimensions are y, x. Typically, cross-sectional medical images such as X-ray, CT, MRI, and PET are generated in sets in which the orientation of the images, their scale factors, and their positions in the patient are all related. Such a collection of images is called a “position-related set,” or “series.” The simplest way to represent such a collection in a program is as a list of image-2d objects. The list can be searched and the data extracted for display and other computations, including the creation of sagittal, coronal and other reformatted images as described earlier. In addition to being useful as 2D images, the set can be reassembled into a 3D image. This kind of object is represented by the class image-3d. (defclass image-3d (image) ((voxels :type (simple-array (unsigned-byte 16) 3) :accessor voxels :initarg :voxels :documentation "a 3-D array of image data values")) (:documentation "An image-3D depicts some 3-D rectangular solid region of a patient’s anatomy.")) In the 3D image, voxels is the 3D array of intensity values or colors coded in some standard way, for example, as RGB (Red, Green, and Blue intensity) values. The value at each index of the array refers to a sample taken from the center of the region indexed. The origin of the voxels array is in the upper left back corner, and the array is stored in row, then plane-major order, so values are indexed as plane, row, column triples, that is, the dimensions are ordered z, y, x. Rearranging the set of 2D pixel arrays into a single 3D voxel array makes some image processing calculations simpler. These include volume rendering and the computation of projected images (simulated X-ray films, also called digital reconstructed radiographs, or DRR).

Reading and Writing Image Data Software packages to display and manipulate medical images use many different forms of storage of the image data in files. One way to do this is to store the pixel values as 16-bit binary numbers and put the other information in a separate text file, formatted as a tagged data stream, just as we did for the patient data example in Section 1.2.3. Figure 1.19 is an example of a keyword–value arrangement for a text file containing the “annotations” or descriptive information about the images. Each instance begins with a keyword naming the class, IMAGE-2D, and then keyword–value pairs for each slot in the class, that is, slot names followed by values in a format acceptable directly to the Lisp read function. These slots correspond to the image-2d class (including slots inherited from the image class). This file can be processed and ones like it produced by the get-object and put-object functions described in Section 1.2.3. Note that the pixels slot does not contain actual image pixel values but instead carries a list of information describing a separate file containing the pixel values. This information would be used by a new procedure read-bin-array to read in the actual array data and store it in the slot of the newly constructed object, as we suggested earlier.

Chapter | 1 Biomedical Data

75

IMAGE-2D DESCRIPTION "Pancreatic cancer: abdominal scan" ACQUISITION-DATE "24-May-1994" ACQUISITION-TIME "16:40:23" IMAGE-TYPE "X-ray CT" ORIGIN #(-17.25 17.25 0.0) SCANNER-TYPE "AJAX 660" HOSPITAL-NAME "University Hospital, Hackland, WA" RANGE 4095 UNITS "H - 1024" SIZE (34.504 34.504) PIX-PER-CM 14.8388 THICKNESS 0.500 X-ORIENT #(1.000 0.000 0.000 1.000) Y-ORIENT #(0.000 -1.000 0.000 1.000) PIXELS ("pat-1.image-1-1" 512 512) :END IMAGE-2D DESCRIPTION "Pancreatic cancer: abdominal scan" ACQUISITION-DATE "24-May-1994" ACQUISITION-TIME "16:40:23" IMAGE-TYPE "X-ray CT" ORIGIN #(-17.25 17.25 1.0) SCANNER-TYPE "AJAX 660" HOSPITAL-NAME "University Hospital: Hackland, WA" RANGE 4095 UNITS "H - 1024" SIZE (34.504 34.504) PIX-PER-CM 14.8388 THICKNESS 0.500 X-ORIENT #(1.000 0.000 0.000 1.000) Y-ORIENT #(0.000 -1.000 0.000 1.000) PIXELS ("pat-1.image-1-2" 512 512) :END IMAGE-2D DESCRIPTION "Pancreatic cancer: abdominal scan" ... FIGURE 1.19 A portion of a sample image set data file.

We now turn to the implementation of read-bin-array and write-bin-array mentioned previously. By separating the pixel array from the annotations, we can read in the pixel array data very efficiently and simply, using the standard Common Lisp function read-sequence. This function reads bytes from a binary file until the sequence passed to it is filled. The sequence will contain binary elements as specified by the element type of the file. The read-sequence function can determine the size of the sequence passed to it since in Common Lisp sequences are objects that carry with them information about their size. Here is a version that creates a new array, given the total size in bytes. The array is a one-dimensional array since that is the only type that read-sequence can process. The elements are 16-bit binary quantities, not 8-bit bytes.

76

PART | I Foundations of Biomedical Informatics

(defun read-bin-array (filename size) (let ((bin-array (make-array (list size) :element-type ’(unsigned-byte 16)))) (with-open-file (infile filename :direction :input :element-type ’(unsigned-byte 16)) (read-sequence bin-array infile)) bin-array)) Alternately, if the receiving array was already in existence, it could be passed in, instead of passing a size parameter. In this case, the function need not return the array as a value since it directly modifies the array that is passed in. (defun read-bin-array (filename bin-array) (with-open-file (infile filename :direction :input :element-type ’(unsigned-byte 16)) (read-sequence bin-array infile))) As nice as this is, it is better from the point of view of the program that uses the array if it is a 2D array instead of a one-dimensional array. If it is a 2D array, the program that uses it can explicitly use row and column indices instead of explicitly computing offsets into the linear array. However, as noted, the read-sequence function handles only one-dimensional arrays. One solution to this problem is to put a loop in read-bin-array and read a row at a time, but this turns out to be tricky and inefficient. This problem of needing to index an array in different ways comes up sufficiently often that the Common Lisp standard includes a facility to do this in a standard way. We can create a 2D array, and then create another array, which references exactly the same elements but is indexed as a one-dimensional array. This is called a displaced array. It is used for other purposes as well, for example, referring to a part of an array offset by a fixed amount, for example, as a “subarray.” So, here is the 2D version of read-bin-array: (defun read-bin-array (filename dimensions) (let* ((bin-array (make-array dimensions :element-type ’(unsigned-byte 16))) (disp-array (make-array (array-total-size bin-array) :element-type ’(unsigned-byte 16) :displaced-to bin-array))) (with-open-file (infile filename :direction :input :element-type ’(unsigned-byte 16)) (read-sequence disp-array infile)) bin-array)) Alternatively, as in the 1D case, if we want to supply the array to be filled as an input, (defun read-bin-array (filename bin-array) (let ((disp-array (make-array (array-total-size bin-array) :element-type ’(unsigned-byte 16) :displaced-to bin-array))) (with-open-file (infile filename :direction :input :element-type ’(unsigned-byte 16)) (read-sequence disp-array infile)))) Since the array passed to read-sequence is a one-dimensional array, the code works efficiently. In particular, there is no need to read in a one-dimensional array and then copy it to a separate 2D array. The 3D array case is left as an exercise for the reader.

Chapter | 1 Biomedical Data

77

For generality, the three blocks of code can be combined into one function with a conditional branch on the rank of the desired (or supplied) array. To get the ultimate efficiency achievable in these functions, it would be important to include declarations so that the compiler can generate in-line code and optimize the use of storage for the array values. Now, we can add this support to the get-object function. It only requires adding one more branch to the case expression to handle the bin-array slot type. We use here the first version, where the second argument is the array dimension list. In the file, it is assumed that the slot data are the filename of the binary data and the array dimensions, as shown in Figure 1.19. (defun get-object (in-stream) (let* ((current-key (read in-stream)) (object (if (eq current-key :end) nil ;; end of object list (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) (case (slot-type object current-key) (:simple (read in-stream)) (:object (get-object in-stream)) (:object-list (let ((slotlist ’()) (next-object nil)) (loop (let ((obj (get-object in-stream :parent object))) (if obj (push obj slotlist) (return (nreverse slotlist))))))) (:bin-array (let ((bin-info (read in-stream))) (read-bin-array (first bin-info) (rest bin-info)))) )))))) Now, we need the counterpart of read-bin-array, which takes an image pixel array and writes it to a specified file. This function, write-bin-array, will take a filename for the file to write and the binary array as inputs. It is not necessary to also provide the dimensions since the array has that information available. The idea is to get the array dimensions and in an iteration (using dotimes is probably the simplest) just call write-byte to write each pixel value to the file. The only thing to be careful of is to open the file with the specification that the element type is (unsigned-byte 16). This is an optional input to with-open-file or the open function. Then, the write-bin-array function can be used in an extended version of put-object in the same way as we extended get-object. Both of these functions are left as exercises for the reader.

1.3 XML A system of tags that define specific categories of data and specific structures is called a markup language. The most ubiquitous application of markup languages is in creating documents, notably formatted reports, articles for publication, and books. For example, the LATEX document preparation

78

PART | I Foundations of Biomedical Informatics

system [186] was used in writing and producing this book. The HTML markup language [222] is used in documents that are intended to be viewed by a web browser program. However, as we have shown, markup can be used in data description as well. The most widely used markup languages share a common syntax in which the markup terms are enclosed in angle brackets (), and the tag that ends an item, section, or element is (usually) identical to the tag that begins it, with a / added at the beginning of the tag text. A standard called SGML, for Standard Generalized Markup Language, defines a metalanguage or set of rules for defining a markup language using a standard syntax.41 A subset of SGML known as XML [104], for Extensible Markup Language, is the most popular syntactic standard in use at the present time for defining markup languages. The idea of XML is to provide more standardized and possibly more sophisticated support for markup, that is, to standardize the syntax for embedding tags into the text of a document to label its parts. This allows for retrieval of the parts as entities. It is an alternative to the tag–value representation we presented in Section 1.2.3. However, like the symbol/list tag system, XML only defines the syntax for tags and descriptions of structure. It does not define the meaning of any particular tag. Thus, XML by itself does not give any meaning or interpretation to a document. The writer or designer of the tag language associates meaning with particular tags. In order to do any computation on the document text, a computer program must have some information in it about what to do about each particular tag. This is parallel to the role that the class definition plays in being able to write programs that interpret tagged text, as in Section 1.2.3. One should not be misled into thinking that XML’s document type definition (DTD) facility solves this problem of defining the meaning of tags. Having a DTD for classes of documents or data records is important, but a DTD only defines what is the allowed and required structure for a particular kind of document and is generally only used by programs to do structure checking and to determine if the document is correctly formed or not. The meaning of the tags and the structures containing them is not specified by the DTD but is something that the programmer must decide or know separately. XML schemas are a more flexible way to specify the structure and allowed tags of a document as well as constraints on the content of fields. However, these are still only syntactic and do not specify the meaning of the data contained within a tagged field. Nevertheless, DTDs and schemas are important to assure at least one level of data quality, namely that the documents are correctly constructed. An application program that processes an XML document can be much simpler if it can assume that the tags and data are consistent with the DTD or schema, rather than having to check syntax as the document is processed. Using a DTD or schema allows for running a validation program on a document before an application attempts to process the data. Here is how the patient data instance in Section 1.2.2 might look when labeled with XML style tags. Ira K 99-2345-6 63 ... A computer program could translate the above text into a series of tokens, rather similar to our symbol and list representation, and then search for particular tags within a particular structure. In this example, a program might, on detecting the tag, create an instance of a patient class and then interpret the remaining tagged items up to the closing tag as names of slots and data to be put in the corresponding slots in the newly created patient instance. Updates to existing data structures could be handled the same way. Alternately, the electronic medical record system might be using a relational database system to store and retrieve patient data. In this case, the program 41. The SGML standard is ISO standard 8879 (1986) and may be found at the ISO web site, http://www.iso.ch/ cate/d16387.html. A book [91] written by the inventor of SGML provides additional background.

Chapter | 1 Biomedical Data

79

that is processing the XML input would create appropriate commands in the database system’s data manipulation language to add a new record to the patient data table or update an existing record. The above example is about the simplest possible use of XML imaginable. Each tag has no attributes. It just marks the beginning (and its closing version marks the end) of a container, which has some data. Containers can be nested, just like lists. It is also possible to have attributes associated with a tag, rather than creating separately tagged items aggregated within a container labeled by the tag. Here is an example of such a structure, an excerpt from a record in GO [11, 12, 329], a large hierarchically structured set of data about genes and gene products, including cellular component, biological process, and molecular function information. Each tag has a prefix, which usually means that it has an intended meaning defined somewhere other than the document containing it. NADH dehydrogenase activity This particular “document” describes a class. Every entry in GO is a class. The class tag includes two attributes. The first, labeled with the tag, xmlns:owl, provides a URL where more information is available about the tags that have the prefix owl, for example, the class tag. The second, labeled rdf:ID, provides a unique identifier within GO for this document. Then, the parts of the document include a label, which is some human-readable text describing the entity, and two data elements providing unique identifiers of the parent processes of which this is a subclass or specialization. The general layout of a container tag with attributes is ...content here The tags beginning with the prefixes rdf, rdfs, and owl have meanings defined by World Wide Web Consortium (W3C) standards. Resource Description Framework (RDF) provides a set of predefined tags that can be used in a way that (because they are described in a published document adopted by a standards body) can be relied on by different groups exchanging data. The Web Ontology Language (OWL) similarly adds some predefined tags, with meanings that can be used to represent biological, medical, or other data and knowledge so that it will be interpretable without individual agreements having to be reached by people every time some data needs to be encoded and exchanged. These standards and much more can be found at the W3C web site, http://www.w3.org/. GO is organized into an extensive class hierarchy so that you can determine from it if a particular class of gene product’s function is in some sense a subclass or specialized version of some more general kind of function, for example, in this case, the process “NADH dehydrogenase activity” is a specialization of each of two more general processes. Only their identifiers are given here, so you have to search GO to find the full records for each. A lookup directly in the XML file would involve a huge amount of parsing. However, once the data are converted into structures like lists and symbols, we can use the search methods already described for sequence data. Then, we find that GO_0005489 is the identifier for “electron transporter activity,” and GO_0016651 is the identifier for “oxidoreductase activity, acting on NADH or NADPH.” We can in turn look for the full records for these two to determine if they are subclasses of more general processes, etc. So, given two GO identifiers, we can search GO to find their relationship, if any. This will be developed more extensively in Chapter 5, using ideas and methods from Chapter 2. A full description of basic XML is beyond our scope here; however, to give the flavor of how to generate XML tagged documents from data in a running program and how to transform XML tagged

80

PART | I Foundations of Biomedical Informatics

documents to data within a program, we provide a simple XML writer and a short description of an XML parser available with one of the commercial Common Lisp systems. It is moderately easy for a computer program to write XML versions of simple objects like instances of the patient class described in Section 1.2.2. In fact, for any instances of classes that are implemented like the patient data described in Section 1.2.3, we can use a modified version of the put-object function developed in that section. The changes that are needed to put-object are ●

●

where we print a tag (a slot name), we need to write an XML opening tag containing the slot name, where we are done producing the printed representation of the data item, we need an XML field ending tag (with a slash before the slot name).

We just build the solution with the same basic code as in put-object, replacing the output part with a fancier one that writes all the brackets and slashes of XML syntax. This new function is called put-object-xml to distinguish it from put-object. This version has to write both an opening tag and a closing tag, each in the right place. The opening tag is written before writing out the slot contents, and we put that detail in a separate function, print-xml-tag. Similarly, after printing the slot contents, the function put-object-xml calls another function, print-xml-end-tag, to write the closing tag. (defun put-object-xml (object out-stream &optional (tab 0)) (let ((tag (class-name (class-of object)))) (print-xml-tag tag out-stream tab) (mapc #’(lambda (slotname) (when (slot-boundp object slotname) (print-xml-tag slotname out-stream (+ 2 tab)) (case (slot-type object slotname) (:simple (tab-print (slot-value object slotname) out-stream 0 t)) (:object (fresh-line out-stream) (put-object-xml (slot-value object slotname) out-stream (+ 4 tab))) (:object-list (fresh-line out-stream) (mapc #’(lambda (obj) (put-object-xml obj out-stream (+ 4 tab))) (slot-value object slotname)))) ;; closing tag for each slot regardless of content (print-xml-end-tag slotname out-stream (+ 2 tab)) )) (set-difference (slot-names object) (not-saved object))) (print-xml-end-tag tag out-stream tab))) ; terminates object The two tag printing functions use format in a straightforward way. First, here is print-xml-tag for the opening tag. Given a tag, a stream, and a tab value (an integer), an XML tag is generated and printed after the appropriate number of blank spaces, as specified by the value of tab. A newline is always output afterward. (defun print-xml-tag (tag stream tab) (format stream "˜a˜%" (make-string tab :initial-element #\space) tag))

Chapter | 1 Biomedical Data

81

Next, here is print-xml-end-tag for the closing tag. Given a tag, a stream, and a tab value (an integer), an XML closing tag is generated and printed after the appropriate number of blank spaces, as specified by the value of tab. Here also, a newline is always output afterward. (defun print-xml-end-tag (tag stream tab) (format stream "˜a˜%" (make-string tab :initial-element #\space) tag)) These two functions are so similar that you could parametrize them and write just one: (defun make-xml-tag (tag stream tab &optional close) (format stream (if close "˜a˜%" "˜a˜%") (make-string tab :initial-element #\space) tag)) Then, you would just use this function in place of the other two tag-generating functions in put-object-xml and use the appropriate value for the close parameter in each case. Here is a convenience function analogous to put-all-objects. It opens a file named filename and iteratively calls put-object-xml on successive elements of the list object-list. If a file named filename already exists, a new version is created. (defun put-objects-xml (object-list filename) (with-open-file (stream filename :direction :output :if-exists :new-version) (dolist (obj object-list) (put-object-xml obj stream)))) This code does not write out tags with attributes, so it is very limited in terms of the mapping of CLOS objects to XML. Much more information about a CLOS object is available than just the slot names and values. How much of this is important will depend on the application. Insofar as most additional information is class level information rather than instance level information, it is kept with the class definition, not the serialized instances. Reading and parsing XML into data structures in a computer program is a much bigger programming job. Implementing an XML version of get-object would be an arduous task. However, the need for this is so widespread that there are now XML parsers for most programming languages, including Common Lisp. Several are open source, and some are incorporated with programming language compilers and systems. There are two more or less standard approaches for an API to an XML parser. Document Object Model (DOM) parsing reads the entire XML file and creates an instance of an XML DOM object. A DOM document is a tree-like structure that has components organized according to the tags, attributes, and components at the lowest syntactic level. An API for DOM provides accessor functions to get at the tags and their associated values, much as we illustrated for our list-structured tag architecture. First, your program calls the DOM parser function, then you examine the resulting object to do computations on it or its components. This is simple in that it completely separates the processing of XML syntax from the processing of the resulting data structure. It has the advantage that you can get arbitrary access to any element of the document in any order rather than having to deal with it serially, component by component. For looking up cross-references such as the GO example, this is very useful. A disadvantage is that the entire document must fit into the available memory address space; hence for large documents, performance could suffer if not enough physical memory is available. A standard document defining the DOM, its interfaces, and some language bindings is available at the W3C web site mentioned earlier.

82

PART | I Foundations of Biomedical Informatics

A simple API for XML (SAX) parser will read components and call back a function you provide to do whatever you want with each component. This approach is more complex in that your program has to have lots of logic to deal with whatever might come next in the data stream. It has the advantage that you can incorporate such logic as the data elements are read. This can be very useful when different things must happen depending on what data are input. It is particularly useful when dealing with data streams coming through a network connection rather than from reading a file. Unlike DOM, SAX is not a W3C standard. Its official web site as of this writing is http://www.saxproject.org/, and it is also affiliated with Sourceforge (http://sourceforge.net/). The DOM standard defines a language binding for the java programming language, not surprisingly, since DOM originated as a way to make java programs portable among various web browsers. However, the standard is abstract, and it is possible to define language bindings for other languages, including Common Lisp. We will develop here a small example of how to use the XML DOM parser provided with Allegro Common Lisp (ACL), a well-supported commercial Common Lisp programming system.42 This implementation defines a Common Lisp language binding for DOM. A document consists of a root node, a document object, and child nodes. The child nodes can be elements, corresponding to units that are enclosed by (and include) beginning and ending tags. A child node can also be a text node, which corresponds to a sequence of characters, a CDATA section node (containing uninterpreted data), or other node type. Nodes can have attributes as well as values and children. To illustrate this, the patient document example above would be represented as a document object, whose document element would have as its node name PATIENT, and it would (ignoring the ellipses) have three child nodes, corresponding to the three tagged fields.43 These three child nodes would be accessible as a list of element objects. Each element object corresponds to a tagged field. The element object may contain just text or it may in turn contain nested elements, so we have to examine the child node(s) to find its contents. In the patient example, the node name of the first element is NAME, and its value is actually contained in the child node list. In this case, there is one child node, and it is a text node. That node has the name "#text", and its value is in the node value slot since a text object cannot have any child nodes. If there were also some nested tagged elements, the list of child nodes for the NAME field would include text objects and element objects. If a tag has no attributes associated with it, its attribute list will be empty, otherwise it will contain a list of attribute nodes. An attribute node has in turn a name and a value (but no children). So, if everything worked as we just described, we could use the DOM API as follows. The function parse-to-dom takes a string or an open stream as input and returns a DOM instance. Let us suppose our patient record was contained in a file called dom-test-patient.txt, and we are using the interactive Lisp environment to explore. In order to use the Allegro DOM libraries, we need to use require to insure that code is present in the environment (the module name is :sax because both the DOM parser and the SAX parser are included in the same module), and we also arrange to use the package, whose name is :net.xml.dom so that we do not have to retype the package name every time. Then, we just open a stream and call the parser. > (require :sax) T > (use-package :net.xml.dom) T > (with-open-file (s "dom-test-patient.txt") (setq doc (parse-to-dom s))) # 42. Allegro CL™ is a product of Franz, Inc., Oakland, CA, USA. 43. Actually, there is a typographical problem which we will explain shortly.

Chapter | 1 Biomedical Data

83

The result is that the variable doc now has as its value a DOM document object. We can then look up things as described earlier. To print the text in each of the fields (elements), we would iterate over the list of elements, and for each, look up the child node and print its value. Note that all the values are text. There is no concept of the variety of data type representations that we have in printed values of lists, symbols, strings, numbers, etc. If the content of a text node is actually a number or a list, it needs to be further parsed, for example, using the Lisp function read-from-string. For this example, we will just define a generic function, print-dom-node, whose job is to print the text that is contained in a node, if any, or if the node is an element, look up its components and print those, or if it is a top level document, print its contents, the top level element. (defmethod print-dom-node ((node dom1-text)) (format t "Value: ˜A˜%" (dom-node-value node))) (defmethod print-dom-node ((node dom1-element)) (let ((name (dom-node-name node))) (format t "Element name: ˜A˜%" name) (mapcar #’print-dom-node (dom-child-node-list node)) (format t "End of ˜A˜%" name))) (defmethod print-dom-node ((node dom1-document)) (format t "DOCUMENT ") (print-dom-node (dom-document-element node))) When the print-dom-node function is called, it will examine the type of its input, determine which method is the most specific applicable method, and use that. Each of the above methods recursively calls print-dom-node, but, in general, the recursive call will use different methods depending on what kind of input is provided. For example, the method for a document object will provide a node of type element as input, so the method for element will then be used, etc. So, the generic function dispatch takes care of whatever the function finds as it traverses through the tree of nodes. This function only handles simple structures, but it can easily be generalized to apply to attribute processing and to other types of nodes. Of course, instead of printing to the display, the action taken could instead be to construct a class instance and put values in its slots. Here is the result of applying the function to a file containing the little patient example. > (print-dom-node doc) DOCUMENT Element name: PATIENT Value: Element name: NAME Value: Ira K End of NAME Value: Element name: HOSPITAL-ID Value: 99-2345-6 End of HOSPITAL-ID Value: Element name: AGE Value: 63

84

PART | I Foundations of Biomedical Informatics

End of AGE Value: End of PATIENT NIL It looks like it almost went according to our plans, but there is one strange problem. It appears there is some extra output before and after every element in our document. In fact, there is some text in between the tags ending one element and beginning the others. It is whitespace, that is, characters we usually ignore, such as blanks, tab characters, and newline characters. But, the XML standard does not specify that these should be ignored. There could certainly be a document element with some text and then an element with a tag, and then more text. This introduces a considerable complication. One way to avoid it is to take a strictly data-centric view and demand that such whitespace simply not be present. This makes the data unprintable. Another, perhaps more robust, way is to add a filter to the code above to ignore whitespace. In Chapter 4, Section 4.4, we will show how to do this in the context of querying PubMed for bibliographic data. You can imagine now how complicated it would be to write the analogue of the get-object function. Although put-object was easy, sorting through the DOM structure to get slot values into the right places, and particularly handling object valued slots, will be more difficult than it was for our simple representation with parentheses, symbols, and Lisp-style text representations. Which way is better? It depends on how much existing context is already committed to XML. It should be noted that a huge amount of effort in biomedical informatics is devoted to dealing with decisions that have already been made about data representation and storage. This is as true in the context of biomedical research data as in clinical and public health practice. Finally, it should be noted that several other projects in the Lisp community have as their goal to be able to translate between XML representations of data and their realization in programs as class instances. One noteworthy one is the XMLisp project [266]. The idea here is to extend Lisp to support X-expressions in which XML data elements are interpreted in terms of semantics like class definitions I described earlier (Section 1.2.3). Instead of having an intermediate structure like a DOM object, which then takes a lot of work to translate to and from class instances, XMLisp provides a more direct mapping. XML is intended only to be a “markup” language, a way to support somewhat self-describing or semi-structured data. As pointed out in an excellent book introducing XML [104], XML is not a programming language, and it is not a database system or database schema language. Although you cannot write a program in XML or even a complete data model, the extensions, RDF and OWL, used above in the GO excerpt, provide a substantial set of reserved keywords and associated semantics to define classes, instances, properties, and even rules. However, you will still need a translator that converts this representation into the appropriate constructs in a full programming environment. A program to apply the rules and perform operations on the collection of classes and instances is also necessary. Chapter 2 describes how such rule-based programs work and how they might be integrated with representations of classes and instances.

1.4 DATABASE SYSTEMS AND IDEAS Although the tag–value system described in Section 1.2.3 works well in some biomedical applications, often the regularity of structure of the data suggests that a more efficient system could be built. The problem of dealing with large and complex but regular data is sufficiently broadly important that an entire subfield of computing, the study of database systems, has developed to address it. The following are definitions of some useful terms in reference to database systems. Entity is a collection of data treated as a unit, for example, a radiologic image, a patient, a radiation beam, a laboratory test panel, an encounter record.

Chapter | 1 Biomedical Data

85

Relationship expresses associations between entities, for example, a particular radiologic image belongs to a particular patient. This is not the same as a relation, sometimes called table, which is specific to the relational data model and is described in Section 1.4.1. Schema is a description of the kinds of entities in a database and their relationships. A schema can include many interrelated tables or other structures (sometimes hundreds). Query specifies an operation on a database, resulting in a new collection of data, arranged in some way, possibly a new schema. Data model is a general framework for defining schemas and queries. Examples are the relational model and the object-oriented model. View is the result of a query (in the relational model a view is a table, so it can be the input to another query), but views are not stored in the database system; they are computed. Many different data models are in use, including the relational model, the object-oriented model, the (hybrid) object-relational model, the EAV model, the entity-relationship model, etc. In Section 1.2.2, we gave an illustration of object-oriented modeling with entity-relationship diagrams. A more elaborate treatment may be found in a new edition [25] of a classic text [283].

1.4.1 The Relational Model When data logically match the idea of many identically structured records with relatively simple structure or a collection of such structures, the most powerful model for describing, storing, and querying large data sets appears to be the relational database model [49, 55, 262]. So, much of the data used in business, education, government, and other organizations has this regularity that the relational model is the dominant model for database systems. Many products implement relational database systems, and a large number of applications are built with a relational database back end. In this section, we give only a brief sketch of the core ideas of relational databases. A more in-depth treatment can be found in textbooks devoted specifically to database systems [55, 71, 262]. The core idea of the relational model is that data are organized into a set of relations, often called tables, though strictly speaking a relation is not really a table. A relation is a collection (or set) of tuples. A tuple contains data about some entity and can be thought of as expressing a statement about it. The tuple consists of a set of values, each of which is associated with a particular attribute of the entity it describes. Thus, the relation idea is that this tuple relates the values together for the individual entity. A row in a relational table, as typically shown in database textbooks, displays the contents of a tuple. The columns correspond to the attribute values, and the column headers provide labels for the attributes. There is no significance to the order of the rows or columns, but the columns serve to identify which value in each tuple goes with which attribute. Each attribute has a data type associated with it, and all tuples must have values conforming to the specified type. While most databases have attributes that take on relatively primitive values, such as (small) integer, short character sequence (string), floating point number, etc., the relational model in the abstract supports structured types and other complex and user-defined types. A type specification just defines what are the allowed values, analogously to a type definition in a programming language. Since a relation specifies a set of allowable tuples that are valid for that relation, a relation itself defines a type, and so it is possible even for an attribute type to be a relation. This means in an informal sense that an attribute can have a table instance as a value. The distinction between variables and values that we made in describing a computer program also applies here. In a relational language, one can have variables, whose values may be individual tuples or sets of tuples. However, the values, that is, the tuples and sets of tuples, exist independently of whether they are assigned as values to variables. Furthermore, each tuple must be unique, that is, it must differ from every other tuple in the relation in at least one attribute value. This makes relations analogous to mathematical sets, in that each tuple has an identity determined by its values, and having the same element twice in a set does not

86

PART | I Foundations of Biomedical Informatics

TABLE 1.6 A Table for the Patients Relation Name

Hosp_ID

Tumor_site

Age

Joe Pancreas

11-22-33

Pancreas

38

Sam Vacuum

15-64-00

Glioblastoma

60

Sue Me Too

99-88-77

Left breast

45

David Duck

88-77-99

Pancreas

46

-6

Prostrate

62

Norbert Pivnick …

make any sense. To give a medical example, in a relation that contains laboratory tests performed on patients, we find a tuple that says a creatinine level was done on Jones from blood drawn at 9:40 AM on September 24, and the result was 1.04. There should only be one such entry. If the actual database (files or other storage) contains two tuples with the same set of values, it is a duplicate entry and a mistake was made. This is different from data collection in some scientific experiments where the identity of individual data points does not matter, duplicates are allowed, and the purpose of the experiment is in fact to count the number of occurrences of various combinations of values. An example of a table that might be found in a tumor registry database is shown in Table 1.6.44 Thus, a table is not a spreadsheet, which allows free access to values in any box representing a particular row and column. In a spreadsheet, the row numbers serve to index the rows, and similarly the column numbers index the columns. In a spreadsheet, anything can go in any box, and a single column can have different types of data in different rows. By contrast, tuples cannot be referred to by row and column numbers. They are referred to by content. One can, for example, look for all the tuples in which the Tumor_site attribute has the value “Brain,” or the Age attribute has a value less than 21. These operations are called restrictions. They are sometimes also called selections, implemented by the SELECT command of SQL. In addition to restriction, one can also collect values from a tuple, corresponding only to certain atttributes, rather than all. This operation applied to a set of tuples gives a new set that is a different relation, a projection of the first relation. In a relational database, a schema is a statement that describes a relation. It specifies the name of each attribute and its associated data type. It may specify many other properties as well. The standard data definition, manipulation, and query language for relational databases is SQL. It provides for creating, updating, searching tables, and forming new tables (views) from existing ones. Standard database textbooks cited earlier provide in-depth discussion about the implementation of database systems, particularly relational database systems. They also treat such questions as query optimization, the process of translating the user’s query into a form that is more efficient for the database system to execute than the original query.

A Brief Introduction to SQL SQL (for Structured Query Language) is the standard relational database programming language. Despite being called a “query” language, the standard includes a Data Definition Language (DDL), a Data Manipulation Language (DML), and a Query Language (QL). Other capabilities built into SQL include the ability to embed SQL statements in a conventional programming language like C or Lisp, 44. You may notice that there is a misspelling in this table, where someone has put in “Prostrate” instead of “Prostate.” This is deliberate on the part of the author to illustrate a point about data quality (see Section 1.5).

Chapter | 1 Biomedical Data

87

and also most implementations provide some way to do the converse, that is, to incorporate procedure calls in such languages into SQL statements. It provides statements for defining tables (relations) and statements for populating, updating, and querying them. The following illustrates the essential ideas. To define a table structure, one uses the CREATE TABLE construct. This is the core of the DDL. Here is an example. The Patients schema consists of a single table, described by the following: CREATE TABLE Patients (Name CHAR(20), Hosp_ID CHAR(10), Tumor_site CHAR(20), Age INTEGER) The name of the table follows the CREATE TABLE command; then within parentheses, separated by commas, is a sequence of attribute descriptors. Each attribute descriptor is required to have a name and type declaration. The table shown in Figure 1.6 is an excerpt from an instantiation of this table definition. To make changes to the table, we need a DML. Such tables are maintained by INSERT, DELETE, and UPDATE commands. The INSERT operator adds a new tuple to a relation. The name of the relation is needed along with the names of the attributes in some order and the values to be associated with each attribute (in the same order). INSERT INTO Patients (Name, Hosp_ID, Tumor_site, Age) VALUES (’A. Aardvark’,’00-12-98’,’Nasopharynx’,57) The Patients relation now has a new value, consisting of the original set of tuples plus one more. The DELETE operation does just the reverse, removing a specified tuple from the relation. In this case, we need some way to identify the tuple(s) to be deleted. This is done with a WHERE clause. This clause includes a logical condition to be tested against each tuple. If the condition is true, the tuple is deleted, but if not, it is left in. DELETE FROM Patients WHERE Name = ’I. Kalet’ In this example, it is unambiguous what the attribute Name refers to, but in cases where two or more tables are used in an operation, it will be necessary to use “qualified” attribute names. A qualified name consists of a prefix and a dot, followed by the attribute name. The prefix can be the name assigned to the relation by the CREATE TABLE operation, or it can be a local name associated with the relation, as in the following example. This example shows the use of the UPDATE operator, which uses a SET clause to update an attribute value for a tuple identified by a WHERE clause. UPDATE Patients P SET P.Hosp_ID = ’65-21-07’ WHERE P.Name = ’Norbert Pivnick’ A query consists of a specification of which columns, which table(s), and selection criteria to use. The query commands make up the query language. Generally, the result of a query is a new table, called a view. Views are not stored in the database, but they are temporary creations that are manipulated in an interactive context or in a program. The SELECT operator is used for queries. The format is that after the SELECT one provides a sequence of column labels, separated by commas, and qualified by a symbol that is a proxy for a table name (the P. in the following example). As before, the proxy name is not needed if the column name is unambiguous, that is, only one of the tables referenced contains a column of that name. Next, there is a FROM clause, associating table names with the proxy names, then the selection criteria (if any), specified by a WHERE clause. Here is an example on the Patients relation:

88

PART | I Foundations of Biomedical Informatics

SELECT P.Name,P.Age FROM Patients P WHERE P.Tumor_Site = ’Pancreas’ which gives the result shown in Table 1.7.

TABLE 1.7 A View Table that Results from a Query of the Patients Relation Name

Age

Joe Pancreas

38

David Duck

46

…

An extremely important property of the relational model is that queries on relations produce other relations, that is, the input to a query is one or more tables, and the output is another table. Thus, a relational database is closed under query operations. This makes nested queries possible, that is, the output of one query can be part of the input of another. Suppose we have another table with treatment records CREATE TABLE Treatments (Name CHAR(20), Treatment_Type CHAR(10), Dose INTEGER) and the table is populated as shown in Table 1.8.

TABLE 1.8 A Table of Treatment Records for Each Patient Name

Radiation type

Dose

Sam Vacuum

neutrons

960

Norbert Pivnick

neutrons

840

Sue Me Too

electrons

5040

Joe Pancreas

photons

6000

David Duck

photons

7000

…

Then, with this example, nested queries are possible. The following query would list all the patients and tumor sites that were treated with neutrons. SELECT P.Name,P.Tumor_Site FROM Patients P WHERE P.Name IN (SELECT T.Name FROM Treatments T WHERE T.Treatment_Type = ’Neutrons’) This query would produce the result shown in Table 1.9. Originally, SQL was intended to be a data manipulation “sublanguage” and did not have the full power of a “Turing-equivalent” programming language like Lisp, C, FORTRAN, or java. It provides a very powerful way to define data organization and to search and manipulate it as is most often needed

Chapter | 1 Biomedical Data

89

with database systems. The more recent SQL standard includes extensions that make it capable of arbitrary computations, but many problems remain [55, Chapter 4]. Most database management system implementations also include a way to embed SQL expressions in a regular programming language so that ultimately any computation may be done with the data.

Normalization Although it is required that each tuple in a relation should be unique, it may be that there are many ways to represent the data. Sometimes, the attributes in a relation are not really independent, but there are constraints between them. For example, if we were to represent lab tests of a patient in a table with the patient’s name, address, attending physician, diagnosis, and other information about the patient, every tuple will have something different about it, making it unique. Nevertheless, there will be significant redundancy in such a table. The patient’s address will (usually) be the same in every tuple for that patient, and other attributes will also be determined once the patient is determined. It would seem more efficient to split this information into two tables with links between them. Depending on the relationships among the data, there could be multiple levels of splitting that are possible. These different ways of handling dependencies between attributes are called normal forms. If a table satisifes the basic requirement that every tuple has some difference with every other tuple, it is said to be in first normal form (1NF). Every valid relation is in 1NF. The exceptions are the cases where the uniqueness constraint is violated, that is, there are duplicate tuples or where some attributes have missing values. The laboratory data example, illustrated in Table 1.10, has dependencies between attributes, so it can be reorganized into two separate tables. This process is called normalization.

TABLE 1.9 A View Table Resulting from a Nested Query Involving Both the Patients Relation and the Treatments Relation Name

Tumor_site

Sam Vacuum

Glioblastoma

Norbert Pivnick

Prostrate

…

TABLE 1.10 A Table with Attributes that Apparently have Dependencies Name

Birth Year

Diagnosis

Test name

Result

Date of Test

Joe Pancreas

1967

Pancreatic Ca.

Creatinine

1.7

24-May-2004

David Duck

1954

Prostate Ca.

PSA

14.3

29-May-2004

Joe Pancreas

1967

Pancreatic Ca.

Creatinine

1.3

2-Jun-2004

Joe Pancreas

1967

Pancreatic Ca.

Creatinine

1.6

19-Jun-2004

David Duck

1954

Prostate Ca.

PSA

16.1

23-Jun-2004

David Duck

1954

Prostate Ca.

PSA

0.4

9-Aug-2004

…

90

PART | I Foundations of Biomedical Informatics

The Name, Birth Year, and Diagnosis all appear to be related. One might think of splitting this into two tables, one with just those fields and the other with all the lab test data, together with just enough information to tie each lab test back to the right individual. In reality, the name is not enough, but such tables often have many attributes, a few of which together serve to identify the patient. So, one relation would have the Name, Birth Year, and Diagnosis and the other would have the Name, Test name, Result, and Date of Test. This more highly normalized arrangement would avoid the redundant repetition of the Birth Date and Diagnosis information. In the original arrangement, if this data had to be re-entered manually with each new lab test, typing errors would certainly occur and would be extremely hard to find and correct. One effect of such errors would be that important records would not be retrievable.

Constraints and Keys A reasonable database system would support ways of insuring that the data stored in it are consistent with the schemas and also allow for additional constraints to be specified where needed. Already we have enforceable constraints on elements that can be in each column because we have included type specifications in the table definitions. These can be enforced by the data entry facilities. In addition, as noted earlier, no two rows (tuples) in a table can be identical, that is, each pair of tuples must differ in the value of at least one column or attribute. Further constraints can be specified in SQL, called key constraints, by defining one or more fields in a relation to have the property of being a key. If the relation is at least in 1NF, that is, satisfies the requirement of each tuple being unique, there is always some combination of attributes that can be used as a key, that is, the key uniquely specifies a single tuple. The worst case, of course, is that the entire tuple is the key. More often, a single attribute will suffice to identify the record, or a combination of two or three will do it. There may even be more than one choice of attribute that serves as a key. In the following example, the hospital ID (or medical record number), which is the attribute labeled Hosp_ID, is identified as a key by declaring it UNIQUE, that is, in the Patients table, no two records will have the same value for the Hosp_ID field. CREATE TABLE Patients (Name CHAR(20), Hosp_ID CHAR(10), Tumor_site CHAR(20), Dose INTEGER, UNIQUE (Hosp_ID)) It is possible to choose one key and designate it the primary key. This helps the database system optimize queries, for example, by generating an index. In order to relate one table to another, we can also designate an attribute or combination to be a Foreign key. This attribute is then considered a link to connect information from one table to that in another table, for example, for the Treatments table, a better design would be CREATE TABLE Treatments (Hosp_ID CHAR(10), Treatment_Type CHAR(10), PRIMARY KEY (Hosp_ID), FOREIGN KEY (Hosp_ID) REFERENCES Patients) The ability to combine tables to generate new ones as well as use restrictions and projections makes the relational model very powerful. All the description so far is really a description of the abstract logic of relations and does not imply anything about the actual implementation. How the data are stored in files and actually represented in memory, and whether a query is processed directly in some obvious way or transformed first into an equivalent but more efficient form, are all details that the end user normally would not be aware of.

Relational Algebra We already showed the selection operation, which picks some subset of rows from a relation. This can be thought of and noted formally as a function on a relation that returns another relation. The Greek

Chapter | 1 Biomedical Data

91

letter σ is used to denote a selection operation. The selection operation σ Tumor_site=Pancreas (P ), where the symbol P refers to the Patients table, does part of the job of the SELECT operation example shown earlier. The other part of that operation is to only display two of the columns, not the entire set of columns. That is a projection operator. The projection operation picks a subset of columns (fields). So, the SQL SELECT operator can do just a projection, by not specifying a WHERE clause. Projection is denoted by the Greek letter π, so the projection in the same example as above would be πName,Age (P2), where P2 is the result of the selection operator above. Thus, the SQL query would be rewritten as π Name,Age (σTumor_site=Pancreas (P )). Often the information we need is a combination of data from two or more tables, rather than a single table. We need operations to combine tables into bigger tables and then to select and project from those. A cross product forms a new composite table from two other tables – for every combination of an element from one with an element of the second, there is a row in the cross product. The cross product is denoted by the symbol ×. This does not usually get us exactly what we need. In the cross-product table, there may be repeated columns; if the two tables have a column in common, that is, the same kind of data appears in each, we only want to link up the rows in which the data correspond, that is, the contents from one table in its column are the same as the contents of the other table. For example, we combine two tables that each have patient names. We want only the cross-product records where the name field from the first table is the same as the name field in the second table. So, we can do a selection on that basis and then a projection that just leaves out the now duplicate column. A join is a cross product followed by a selection and /or projection operator. The symbol for a join is . A common kind of join, which accomplishes what is described in the previous paragraph, selects rows in which fields with the same (field) name are equal. In that case, the two equal columns are condensed to a single column, that is, the selection is followed by a projection. So, Patients joined with Treatments gives a table where the Radiation type and Dose fields are added on for each patient for which there is a record in both tables. The result of such a join looks like Table 1.11. This “natural join” can be expressed in relational algebra as Patients  Treatments. Since no condition for selection or projection is specified, the two columns whose names match are taken to be the ones where equal fields select the rows, and the columns are then condensed to one. Other operations on tables are possible, such as set union, intersection, and others. Standard database texts such as [55, 71, 262] develop all these ideas in more depth. A motivation for expressing schemas and queries in relational algebra is that complex queries can be transformed into equivalent queries that may realize huge efficiency gains. This is a subject for database system design. A well-designed system will need a way to take a schema and create an implementation, some efficient way to store the data and maintain appropriate indexing of records for fast search and retrieval. A query interpreter is needed to translate SQL (or some other query language) into basic operators that can be implemented in the system. A query optimizer then looks at the operations requested to see if the query can be reorganized

TABLE 1.11 A Table Showing Both Tumor site and Treatment for Each Patient, the Result of the Natural Join, Patients  Treatments Name

Hosp_ID

Tumor_site

Age

Sam Vacuum

15-64-00

Glioblastoma

60

neutrons

960

Sue Me Too

99-88-77

Lt. breast

45

electrons

5040

-6

Prostrate

62

neutrons

840

Norbert Pivnick …

Radiation_type

Dose

92

PART | I Foundations of Biomedical Informatics

to a more efficient form, for example, by changing the order of selection operations or by handling rows in groups rather than one by one. Finally, an efficient execution engine will perform the optimized query using the index and other facilities available in the system.

The Catalog, Metadata, and Object-oriented Databases Our exploration of the use of CLOS MOP to serialize data showed that programs can be used as data to generalize operations on the data that the programs describe. This is kind of how a database system works as well. The SQL CREATE TABLE expressions are code in an SQL program, but they can also serve the same meta-object role as the CLOS class definitions. They describe the structures of relations. Database implementations would convert the text of such statements into an internal form that can be used to interpret further SQL operations and tuple data. This information is itself stored in a relation (or set of relations) called the catalog, sometimes also called the data dictionary. The point here is that a relational database is typically built on its own machinery, much as CLOS is built using CLOS classes and methods. One implication of this is that one could write a program to create a database schema from a class model in a programming language if the class descriptions were available. It might seem that this way you could add persistence or non-volatile storage to a programming environment like Common Lisp. There are systems that augment Common Lisp to provide persistent objects, essentially an objectoriented database, but they do not use a relational database as a back-end storage or implementation scheme. Instead, they use the MOP to implement an object-oriented database model more directly. An example is the AllegroCacheTM system from Franz, Inc., which is an extension of ACL to provide object-oriented database capabilities. This approach comes at the problem from the opposite end of the database field, where relational database technology and SQL have been extended to incorporate ideas from general purpose and object-oriented programming. The work on object-oriented databases in the Lisp environment emphasizes extending the programming environment to support persistence for program data, so there is no issue of an object-oriented query language. The Lisp programmer just writes Lisp code in the usual way to manipulate persistent data just the same as transient data. In Chapter 2, we develop the idea of frames as an abstract modeling method. Frames are an extension of the idea of classes in object-oriented design. It is possible to create (and even somewhat automate) a mapping from a frame-based model of data and knowledge to an implementation as a relational database schema. Maya Hao Li has investigated this in the context of providing support for building and maintaining customized laboratory data management systems [191].

1.4.2 The Entity–Attribute–Value Model We consider one more flexible approach related to the tagged data idea, the Entity–Attribute–Value (EAV) database. In this model, every piece of data is in the same form, a triple, in which the three elements are: a reference to some object, the name of an attribute of that object, and the value associated with that attribute. The value could possibly be a reference to another object, or it could be a basic datum (a number, a string or other elementary datum). Some attributes may have multiple values, for example, PSA test results, in which case there will be multiple EAV triples, one for each test result. Here are some examples, just written as three element lists: (patient-6 creatinine 1.2) (radiation-beam-3 gantry-angle 45.0) A value could be another entity, as in (patient-6 treatment radiation-beam-3) This could be represented in a relational database as a simple three-column table. The efficiency is offset by the complexity of queries, some of which may not be possible in SQL. Nevertheless,

Chapter | 1 Biomedical Data

93

such systems are used as the basis for some EMR implementations, notable the MIND system at the University of Washington. In some hospital IT settings, this model is also called the vertical model because a graphical display of the data when extracted by a simple SQL query runs vertically down the page, row after row, rather than horizontally across the page, column after column. EAV modeling in production databases is commonly seen in clinical data repositories, with such areas as clinical findings, clinical procedures, etc.

1.5 DATA QUALITY All the discussion to this point somewhat implicitly assumes that the data contained in the various long-term storage schemes are of high quality, that is, there are no misspellings of names of patients, diseases, or other text strings. By now, you will have noticed that in Figure 1.6, the term “Prostate” is misspelled as “Prostrate,” which is a position, not a disease or an organ. This typographical error then propagates to views, as in Figures 1.7 and 1.11. This kind of error often happens when the data entry is done by typing into a text field in a computerized form. One problem with this is that the record will not turn up or be counted in a search, for example, for all patients with prostate cancer. To alleviate the data entry problem, large “controlled vocabularies” have been built to standardize the terminology that people use in recording medical information. Another strategy for reducing such errors is to provide structured data entry facilities, that is, choosing from menus rather than typing in a word or phrase that is part of a standardized vocabulary. The complexity of biological and medical data makes this a challenging design problem. Especially in the context of medical practice, time pressure on the provider actually favors traditional dictation and transcription rather than direct data entry. In many circumstances, data are already available in computerized form and can be transmitted from system to system. An example that has been available for a long time is the planning and delivery of radiation therapy (see Chapter 9 for more background). For many decades, it has been possible to create a plan for radiation treatment of tumors using a computer simulation system. The system displays cross-sectional images of the patient and also can display the radiation pattern produced by the treatment machinery. The planner, called a “dosimetrist,” uses interactive controls on the display to position the radiation beams. When the plan is completed, it can be written on tape, disk, or other media, or transmitted over a computer network to a computer-controlled radiation treatment machine. In the early days of such facilities, the radiation therapist was required to enter the machine settings from a printed sheet produced by the planning computer. The computerized version of the settings was used by what was called a “Record and Verify” system to have the machine check if the therapist entered the data correctly. In my opinion (loudly expressed at the time, early to mid-1980s), this is exactly backward. The computerized data and network connection have the potential to save time and improve reliability. The role of the radiation therapist should be to check that the machines are operating correctly, and not for the machines to check the humans. Fortunately, this view prevailed, and current practice is to use a network protocol (DICOM, described in Chapter 8) to transfer the data, to have the operators (dosimetrist and therapist) provide the quality assurance of human oversight, and to insure that the machines are set up properly. Electronic medical record systems store data in eclectic ways, depending on the medical software vendor. One system uses B-trees, another uses an EAV model, and yet another uses an RDB schema. When data are put into such systems, either by HL7 messages or a data-entry facility, some conversion is necessary, just as for the medical digital image data described in Section 1.1.5. The DICOM standard, described in Chapter 8, goes a long way towards mitigating this problem, at least for digital image data, radiology reports, and radiation treatment data, by providing a common data model, but the actual details of how the data are stored, retrieved, and managed within a particular system is strictly a proprietary matter unique to that system. For display purposes, when a medical practitioner looks up information on a patient, the presentation is controlled by tables that specify what appears on the screen. These tables can be very large. In a

94

PART | I Foundations of Biomedical Informatics

typical table, there are entries for each possible laboratory test or group of tests, for example. The way in which tests are classified is not standard, but it is up to each hospital or clinic to create the tables specifying how the data are to be handled. The motivation behind the LOINC naming system described in Section 1.1.4 is to have a common set of test names and definitions. Despite the widespread use of LOINC, problems can still occur. One of the most challenging is to maintain consistency when updates occur. MINDscape [324] is a web-based system that integrates access to various clinical data sources at the University of Washington Medical Center and related practice sites. Its back-end system, MIND, builds tables of test names dynamically, with caching. The first time a test is displayed, the (vendor system supplied) name is cached. It is not subsequently updated when changes occur. Normally, these names do not change, but on one occasion, a test was displayed with the name “HTLV 1” when the result should have been labeled “HTLV 1 + 2.” The original entry apparently was realized to be incorrect and was changed, but the update did not get into the cached table. Configuration tables in electronic medical record systems (that are used to generate displays of results and other information) have evolved over time and are not generally the result of systematic software development. Sometimes, vendor-supplied enhancements to such tables will conflict with local enhancements installed by the system users at a particular hospital. Coordination of configurations between different software components and systems presents additional challenges. Much remains to be done. Another consistency problem is implied by the table examples in Section 1.4. A spelling error in a person’s name may be discovered and corrected in one place, but by the time such errors are discovered, often many copies of the information have propagated to other systems. For example, when a CT image data set is transmitted from the Radiology PACS (picture archiving and communications system, a large-scale online storage system for medical image data) to the Radiation Therapy Department’s radiation treatment planning systems, the data must be matched with other data for that patient. The matching must rely on the patient’s name, medical record number, and possibly other information. Such matching algorithms will make errors when there are spelling mismatches. This problem is difficult to solve because no matter how loud the cry for one vendor to provide all the medical computing applications for an institution, it is clearly a naive wish that ignores the complexity of medical practice. There will always be many vendors for all the huge variety of medical equipment and systems, including radiology imaging systems, infusion pumps, radiation treatment machines, anesthesia monitoring systems, vital signs monitors, etc., not to mention the imaginary central repository, the electronic medical record. The problem of managing context, that is, accessing multiple systems for data on the same patient, has given rise to software products and attempts at standards, such as CCOW (Clinical Context Object Workgroup). This group is a part of the HL7 standardization effort. Although products exist that are in compliance with this standard and leverage compliance to present an appearance of seamless integration, they are more at the level of providing a cover over what remains a pretty messy situation. In addition to managing consistency of identifiers for patients, there is a related issue of managing user access credentials and authorization of users of all these different systems. Another popular wish is for “Single Sign On” (SSO). The goal of SSO is that a user presents credentials such as a login ID and password (and perhaps additional authentication such as “SecurID”), at the user’s desktop, and then it is passed through or otherwise managed by the SSO layer so that the user does not have to repeatedly authenticate with each application. This requires synchronization of credentials and authorization among many applications, not an easy task. Systems for SSO exist, but, again, they tend to take a “sweep the trouble under the rug” approach, rather than really solving the underlying problem. Finally, looking ahead to the problem of creating large-scale knowledge systems in addition to data systems raises the question of whether the knowledge, facts and ideas, terminology, etc. are consistent with each other. The FMA, mentioned earlier, is a collection of millions of facts about human anatomy. We know that anatomic entities satisfy constraints and are not arbitrarily interconnected. For example, lymphatic vessels have as part of their description the names of other lymphatic vessels, which are

Chapter | 1 Biomedical Data

95

downstream and upstream. The upstream vessels should always be other lymphatic vessels, never arteries or veins, and never other kinds of organs or tissues. The downstream vessels are similarly constrained, with two exceptions, the thoracic duct and the right lymphatic duct, which connect to veins, as they are the terminal elements or trunks of the two lymphatic trees that make up the lymphatic system. Another constraint is that every lymphatic vessel, by following the downstream relation, should reach one of the two mentioned above, that is, there are no lymphatic vessels that are not part of the two trees. Such requirements can be formulated as constraints, and a construct like the FMA can be automatically checked by a computer program making queries and tracing the data. This will be further developed in Chapter 6. Another example of the possibility of automated data quality checking is in systems like EcoCyc [161, 163, 164]. EcoCyc has a representation of biological molecules, biochemical reactions, and pathways that consist of linked reactions. The molecule entries include information about how many of each type of atom are in the molecule. The reactions include details of how many of each molecule participate in the reaction as reactants and how many of each of the products are produced. In effect, the information usually found in a chemical reaction equation is stored. It is, therefore, possible to check each reaction to determine if the number of each type of atom is balanced on the left side and the right side of the reaction. This is the requirement of stoichometry. It is a useful quality check to identify possible data entry errors when creating such large-scale information resources. Terminology systems that are the basis for standards like HL7 as well as medical terminology systems such as the System of Nomenclature for Medicine (SNOMED) [280] and the Unified Medical Language System (UMLS) [26, 228] also can be examined to determine if they meet reasonable constraints [45]. Many misclassifications or anomalies exist. Such misclassifications can have serious consequences when these systems reach the point where they are relied on in a clinical application. The HL7 Version 3 Reference Information Model (RIM) has been the subject of much criticism [307, 308] because it systematically misclassifies many entities of different types as if they were the same types. Even HL7 Version 2 has problems with inconsistencies in the formal descriptions of messages and other problems that stem from allowing the use of arbitrary terminology and labeling systems. The implementors (meaning the installers, not the software developers) of HL7 message routing systems must somehow resolve all these discrepancies, which are often undocumented and must be discovered by actually looking at data streams to determine what a system is actually sending.

1.6 DATA, INFORMATION AND KNOWLEDGE Before leaving the subject of biomedical data, it is worth considering how the terms, “data,” “information,” and “knowledge” are used. In the next chapters, we will show how to encode biomedical knowledge and compute with it. Is knowledge different from data? What about the seemingly broader term, “information”? In distinguishing among the commonly used terms, “data,” “information,” and “knowledge,” the dictionary is not of much help. The Random House Dictionary of the English Language [313] defines “data” as “facts, information, statistics or the like, either historical or derived by calculation or experimentation.” It does, however, also offer the definition from philosophy, “any fact assumed to be a matter from direct observation,” which seems to exclude the derivation by calculation. “Information, on the other hand, is defined as “knowledge communicated or received concerning a particular fact or circumstance.” The words “data” and “facts” are presented as synonyms for “information.” The entry for “information” distinguishes between information as unorganized and knowledge as organized. The dictionary defines “knowledge” as “acquaintance with facts…” and suggests that “information” is a synonym. An additional complication is that the term “information” is indeed used in the sense of communication of data or knowledge, as in Information Theory. This is the quantitative study of how data are transmitted and received through communication channels, accounting for noise, redundancy,

96

PART | I Foundations of Biomedical Informatics

synchronization, and other matters. Two good elementary introductions to this subject are the reprints of the original pioneering work of Claude Shannon [297] and a very entertaining treatment for the layman by John R. Pierce [255]. A message containing a large amount of data can be transmitted, but it may not convey a large amount of information. The idea here of information is that a message contains information when the content is not known in advance. The amount of information the message conveys is related to the amount by which the unknown is reduced. If the only messages that can be conveyed are “yes” and “no,” the message is said to convey one bit of information. When there are many more possibilities, the message will contain more information. This has some relevance in biology, and is being pursued by some researchers [3]. The related concept of “entropy” is used in medical image registration, pattern matching, and optimization [325, 326]. For our purposes, we use the convention that “data” refers to matters of direct observation of specific instances or computed assertions about those specific instances. So, blood test results such as glucose level, red blood cell counts, etc. for a blood sample from a patient are data. We will usually use “facts” as a synonym for “data.” We reserve the term “knowledge” to refer to statements that are true of classes of individuals, or what we might also call “general principles.” So, a general principle, or chunk of knowledge, might be that, in general, the drug heparin prevents clotting of blood. Together with some facts about an individual, these chunks of knowledge can be applied to derive new facts by logic or other calculations. When there are enough chunks of knowledge to provide a comprehensive and internally consistent representation of a biological system or process or entity, we call that collection a “theory.” What about information? The dictionary seems to suggest that unorganized information is data, and organized information is knowledge. This neither distinguishes between information about individuals versus information about general principles, nor does it address information as a way to quantify communication (Information Theory). We will use the term “information” in all those ways, but only where the context makes it clear what is meant. We will see that similar ideas about looking up information will apply to both data and knowledge in various forms. So, although one might imagine a progression from data to information to knowledge as shown in Figure 1.20, in reality the progression is 2D, from unorganized to organized, and from particular instances to general laws and principles, as shown in Figure 1.21. The general laws and organized information can be used to infer more facts, and possibly to discover further general laws. Data are the means by which we test theories, and also the source of insights and patterns from which we might guess theories. This is the activity of the theoretical side of scientific research. In clinical practice, too, one can see the same process. For example, we start with some facts from a medical record. Patient X has an adenoid cystic carcinoma (a kind of cancer) in the nasal cavity,

Knowledge

FIGURE 1.20 A diagrammatic illustration of the progression from data to information to knowledge.

Information

Data

FIGURE 1.21 A 2D view of data, information, and knowledge.

Organized Unorganized

Structured data

Biomedical theories

Raw data (Facts)

Unstructured knowledge

Specific

General

Chapter | 1 Biomedical Data

97

behind the nasal vestibule, between the upper left turbinate and the nasal bone. This is information (data) about patient X. We know that this location is drained by the submandibular lymph nodes and the retropharyngeal lymph nodes. This is knowledge, because it is true in general about human anatomy, not just for a particular patient. But, it can be applied to this patient to suggest that these two nodes are at risk for metastatic disease and should be treated with therapeutic irradiation. So, the combination of data and knowledge leads to more data and a useful clinical insight. The process of medical diagnosis can also be seen as an application of knowledge to data and a stepwise theory refinement. In both diagnosis and treatment planning, instead of trying to construct a theory of biomedical or pathological processes in general, the physician is constructing a theory for a particular patient at a particular time. This is referred to as the hypothetical-deductive approach [300, pp. 53–54]. Some early medical expert systems were designed along these lines. This neat distinction, while useful, is not so rigid as one might surmise. Consider the FMA [279] described in more detail in Chapter 6. It is an ontology, a collection of terms naming the entities in the human body and links naming the relationships between them. The intent of the authors of the FMA is to represent as precisely as possible what is known about human anatomy. To a student learning anatomy by browsing the FMA, it is a collection of information to be understood and perhaps to some extent memorized. To a software designer, the terms and links may be considered data that are subject to search and manipulation by a computer program. To a biological scientist, it is a formal theory of human body structure. The difference in labeling the contents of the FMA are really about different uses of the same things. As long as the meaning, structure, and intended use are clear, we will not worry too much about the labels, “data,” “information,” and “knowledge.”

1.7 SUMMARY Some essential ideas come out of our exploration of how to represent and manipulate biomedical data in a computer: ●

●

●

●

●

Biomedical data are heterogeneous, highly variable in size as well as type and structure, but from molecules to humans to populations, there are some common themes. Biomedical data are symbolic and structured, not just numbers and text. Programming languages designed to handle symbols and structures (e.g., Lisp) help in working with such data. Self-describing data (and use of metadata) organization strategies can pay off in simplifying access and storage. These methods also provide flexibility and robustness in the face of change. When raw speed is needed, for example, for medical images and large sequences, special techniques are appropriate, but abstraction is still important. When dealing with generic descriptive data rather than characteristics of individuals, the distinction between data and knowledge is less clear.

In addition, we saw that the Lisp programming language provides strong capabilities for handling biomedical data. We will see in the next chapter that these same capabilities are powerful tools for handling knowledge as well as data. Special features of Lisp that are particularly important are: ● ● ●

data, not variables, have types, lisp supports symbols and lists, functions and other code (e.g., class definitions) are also data, making possible the use of metadata.

In the next chapter, we make the transition from data to knowledge, along the dimension described, from the particular (data) to the general (knowledge) and then examine how to combine data and knowledge in the solution of biomedical problems.

Chapter 2

Symbolic Biomedical Knowledge 2.1 Biomedical Theories and Computer Programs 2.1.1 A World Class Reasoning Example 2.1.2 Biological Examples 2.1.3 Symbolic Theories 2.2 Logic and Inference Systems 2.2.1 Predicate Calculus 2.2.2 Unsound Inference: Abduction and Induction 2.2.3 First Order Logic 2.2.4 Rule-based Programming for FOL 2.2.5 Limitations of FOL 2.3 Frames, Semantic Nets, and Ontologies 2.3.1 A Simple Frame System 2.3.2 Extensions to Frame Systems 2.3.3 Frame System Implementations, Interfaces, and APIs 2.3.4 Frames and Object-oriented Programming Languages 2.4 Description Logics 2.4.1 Description Logic Languages 2.4.2 Examples from GALEN 2.4.3 The Semantic Web 2.4.4 Back to the Future 2.5 Search 2.5.1 A General Framework for Search 2.5.2 Uninformed Search Strategies 2.5.3 Informed Search Strategies 2.5.4 Path Search 2.6 Summary

A little knowledge is a dangerous thing. – Alexander Pope An Essay on Criticism

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

99

100

PART | I Foundations of Biomedical Informatics

In Chapter 1, we distinguished between data and knowledge by reserving the term “knowledge” for general principles and assertions about classes or categories rather than individuals. The power of such general principles comes from their compactness. A few general principles may be sufficient to infer, calculate, or derive a huge range of assertions that are entailed by these principles. The derivation of a particular result may involve a lot of computation, but it is done only when needed. Precomputing all possible results (or, alternatively, doing experiments to observe, record, and catalog all possible facts) is usually (although not always) out of question. Even when it is possible, it raises substantial questions about indexing and retrieval, some of which will be addressed in Chapter 4. A second important aspect of representing knowledge in the form of general principles is that one may take the view that the principles are descriptive, that is, they are not just a compact summary of the facts of the world but statements about how the world really works. These two points of view were espoused by two very prominent scientists. Ernst Mach held that the theories (equations and formulas) of physics were powerful and compact summaries of all known observed data of the physical world, and nothing more.1 Albert Einstein, on the other hand, took the view that the theories were approximate descriptions of how the world really works.2 This is a substantial point of discussion among biologists and medical scientists. One example is the study of biomedical pathways (e.g., for metabolism). One view of pathways is that they do not exist as such but are only convenient constructs to organize information about biochemical reactions. Others may take the view that such pathways represent fundamental principles of operation of living cells and organisms. Both views have a place in biomedical informatics. In fact, three views of knowledge representation are possible. One is the view of Mach, which is knowledge representation as information management. If the focus is on organizing what is known (or believed) for efficient retrieval and communication, it may be acceptable to have contradictory assertions in the knowledge repository.3 The human users of such systems would make judgments about what to do in cases of conflicting information. Information retrieval (IR) is dealt with in more depth in Chapter 4. A second view, which will extensively be developed here, is that of knowledge representation ideas and methods as the basis for constructing biomedical theories. In this context, a particular theory must be constructed free from contradictions in order to be able to unambiguously determine the predictions of the theory. When there are competing ideas, we construct multiple theories and separately compute their predictions. The experimental facts will ultimately decide which theory is right (of course both may be wrong). Finally, there is the view of knowledge representation as a model of human activity or human intelligence, that is, modeling what people believe or do. This is the point of view of much research in the field of artificial intelligence (AI). The goal is to understand the nature of intelligent thinking, not so much to create a model of the world of things. The only area in this book where we address this is Chapter 3, where we present decision modeling that incorporates preferences and beliefs rather than truths about biomedical entities and relationships. Thus, in this chapter, rather than settling this philosophical debate, we will develop the ideas, methods, and formalisms from which biomedical theories may be constructed. This in turn provides the foundation on which many applications described in Part II of this book have been built. Logic is at the base of the rest of the formalisms that are widely used today, and so it is the first topic to be developed here. Biomedical knowledge also involves cataloging and describing relations between categories, and so systems for representing categories and relations come next, in particular semantic nets, frame formalisms, and description logics. Since so much of biomedical computation involves traversing graphs, implicitly or explicitly, the final topic is methods for search of knowledge networks or graphs.

1. A succinct summary of Mach’s ideas may be found in an article in Wikipedia under his name. 2. See, for example [68] which has been reprinted in several anthologies of Einstein’s essays, including [69] and [70]. 3. Mach would not likely have accepted this view. Like other physicists, he saw that the compactness of the representation depends on the ability to infer or compute things from the basic knowledge rather than enumerate all the facts; thus consistency would be critical.

Chapter | 2 Symbolic Biomedical Knowledge

101

2.1 BIOMEDICAL THEORIES AND COMPUTER PROGRAMS Formally speaking, a theory is a set of statements called “principles” or “axioms” and a reasoning method from which one can infer new statements from the principles or axioms, given specific assertions or facts about a particular case. In sufficiently rich theories, one may also infer general statements that are consequences of the axioms. Such derived generalities are called “theorems” in mathematical context. These in turn can be applied to specific cases just as if they were axioms. The language in which the statements are expressed is characteristic of the topic or domain. In physics, algebraic symbols are used to represent variables or elements of the theory, since their values may vary with time and position. A frame of reference is needed to relate the symbols to things we see or experience. The axioms or laws are represented by equations that relate quantities to other quantities. The methods of algebra, geometry, calculus, and higher mathematics can then be used to manipulate the equations using some particular values for the symbols and arrive at other values.

2.1.1 A World Class Reasoning Example A remarkable example of the power of mathematics and reasoning is the method by which Eratosthenes determined the circumference of the earth [235, Volume 1, pp. 206–208]. Figure 2.1 shows the geometric and physical picture from which the reasoning follows. The diagram shows the sun’s rays striking the earth (vertical lines) at Syene and Alexandria in Egypt. The angles a and b are equal, and measured in Alexandria (b) to be about 7◦ . The argument of Eratosthenes is as follows: 1. 2. 3. 4.

Axiom: Light from the sun comes to the earth in parallel rays. Axiom: The earth is round (remember, this discovery took place around 200 B.C.E.). Fact: At noon in the summer, sundials cast no shadow in Syene (in Egypt). Fact: At noon in the summer, sundials do cast a shadow in Alexandria (also in Egypt), about 7◦ off of vertical. 5. Fact: The distance from Alexandria to Syene is about 4,900 stadia (a stadion is an ancient unit of distance, roughly corresponding to about 160 to 180 m). By Euclidean geometry, the angle subtended by the arc from Alexandria to Syene (as measured from the center of the earth) is the same as the angle of the sun from vertical (by a theorem from Euclidean geometry: when a line intersects parallel lines, corresponding angles are equal). So, the distance from Alexandria to Syene represents about 7◦ of arc length, from which Eratosthenes calculated about 700 stadia per degree. Then, since a full circle is 360◦ , the circumference of the earth is simply 700 × 360 or about 252,000 stadia. The size Eratosthenes used for a stadion is not known exactly. Eratosthenes’ result was somewhere between 39,690 and 46,620 km. The current best value is about 40,000 km. FIGURE 2.1 Diagram showing how Eratosthenes calculated the circumference of the earth.

Sun

b

Syene

Alexandria

a

Earth

102

PART | I Foundations of Biomedical Informatics

What would it take to represent the reasoning of Eratosthenes in a computer program? Certainly, the arithmetic is easy. What about the logic that led to the right arithmetic formula? That requires a computer program to implement symbols representing the propositions, methods for combining the symbols in abstract formulas, and finally a proof method to derive the final formula (i.e., deriving theorems or results from axioms and other assertions). Of course, the earth’s surface is not exactly a perfect circle, and the light from the sun does not exactly travel to earth in parallel rays. This calculation nevertheless is close enough to reality in order to be useful. Success in science depends not only on accuracy of measurements, but also on making the right approximations and being able to create abstractions that leave out unimportant details. In addition, it is critical to apply the abstractions using sound reasoning and in a consistent way. Ignoring sound reasoning requirements can not only lead to results that are somewhat inaccurate but also to results that are just plain contradictory and, therefore, patently false. Lots of good traditional examples of paradoxical and unsound reasoning may be found in [166], as well as in [167].

2.1.2 Biological Examples Physiological systems can be described by mathematical variables, and the general knowledge about such systems as equations and the solutions of those equations for a particular individual case may be compared to measurements for that case. The measurements are the data; the formulas or equations are the knowledge. However, as we saw in Chapter 1, much of what we know in biology and medicine is not quantitative, as it is for the subfield of physiology. Even in biochemistry, where we might also have equations relating concentrations of biochemical compounds, often the form of the equations is unknown or the rate constants are unknown. Nevertheless, what is known is that certain molecules react with certain other molecules in various ways, that is, we know the reactants (sometimes called substrates), products, and catalysts but not the numerical details. Is this useful? It turns out that catalogs of such reactions and indeed whole biochemical pathways are very useful for answering important biological questions. For example, the EcoCyc knowledge base [161] contains the complete metabolic pathways of the Escherichia coli organism in symbolic form. Figure 2.2 shows an example pathway, glycolysis, which transforms glucose to pyruvate. Such a collection of pathway representations can answer a question: “Can E. coli grow in a medium consisting of the following materials…?” It is a graph search problem. Are there pathways that start with the given nutrients and end (individually or in combination) with all the necessary compounds for the organism to build proteins, etc. to survive? In Chapter 5, we develop this idea in detail.

2.1.3 Symbolic Theories The variables in some theories thus take on discrete values rather than continuous ones, or sometimes just one of the values “true” and “false.” Functions can also have discrete values in their range as well as their domain. If a function’s range is the set consisting only of the values “true” and “false,” it is called a predicate function, or simply predicate. We can still write relations between these variables, functions, and values, and in some sense solve the “equations” that we write as the axioms of our theory. These ideas form the basis of first order logic, abbreviated “FOL.” The discussion of the nasal cavity tumor that may metastasize (in Chapter 1, pages 96–97) can be put in the form of FOL. The goal is to express the knowledge that tumor cells spread from the primary tumor site through the lymphatic system and lodge in lymph nodes, so that we can use the knowledge of the structure of the lymphatic system to predict the locations of regional metastasis. Then, having a formal theory of tumor spread, the theory can be embodied in a computer program to automate the application in a practical clinical setting. We define the location function, a function of two variables, such that if location(x, y) has the value “true” (which we represent by the symbol t), then the object denoted by x is located at

Chapter | 2 Symbolic Biomedical Knowledge

103

FIGURE 2.2 A diagrammatic representation of the first part of the glycolysis pathway.

– D – glucose – 6 –phosphate D – fructose – 6 –phosphate

Fructose – 1,6 – bisphosphate

Dihydroxy– acetone –phosphate

D – glyceraldehyde – 3 – phosphate

1, 3 – Diphosphateglycerate 3 – Phosphoglycerate 2 – Phosphoglycerate Phosphoenolpyruvate Pyruvate

the anatomical site y. Similarly, the lymphatic-drainage function, called drains, has two variables, an anatomic location and a lymphatic network or chain. If drains(x, y) has the value t, it may be interpreted to mean that the lymphatic chain y drains the anatomic location x. Finally, we define the metastatic risk function, called risk, a function of one variable, a lymph node. This means that risk(x) has the value t if the lymph node is at risk of metastatic disease. Then, the first axiom of our theory may be written as a logic formula (the notation is described in more detail in Section 2.2): ∀x, y, z tumor(x) ∧ location(x, y) ∧ drains(y, z) → risk(z)

(2.1)

In this formula, x, y, and z play the role of variables. Here, however, their values are not numbers but symbols representing things like a particular tumor, an anatomic location (taken from the FMA introduced in Chapter 1 and more fully described in Chapter 6, illustrating yet another way in which the FMA appears as a collection of data, rather than knowledge), and a lymph node or lymphatic chain (also from the FMA). The formula represents general knowledge. For an individual patient, we would have assertions about the location of a particular tumor and the lymphatic drainage of that location. We will consider a tumor in the nasal cavity, which has the retropharyngeal node group as its lymphatic drainage. For this patient, we have these additional formulas: location(T 4, NC) = t

(2.2)

drains(NC, RP) = t

(2.3)

where T 4 is the tumor, NC is the nasal cavity, and RP is the retropharyngeal node group. Then, we can infer the result from formula 2.1: risk(RP) = t and from this, we would infer that we should include these nodes in a radiation treatment plan to insure that these suspected metastatic tumor cells are destroyed.

104

PART | I Foundations of Biomedical Informatics

What about the functions? How are they defined? The drains function can be implemented as a query of an anatomy model such as the FMA. This is possible because an ontology like the FMA serves not only just as a standardized vocabulary but also contains relations between the terms, such as contained-in, part-of, and lymphatic-drainage, as well as subsumption relations (one thing is a specialization of another, sometimes called an is-a relation). From this perspective, the FMA represents knowledge not just data. In this simple example, it is a lot of notation for something easy to glean from reading the textual version of the knowledge. However, it is also known that tumor cells may spread through lymphatic vessels for some distance beyond the initial drainage sites. Thus, to predict the extent of metastatic (but unseen) disease, one must know or look up many details of connectivity of the lymphatic system. When the number of formulas gets only a little larger and the number of anatomic locations and lymph nodes also gets large, it will pay to formalize the knowledge. Why? Once we have a symbolic form for it, we can have a computer do the work. Even better, if the symbolic language we use for formalizing the data and knowledge is a computer interpretable language (a programming language), we can eliminate one translation step. The EcoCYC knowledge base is another example of a symbolic theory. It is a theory in the sense that it represents a collection of known biochemical principles, basic knowledge about biochemical compounds, and a collection of known biochemical pathways. By applying reasoning principles or methods, one can specify a particular problem or condition and then predict the behavior of the E. coli organism under that condition. One can go further and predict possible pathways by searching at a more detailed level, chaining together known biochemical reactions to see if there is a way to, for example, metabolize glucose, that is, manufacture other useful molecules from it with the available enzymes and reactants. This and other examples are developed in Chapter 5. This idea of “theoretical biomedicine” is controversial. Certainly, our biomedical theories are taking a different shape than theories in physics or chemistry. In biology and medicine, these theories contain lots (possibly millions) of specific assertions rather than a few general rules or equations from which large numbers of solutions can be derived. Also in medicine (and biology), although we are writing categorical statements here, for every statement we will put in logical form, there is a lot of uncertainty associated with it. Finally, in many circumstances, particularly in medical practice, such theories are very incomplete in coverage, and thus may have limited applicability. Even where the coverage is good, one can question whether much new or interesting can be predicted from such knowledge compilations. We are going to leave these questions to be answered by future experience. Despite these limitations, there is a large potential and growing activity in this area. Expressing ideas in biomedicine as computer programs gives three benefits. One is that a program gives precision to the theory, so that its properties can be formally examined, deduced, and discovered. It is possible, for example, to determine through the formalism if the proposed theory is self-consistent or not. The second is that the proofs, derivations, and calculations that in the physical sciences until recently have been done by hand (the algebraic and other mathematical manipulations of the formulas, not the computation of specific numeric results) can be done automatically by the computing machinery. Third, the program can in principle be incorporated into a practical system for use in the laboratory, the clinic, or in other biomedical contexts. These are lofty goals. The extent to which they are easy or difficult to achieve will be seen in the following sections. The citations and summary at the end of this chapter provide an entry to research aimed at extending the ideas and solving the difficult problems. Another way to look at the problem of representing medical knowledge is referred to as “evidencebased medicine” (EBM). This name is misleading. It has been described as the idea “that clinical care should be guided by the best scientific evidence” [109, page 57]. This way of describing it to the lay person usually gets the response, “So, how have doctors been doing it until now?” Clinical practice, done well, has always been guided by the best scientific evidence. Until recently, progress in biomedical science has been slow enough for research findings (evidence) to gradually and

Chapter | 2 Symbolic Biomedical Knowledge

105

carefully move from the research literature to the textbooks and to practice. Now, with the explosion in biological data and the rapid increase in sheer volume of scientific publication, the amount of new information is overwhelming our old system of knowledge transfer. When people talk about EBM, what they are really talking about is finding new and more efficient methods of distilling, summarizing, and transmitting (making available) scientific discoveries. This process needs to go more rapidly than before in order to cope with the huge increase in the rate of discovery of new knowledge. From this perspective, the role of logic, inference, ontologies, etc. is to provide new organizing tools so that we can record, search, and retrieve chunks of knowledge. So, we will have to keep in mind these two points of view, knowledge-based systems as scientific theories and knowledge-based systems as information management tools. In this chapter and Chapter 3, the emphasis will be on building scientific theories, and in Chapter 4 the emphasis will be on information management.

2.2 LOGIC AND INFERENCE SYSTEMS The supreme task of the physicist is to arrive at those universal elementary laws from which the cosmos can be built up by pure deduction. – Albert Einstein from “Principles of Research,” address at the celebration of the sixtieth birthday of Max Planck, reprinted in [69]

Biology is not physics. – Larry Hunter (personal communication)

Logics are formal languages for representing information and knowledge such that new assertions can be inferred from the initial knowledge, assertions that were not part of the initial information or knowledge. Many different kinds of logic systems can be invented, each with a range of capabilities and limitations. The most widely used and studied, propositional calculus and FOL, will be described here. A logical system consists of a collection of statements, or sentences, made up of symbols that have some predefined meanings. In order to make it possible to do automated deduction and analysis, we have to specify what constitutes a sentence and what is not a sentence, just as in ordinary written languages. The allowed symbols constitute the vocabulary of our logic. The rules for constructing grammatically correct sentences specify the syntax. In order to make any practical use of the logic system, we need to specify also an interpretation of the symbols, essentially a mapping of symbols to things in the world of our experience. This mapping is also called the semantics of the logic system. Some of the symbols will have meanings that can be completely specified independently of interpretation of the other symbols. These are the familiar connectives, such as and, or, and not, and (when dealing with variables) quantifiers, like for all and there exists. For example, if A and B are sentences that could be either true or false, then A ∧ B is also a sentence, where the symbol ∧ represents the “and” connector. The meaning of ∧ is that if the sentence A is true and B is also true, the compound sentence is true, otherwise the compound sentence is false. This only depends on the truth value of the two terms, A and B, not on their actual real-world interpretations or meanings. In any logic system there are also primitives, whose meaning depends on an interpretation. Because of this, a sentence that is true in one real-world interpretation may well be false in another. For example, the statement, “Mach is the best in the class” could be either true or false, depending on what the terms “Mach,” “best,” and “class” refer to. One interpretation is that Mach is the famous nineteenth century physicist, “class” refers to a mathematics class he enrolled in, and “best” compares his numeric grade

106

PART | I Foundations of Biomedical Informatics

in the class to that of the other students. I do not know if this is true; it certainly could be false. On the other hand, in more modern times, this sentence could refer to Mach, a variant of the UNIX operating system, and the class referred to is the class of UNIX variants. “Best” could mean many things, and this too could be either true or false. The overall plan for building logical theories is to start with sentences that are true in the real-world interpretation of interest (these are axioms), and then by a reliable method of proof, find out what other sentences are true in that interpretation (these are the entailments). Thus a logic consists of ● ● ●

a set of primitives, ways of building formulas (connectives, quantifiers, punctuation), and inference rules (how to derive new formulas).

In the following subsections, we will develop a simple logic, predicate calculus, with biological, medical, and public health examples. We will then consider FOL, which includes variables and quantifiers. At the end of this section, we will consider some limitations of the formal logic approach, which will then lead to some alternatives.

2.2.1 Predicate Calculus A simple logic in which to illustrate the ideas is predicate calculus, sometimes also called propositional calculus or propositional logic. We will represent primitives by symbols. There will be a few special symbols, the connectives, whose meaning is independent of any particular real-world interpretation, and then we will show how to do proofs, that is, determine what the implications are of a starting set of formulas. The standard connective symbols of predicate calculus are: ∨ ∧ ¬ →

or (inclusive) and not implies

Using these symbols and also symbols for primitives, we can construct sentences in our logic, called “Well Formed Formulas” (sometimes abbreviated as “wff”). Here are the rules for constructing a wff from primitives, connectors, and other wffs (in the following, we use the Greek letters, α, β, and γ as symbols for propositions, in addition to the ordinary Latin alphabet): ● ● ●

Every primitive symbol is a formula. If α is a formula, then ¬α is a formula. If α and β are formulas, then α ∧ β, α ∨ β, and α → β are all formulas.

In cases where combining formulas with connectors might result in ambiguity as to the meaning (for example because the resulting series of symbols might be grouped in different ways), parentheses are used to make clear the order in which the connectors are applied. For example, (¬α) ∨ β is not the same as ¬(α ∨ β). The language of logic is compositional, that is, the meaning and value of compound formulas depends on the meaning of the individual terms. When a term appears in several places in a single formula, it is required to have the same interpretation everywhere. For the relation α → β, for example, we can assign truth values that depend only on the truth values of the individual primitives, α and β, regardless of what the symbols stand for. β α and similarly for α ∨ β and α ∧ β and ¬α.

T F

T T T

F F T

Chapter | 2 Symbolic Biomedical Knowledge

107

The point of all this is to take knowledge in biology, medicine and health, and where possible reformulate it in this kind of language. Then we can automate the reasoning that would otherwise have to be done manually. An example from the field of public health surveillance will help to illustrate the idea. This scenario is based on an idealized vision for public health surveillance in a book chapter by Dean [56]. In Dean’s example, the epidemiologist has at his/her disposal computer systems that can retrieve information about patterns of activity and other data, displayed geographically, so that the epidemiologist can correlate outbreaks with environmental conditions. The epidemiologist notices what appears to be an unusual occurrence of asthma in a particular area, and after looking at several other data sources identifies a factory that is upwind of the neighborhood, where industrial waste is being moved by bulldozer. The action chosen is to request that the waste be sprayed with water so that it will not so easily be spread by wind currents. There are many components of this scenario, including statistical analysis of time series and geographic data to identify anomalous signals. However, here we just show how some of the reasoning of the epidemiologist can be expressed in logic formulas. Here are the English language statements in a simplified form. ● ●

●

If particulate material is being moved and it is dry, it will become airborne. If particles are toxic and airborne, then there will be an increase of incidence of asthma in the vicinity. If there is an increase of asthma incidence, there will be an increase of clinic visits in the area.

How can this be formalized? We abbreviate the things being described by symbols and use the connectors above to represent the causal relations. Thus, ● ● ●

moved ∧ dry → airborne airborne ∧ toxic → more-asthma more-asthma → more-clinic-visits

One can use single letter symbols if only a few are needed, as we used the Greek letters earlier. However, in most biomedical and health applications, the number of things in the world that are coded as symbols can be in the thousands or even hundreds of thousands, so longer names are needed. The formulas above can be combined to reach a conclusion from the environmental facts, which can explain the observation that matches this conclusion. Intuitively, we can see that if someone is moving (transporting in an open truck) some significant amount of dry and toxic waste, the above statements imply that we will see an increase in clinic visits. In the following sections, we will give this inference process a formal framework, and then show how it can be automated in a computer program.

Truth and Consequences The formulas about toxic waste cleverly use symbols that we recognize as words with meanings, but a computer program has no way to assign meaning to symbols. So, in order for a computer program to process the information, we need a more narrow idea of “meaning.” When we read the statements, we intuitively assign each term to correspond to something in the physical world, a property of the world that can be either true or false. In any particular instance, this connection between the term and its real-world counterpart should determine if it is actually a true assertion or a false one. When we choose the connections, we are creating what is called an interpretation. The meanings determine whether each formula is true or false in that interpretation. In the domain of logic, the term “interpretation” means simply to assign a value of either true or false to each of the primitives that appear in all the formulas (this must of course be done consistently, that is, wherever the same primitive appears, the value must be the same for it). In the context of a biomedical theory or knowledge base, however, we get these assignments of true or false values from the meaning of each primitive in the real-world. In a set of formulas (we sometimes call such a set a “knowledge base”), when a primitive appears in different formulas, its meaning should be the same everywhere. Of course, to represent knowledge,

108

PART | I Foundations of Biomedical Informatics

rather than arbitrary statements, each of the statements, that is, formulas, should be true in our chosen interpretation. In that case, it could be that additional statements must be true as well (this is the idea of inference described informally above). A formal reasoning process would enable us to determine what else is true if all the formulas (we call them sentences) in the set are true. ● ●

If a sentence is true in an interpretation, we say it is satisfied in that interpretation. A sentence α is said to be entailed by a set of sentences S if α is true in every interpretation in which all the sentences in S are true.

Determining entailment is a difficult problem. Generally, it involves computing and examining truth tables for every combination of primitive terms that appear in the set of sentences, and that make the sentences true. As an example, we can show that the formula α → β is equivalent to (¬α) ∨ β, that is, the second formula is entailed by the first and vice versa. This can be verified by using truth tables. For each of the four combinations of the values true and false for α and β, we determine the value of the first formula and the value of the second formula, to find that they are identical in every case. The truth table for α → β is already given above. When α has the value true (T) and β does also, (¬α) ∨ β has the value T because that is the meaning of the “or” connective. (¬α) may be F but if β is T, then the whole expression is T. Each of the other combinations can be verified the same way.

Inference Rules Since entailment (using interpretations or truth tables) is so difficult, it is important to find more reasonable strategies for determining it. Such strategies are called inference procedures. Inference procedures are purely formal manipulations of formulas from which we derive new formulas. If we can depend on them to produce only formulas that are true, when we start from a set of formulas that are true (assuming of course that the original set is consistent), we say that the inference procedures are sound. When the possibilities become extremely numerous, it is a real advantage to have the inference done by machine rather than by an epidemiologist who will be overwhelmed by data. Usually, when we translate knowledge in ordinary language into logic statements, the formulas are not in the simplest or best form for an automated reasoning system. In addition, the automated reasoning system may need to rearrange the formulas in some equivalent but simpler way, as part of the automated reasoning. To help with this, there are some relationships among formulas that are true, no matter what the interpretation of the symbols is. These are like algebraic identities and trigonometric identities. Here are some useful relations that apply to predicate calculus (again, the Greek letters stand for any term or proposition). ●

DeMorgan’s laws allow us to rewrite formulas that include the ¬ (not) operator, either to move the ¬ past parentheses or factor it out. The effect of moving the ¬ is to change ∨ into ∧ and vice versa. ¬(α ∧ β) is equivalent to (¬α) ∨ (¬β) and ¬(α ∨ β) is equivalent to (¬α) ∧ (¬β)

In addition, there are distributive, commutative, and associative laws that allow us to rearrange formulas that combine ∨ and ∧. ●

The distributive laws are similar to but not exactly like the rules in algebra for factoring with + and ∗. α ∧ (β ∨ γ) is equivalent to (α ∧ β) ∨ (α ∧ γ) and α ∨ (β ∧ γ) is equivalent to (α ∨ β) ∧ (α ∨ γ)

Chapter | 2 Symbolic Biomedical Knowledge

●

109

The commutative laws just state that the order of the terms in ∨ and ∧ expressions does not matter. α ∨ β is equivalent to β ∨ α and α ∧ β is equivalent to β ∧ α

●

The associative laws show that we can write expressions with multiple terms all connected by the same connective, without grouping by parentheses, since the results are the same for all possible groupings. However, when there are mixed connectives, you must include parentheses, otherwise the formula is ambiguous. α ∧ (β ∧ γ) is equivalent to (α ∧ β) ∧ γ and α ∨ (β ∨ γ) is equivalent to (α ∨ β) ∨ γ

All the equivalence laws described earlier in this section can be used as inference rules, since all of them can be verified to be sound. For example, if your set of formulas includes the formula α → β, you can add to your set the equivalent formula, (¬α) ∨ β. The following are some important additional sound inference procedures for propositional logic. ●

●

●

●

●

“and” elimination: From a conjunction, α ∧ β, we can infer α and β separately. “and” introduction: Given two sentences, α and β, we can infer the conjunction, α ∧ β. double negative elimination: The double negative, ¬¬α, is equivalent to the formula α. Modus Ponens: From the two formulas, α and α → β, we can infer β. resolution: From α1 ∨ . . . ∨ αn ∨ γ and β1 ∨ . . . ∨ βm ∨ ¬γ, we can infer α1 ∨ . . . ∨ α n ∨ β1 ∨ . . . ∨ β m .

It might appear that one can write inference rules as sentences within the logic system. For example, one might think that Modus Ponens is equivalent to the wff α ∧ (α → β) → β, but this formula, even though it is always true, is not the same as the assertion that we can add the formula β to the collection.4 How do we then determine whether a particular inference procedure is sound or not? Indeed there is a connection with the reformulation of inference rules as formulas within the system. If such a formula can be shown to be true no matter what the interpretation is, then the inference rule corresponding to it is sound [320].

Theorems and Proofs Entailment is not the same as proof. Entailment concerns what is actually true as a consequence of a collection of sentences being true. It is conceivable that there may be truths that follow from a collection of sentences, but there is no way to prove them (in the sense we usually mean by proof, using sound inference procedures, not by checking truth tables). Furthermore, we may invent proof methods that 4. A droll treatment of this matter, by Lewis Carroll, reprinted in The World of Mathematics [44], can also be found in Hofstadter’s Gödel, Escher, Bach: An Eternal Golden Braid [112, pages 32–34].

110

PART | I Foundations of Biomedical Informatics

are not reliable, in that they may allow us to find proofs for sentences which are not entailed by the given sentences. In the following, we are starting with a set of axioms, which are formulas that are assumed to be true in the (usually biomedical) interpretation of interest, and which form the basic assertions of our knowledge base (or, put another way, our biomedical theory). The goal is to compute (eventually by an algorithm that can be implemented in a computer program) the entailments of such a set of axioms (usually together with some additional assertions about a particular problem case). Note that an axiom is not the same as an assertion that may be true (entailed by the other assertions) but cannot be proved. An axiom is also different from a definition, which serves to associate a name with some conditions, entities, or both. Definitions say nothing about the world, but axioms do. ●

● ●

A proof is a sequence of formulas, where the next formula is derived from previous ones using sound inference rules. A theorem is a formula that can be derived (proved) from a set of axioms. A tautology is a formula that is true regardless of the interpretation. An example is A → (A ∨ B), but A → B is not a tautology. (A tautology is sometimes called a valid formula.) Sound inference rules can be made to correspond to tautologies, although strictly speaking they are not formulas but procedures for manipulating collections of formulas. As an example, the Modus Ponens inference rule corresponds to the tautology α ∧ (α → β) → β.

It is important to note that a tautology is simply true, independent of the interpretation given to the literals in the formula. All the laws mentioned earlier can be expressed as tautologies. An axiom is different. An axiom is a formula that you assert to be true as part of a theory about something in the world, that is, in some particular interpretation. It might or might not actually be true. When our understanding of the world takes the form of a complex theory with many axioms and lots of inferences, it might not be possible to do an experiment or measurement to determine directly whether an axiom is true. In that case, the theorems that follow from that and the other axioms are used to test the theory. If a theorem’s statement is in disagreement with the observed world, one or more axioms must be wrong too. As an example of a proof, we return to the epidemiological example. We start with the set of sentences described previously, together with the three further assertions, moved, dry and toxic (referring to some large amount of industrial waste). A: B: C: D: E: F:

moved ∧ dry → airborne airborne ∧ toxic → more-asthma more-asthma → more-clinic-visits moved dry toxic

What is entailed by these sentences? First, we note that we can use the Modus Ponens inference rule with formulas A, D, and E. The α part is just the combination moved ∧ dry, which comes from D and E. The β part is the assertion airborne. Thus, we can add G: airborne. Then we can again apply Modus Ponens, this time to B and the combination of G and F, to get H: more-asthma. One more time, we can apply Modus Ponens with C and H to get I: more-clinic-visits. So, there are several entailments that we can prove. This process of going from facts and inferences to new facts and then applying new inferences is called forward chaining. Another way to discover a proof is to start with the theorem to be proved and look for support. This means finding formulas in the knowledge base and an inference rule that together can infer the formula of the theorem. Here, we would look to prove the proposition more-clinic-visits. By C, if we had more-asthma, we could prove more-clinic-visits using Modus Ponens. So, we look for a way to

Chapter | 2 Symbolic Biomedical Knowledge

111

prove more-asthma. This could be done with B if we had both airborne and toxic. Aha! We do have toxic in the original set. Now we just need to prove airborne. Fortunately, sentence A provides a way to get airborne, if we have moved and dry. Since we do (D and E), we can then infer that we have everything needed to prove more-clinic-visits. This method of starting with the conclusion and finding the support that leads to it is called backward chaining. Even though a proof might exist, using forward or backward chaining might not succeed in constructing or finding it. Here is a simple example of a set of medical knowledge formulas that have entailments that cannot be deduced by either forward or backward chaining. These sentences form a collection of axioms, a simple theory of bacterial infection and treatment. These statements, involving bacteria and infections, are not entirely biologically accurate. I have artificially simplified the situation in order to illustrate the limitations of Modus Ponens as an inference rule. ●

● ●

Bacteria are either Gram positive or Gram negative (the Gram stain is a procedure that colors bacteria either pink or deep purple, depending on the permeability of their cell membranes). There are antibiotics for treating infections from Gram positive bacteria. There are antibiotics for treating infections from Gram negative bacteria. We can write these statements in logic notation as follows:

A: bacteria → (gram-positive ∨ gram-negative) B: gram-positive → treatable C: gram-negative → treatable This set of axioms entails the statement that all bacterial infections are treatable, that is, no matter what organism attacks, there is an antibiotic treatment for it. In logic, with the above predicates, bacteria → treatable. However, this statement cannot be proven by forward chaining or backward chaining using Modus Ponens. The problem is this: in order to use sentence B to conclude that bacteria are treatable, we need to assert that bacteria are Gram positive. But they are not all Gram positive. Only some are. For those, we can conclude treatable. Similarly, for the ones that are Gram negative, we can reach the same conclusion, but there is no way to use the Modus Ponens rule to separately reach either gram-positive or gram-negative. To deal with axioms using the “or” connector, we need stronger inference rules. Fortunately, the resolution inference rule, also mentioned above, is sufficient to construct a proof. The resolution rule does deal with the “or” connector. In order to apply resolution, we need to convert all our formulas to the forms that appear in the rule. This means that we need to have a collection of formulas called clauses. A clause is a formula with only primitives and negations of primitives, connected by ∨ (or). Later, we will show how to convert any formula to a collection of clauses (this is called “conjunctive normal form,” or CNF). Using the fact that the formula α → β is equivalent to (¬α) ∨ β, we can rewrite A as ¬bacteria ∨ (gram-positive ∨ gram-negative) and similarly, B and C as ¬gram-positive ∨ treatable and ¬gram-negative ∨ treatable Then, using resolution with the first and the second, we can eliminate the term gram-positive since it appears in one formula as a primitive and in the other as its negation. The result is ¬bacteria ∨ gram-negative ∨ treatable

112

PART | I Foundations of Biomedical Informatics

Combining this with the third formula (derived from C), we can eliminate the term gram-negative because it appears in one formula as a primitive and in the other as its negation. The result is ¬bacteria ∨ treatable which we can then transform back to the implication form, and thus our result is derivable from the axioms, using resolution as the main inference method. So far, when we consider proofs and truth, we are referring to truth in the sense of entailment, independent of any real-world interpretation of the symbols we are manipulating. For any collection of logic sentences, we can give the symbols many different interpretations. In some interpretations a sentence may be true, but it is possible that there is no proof for it. The absence of a proof for an assertion does not mean it is false, but onl