Fast exact string pattern-matching algorithms adapted to the characteristics of the medical language.

OBJECTIVE: The authors consider the problem of exact string pattern matching using algorithms that do not require any preprocessing. To choose the most appropriate algorithm, distinctive features of the medical language must be taken into account. The characteristics of medical language are emphasized in this regard, the best algorithm of those reviewed is proposed, and detailed evaluations of time complexity for processing medical texts are provided. DESIGN: The authors first illustrate and discuss the techniques of various string pattern-matching algorithms. Next, the source code and the behavior of representative exact string pattern-matching algorithms are presented in a comprehensive manner to promote their implementation. Detailed explanations of the use of various techniques to improve performance are given. MEASUREMENTS: Real-time measures of time complexity with English medical texts are presented. They lead to results distinct from those found in the computer science literature, which are typically computed with normally distributed texts. RESULTS: The Boyer-Moore-Horspool algorithm achieves the best overall results when used with medical texts. This algorithm usually performs at least twice as fast as the other algorithms tested. CONCLUSION: The time performance of exact string pattern matching can be greatly improved if an efficient algorithm is used. Considering the growing amount of text handled in the electronic patient record, it is worth implementing this efficient algorithm.

Evaluation of a command-line parser-based order entry pathway for the Department of Veterans Affairs electronic patient record.

OBJECTIVE: To improve and simplify electronic order entry in an existing electronic patient record, the authors developed an alternative system for entering orders, which is based on a command- interface using robust and simple natural-language techniques. DESIGN: The authors conducted a randomized evaluation of the new entry pathway, measuring time to complete a standard set of orders, and users' satisfaction measured by questionnaire. A group of 16 physician volunteers from the staff of the Department of Veterans Affairs Puget Sound Health Care System-Seattle Division participated in the evaluation. RESULTS: Thirteen of the 16 physicians (81%) were able to enter medical orders more quickly using the natural-language-based entry system than the standard graphical user interface that uses menus and dialogs (mean time spared, 16.06 +/- 4.52 minutes; P=0.029). Compared with the graphical user interface, the command--based pathway was perceived as easier to learn (P<0.01), was considered easier to use and faster (P<0.01), and was rated better overall (P<0.05). CONCLUSION: Physicians found the command- interface easier to learn and faster to use than the usual menu-driven system. The major advantage of the system is that it combines an intuitive graphical user interface with the power and speed of a natural-language analyzer.

Alternative ways for knowledge collection, indexing and robust language retrieval.

Definitions are provided of the key entities in knowledge representation for Natural Language Processing (NLP). Starting from the words, which are the natural components of any sentence, both the role of expressions and the decomposition of words into their parts are emphasized. This leads to the notion of concepts, which are either primitive or composite depending on the model where they are created. The problem of finding the most adequate degree of granularity for a concept is studied. From this reflection on basic Natural Language Processing components, four categories of linguistic knowledge are recognized, that are considered to be the building blocks of a Medical Linguistic Knowledge Base (MLKB). Following on the tracks of a recent experience in building a natural language-based patient encoding browser, a robust method for conceptual indexing and query of medical texts is presented with particular attention to the scheme of knowledge representation.

Natural language processing and semantical representation of medical texts.

For medical records, the challenge for the present decade is Natural Language Processing (NLP) of texts, and the construction of an adequate Knowledge Representation. This article describes the components of an NLP system, which is currently being developed in the Geneva Hospital, and within the European Community's AIM programme. They are: a Natural Language Analyser, a Conceptual Graphs Builder, a Data Base Storage component, a Query Processor, a Natural Language Generator and, in addition, a Translator, a Diagnosis Encoding System and a Literature Indexing System. Taking advantage of a closed domain of knowledge, defined around a medical specialty, a method called proximity processing has been developed. In this situation no parser of the initial text is needed, and the system is based on semantical information of near words in sentences. The benefits are: easy implementation, portability between languages, robustness towards badly-formed sentences, and a sound representation using conceptual graphs.

Modeling concepts in medicine for medical language understanding.

Over the past two decades, the construction of models for medical concept representation and for understanding of the deep meaning of medical narrative texts have been challenging areas of medical informatics research. This review highlights how these two inter-related domains have evolved, emphasizing aspects of medical modeling as a tool for medical language understanding. A representation schema, which balances partially but accurately with complete but complex representations of domain-specific knowledge, must be developed to facilitate language understanding. Representative examples are drawn from two major independent efforts undertaken by the authors: the elaboration and the subsequent adjustment of the RECIT multilingual analyzer to include a robust medical concept model, and the recasting of a frame-based interlingua system, originally developed to map equivalent concepts between controlled clinical vocabularies, to invoke a similar concept model.

Representing clinical narratives using conceptual graphs.

The analysis of medical narratives and the generation of natural language expressions are strongly dependent on the existence of an adequate representation language. Such a language has to be expressive enough in order to handle the complexity of human reasoning in the domain. Sowa's Conceptual Graphs (CG) are an answer, and this paper presents a multilingual implementation, using French, English and German. Current developments demonstrate the feasibility of an approach to natural Language Understanding where semantic aspects are dominant, in contrast to syntax driven methods. The basic idea is to aggregate blocks of words according to semantic compatibility rules, following a method called Proximity Processing. The CG representation is gradually built, starting from single words in a semantic lexicon, to finally give a complete representation of the sentence under the form of a single CG. The process is dependent on specific rules of the medical domain, and for this reason is largely controlled by the declarative knowledge of the medical Linguistic Knowledge Base.

Power of expression in the electronic patient record: structured data or narrative text?

This paper presents the authors' experience with the development and use of a document-centered electronic patient record (EPR) in a large teaching hospital. The development of the document-centered EPR began with the formulation of a set of critical hypotheses to facilitate both the continuation of the best medical practice and the implementation and use of the EPR. An alternate and more conventional approach - the data-centered EPR - is compared with the document-centered EPR. Various benefits and pitfalls are discussed. Finally, the choice was to offer both solutions in a tightly linked system. The need for an EPR which combines the document and data centered approaches is a reflection of the more general discussion of what the medical record will be in the future. All too often, the need for structured data conflicts with the need for free texts and the power of expression. It is not easy to evaluate the consequences of this initial decision. However, changing the foundations of the EPR after its implementation is difficult and expensive. Therefore, the selection of the correct orientation in a given hospital requires a broad-based discussion.

Natural language generation of surgical procedures.

A number of compositional Medical Concept Representation systems are being developed. Although these provide for a detailed conceptual representation of the underlying information, they have to be translated back to natural language for used by end-users and applications. The GALEN programme has been developing one such representation and we report here on a tool developed to generate natural language phrases from the GALEN conceptual representations. This tool can be adapted to different source modelling schemes and to different destination languages or sublanguages of a domain. It is based on a multilingual approach to natural language generation, realised through a clean separation of the domain model from the linguistic model and their link by well defined structures. Specific knowledge structures and operations have been developed for bridging between the modelling 'style' of the conceptual representation and natural language. Using the example of the scheme developed for modelling surgical operative procedures within the GALEN-IN-USE project, we show how the generator is adapted to such a scheme. The basic characteristics of the surgical procedures scheme are presented together with the basic principles of the generation tool. Using worked examples, we discuss the transformation operations which change the initial source representation into a form which can more directly be translated to a given natural language. In particular, the linguistic knowledge which has to be introduced--such as definitions of concepts and relationships is described. We explain the overall generator strategy and how particular transformation operations are triggered by language-dependent and conceptual parameters. Results are shown for generated French phrases corresponding to surgical procedures from the urology domain.

Internet integrated in the daily medical practice within an electronic patient record.

Healthcare enters the information age and professionals are finding an ever-growing role for computers in the daily practice of medicine. However, a number of problematic issues are associated with electronic publications, especially through Internet. Whilst access to any information has been improved, access to specific information has become more and more difficult [1], due to the lack of a general meta-knowledge allowing to structure Internet resources. Physicians have to learn and adapt themselves to computers and Internet, but Internet has to meet the specific requirements of Healthcare. Important issues must therefore be addressed to allow a real and daily use of Internet in the medical practice. The paper discusses most of these issues and proposes a solution developed at the University Hospital of Geneva that integrates an Electronic Patient Record with Internet, without compromises on security or on performances and that runs on standard PCs'.

Conceptual search in electronic patient record.

Search by content in a large corpus of free texts in the medical domain is, today, only partially solved. The so-called GREP approach (Get Regular Expression and Print), based on highly efficient string matching techniques, is subject to inherent limitations, especially its inability to recognize domain specific knowledge. Such methods oblige the user to formulate his or her query in a logical Boolean style; if this constraint is not fulfilled, the results are poor. The authors present an enhancement to string matching search by the addition of a light conceptual model behind the word lexicon. The new system accepts any sentence as a query and radically improves the quality of results. Efficiency regarding execution time is obtained at the expense of implementing advanced indexing algorithms in a pre-processing phase. The method is described and commented and a brief account of the results illustrates this paper.

A toolset for medical text processing.

The processing of medical texts is a burden in the absence of a toolset designed for simple operations such as recognizing morphological variants, updating and accessing a word dictionary of the domain and segmenting words with multiple morpho-semantems. The apparent simplicity of these basic operations is an illusion because it soon becomes clear that quality implementation is a long-term task. Coherency between subtasks may be lacking unless strict rules are enforced. In fact, good tools are rarely available or have not been tailored for the medical profession. This paper aims at defining a complete toolset for medical word processing. In addition, it provides relevant examples of the inherent difficulties of this task. It reports on typical results that can be expected from an industry-standard implementation.

Natural language generation of surgical procedures.

The GALEN-IN-USE project has developed a compositional scheme for the conceptual representation of surgical operative procedure rubrics. The complex representations which result are translated back to surface language by a tool for multilingual natural language generation. This generator can be adapted to the specific characteristics of the scheme by introducing particular definitions of concepts and relationships. We discuss how the generator uses such definitions to bridge between the modelling 'style' of the GALEN scheme and natural language.

Paragraph-oriented structure for narratives in medical documentation.

The authors present a 6 years experiment using a document- centered electronic patient record, based on a central document repository. The document management system is paragraph oriented and all documents are built automatically before editing using predefined ordered sets of para-graphs. Paragraphs can be preloaded with templates, text or images. Once edited, signed and printed, documents are again decomposed in paragraphs and permanently stored. This system, though the compositional aspect of paragraphs is limited and their semantic content wide, offers numerous advantages. The typology is easy to build and to maintain, it has been implemented widely in our hospitals without need for any natural language processing techniques and is used daily within commercially available text editors. The actual state of the system is discussed, emphasizing the structure of the documents, the various attributes and properties that have been needed in order to meet user's needs.

Interchanging lexical information for a multilingual dictionary.

OBJECTIVE: To facilitate the interchange of lexical information for multiple languages in the medical domain. To pave the way for the emergence of a generally available truly multilingual electronic dictionary in the medical domain. METHODS: An interchange format has to be neutral relative to the target languages. It has to be consistent with current needs of lexicon authors, present and future. An active interaction between six potential authors aimed to determine a common denominator striking the right balance between richness of content and ease of use for lexicon providers. RESULTS: A simple list of relevant attributes has been established and published. The format has the potential for collecting relevant parts of a future multilingual dictionary. An XML version is available. CONCLUSION: This effort makes feasible the exchange of lexical information between research groups. Interchange files are made available in a public repository. This procedure opens the door to a true multilingual dictionary, in the awareness that the exchange of lexical information is (only) a necessary first step, before structuring the corresponding entries in different languages.

Versatility of a multilingual and bi-directional approach for medical language processing.

At the dawn of the 21st century, we are experiencing an exponential growth of online information that is mostly textual, and that benefits from new electronic media, such as the World Wide Web (WWW), to be broadly diffused across borders. However, there is a gap to bridge between holding information and accessing in a relevant way the deep underlying knowledge. Multilingual natural language processing (NLP), once tuned, is certainly the best solution to cope with this era of textual information. This paper focuses on the lesson learned through the joint development of an analyzer and a generator of medical language, within a multilingual context. Concrete examples, derived from the efforts under way in the European GALEN-IN-USE project, illustrate the use of these linguistic tools for the handling of surgical procedures.

Morpho-semantic parsing of medical expressions.

The task of editing, indexing, storing, and retrieving medical expressions within medical records remains the main objective for the years to come. Therefore, the need for a parser with semantic capabilities able to robustly extract an essential part of the knowledge embedded in the medical record is paramount. The minimal requirements before considering clinical trials are that such a system has to be in position to handle any source of medical information and to conveniently grasp the main key concepts with low silence, good recognition of modalities and acceptable noise. This paper shows that the potential of morpho-semantic parsing is high to meet these conditions. This technique is an important complement to the traditional lexical approach and to expression-oriented systems like controlled vocabularies.

A light knowledge model for linguistic applications.

Content extraction from medical texts is achievable today by linguistic applications, in so far as sufficient domain knowledge is available. Such knowledge represents a model of the domain and is hard to collect with sufficient depth and good coverage, despite numerous attempts. To leverage this task is a priority in order to benefit from the awaited linguistic tools. The light model is designed with this goal in mind. Syntactic and lexical information are generally available with large lexicons. A domain model should add the necessary semantic information. The authors have designed a light knowledge model for the collection of semantic information on the basis of the recognized syntactical and lexical attributes. It has been tailored for the acquisition of enough semantic information in order to retrieve terms of a controlled vocabulary from free texts, as for example, to retrieve Mesh terms from patient records.

Modeling principles for QMR medical findings.

Structured representation of medical information is essential for ensuring the accuracy and reliability of computerized decision support applications. Such systems require input that is error-free and clinically pertinent. This paper reviews existing medical models, particularly those exploited for natural language understanding, and highlights modeling features important to future indexing of medical texts with controlled vocabularies. A hybrid representation derived from existing frame-based and conceptual-graph-based systems is proposed to represent relevant medical terms as used by experts.

Controlling the vocabulary for anatomy.

When confronted with the representation of human anatomy, natural language processing (NLP) system designers are facing an unsolved and frequent problem: the lack of a suitable global reference. The available sources in electronic format are numerous, but none fits adequately all the constraints and needs of language analysis. These sources are usually incomplete, difficult to use or tailored to specific needs. The anatomist's or ontologist's view does not necessarily match that of the linguist. The purpose of this paper is to review most recognized sources of knowledge in anatomy usable for linguistic analysis. Their potential and limits are emphasized according to this point of view. Focus is given on the role of the consensus work of the International Federation of Associations of Anatomists (IFAA) giving the Terminologia Anatomica.

The power and limits of a rule-based morpho-semantic parser.

The venue of Electronic Patient Record (EPR) implies an increasing amount of medical texts readily available for processing, as soon as convenient tools are made available. The chief application is text analysis, from which one can drive other disciplines like indexing for retrieval, knowledge representation, translation and inferencing for medical intelligent systems. Prerequisites for a convenient analyzer of medical texts are: building the lexicon, developing semantic representation of the domain, having a large corpus of texts available for statistical analysis, and finally mastering robust and powerful parsing techniques in order to satisfy the constraints of the medical domain. This article aims at presenting an easy-to-use parser ready to be adapted in different settings. It describes its power together with its practical limitations as experienced by the authors.