extfieldsofstudy: Physics Mathematics

text:
Fast Spatial Prediction from Inhomogeneously Sampled Data Based on Generalized Random Fields with Gibbs Energy Functionals

An explicit optimal linear spatial predictor is derived. The spatial correlations are imposed by means of Gibbs energy functionals with explicit coupling coefficients instead of covariance matrices. The model inference process is based on physically identifiable constraints corresponding to distinct terms of the energy functional. The proposed predictor is compared with the geostatistical linear optimal filter (kriging) using simulated data. The agreement between the two methods is excellent. The proposed framework allows a unified approach to the problems of parameter inference, spatial prediction and simulation of spatial random fields.

INTRODUCTION
Spatial prediction of physical variables from samples that are irregularly distributed in space is a task with applications in many fields of science and engineering, including subsurface hydrology [1,2], oil reservoir engineering [3,4], environmental pollutant mapping and risk assessment [5], mining exploration and reserves estimation [6], environmental health studies [7], image analysis [8] and neuroscience [9]. Physical quantities of economical and environmental interest include mineral grades, concentrations of environmental pollutants, soil and rock permeability and flow fields in oil reservoirs. Modeling the variability of such processes is based on the theory of spatial random fields (SRFs) [10]. Knowledge of spatial correlations in SRFs enables (i) generating predictive isolevel maps (ii) estimating prediction uncertainty and (iii) developing simulations that reconstruct probable scenarios conditioned on the data. The classical approach is based on Gaussian SRF's (GSRF's) and various generalizations for non-Gaussian distributions [11,12]. For GSRF's the spatial structure is determined from the covariance matrix, which is estimated from the available sample(s).
Let Ω ∈ R d denote the area of interest, and |Ω| its volume. An SRF state (realization) in Ω can be decomposed into a deterministic trend m x (s), a correlated fluctuation X λ (s), and an independent random noise term, ǫ(s), i.e., X(s) = m x (s) + X λ (s) + ǫ(s). The trend represents large-scale variations obtained in principle by ensemble averaging, i.e. m x (s) = E[X(s)]. In practice, the trend is often determined from a single available realization. The fluctuation represents 'fast variations' describing fine structure above the resolution limit λ. The random noise represents non-resolved inherent variability, purely random additive noise, or non-systematic measurement errors. The fluctuation typically is a second-order stationary SRF, or an intrinsic SRF with second-order station-ary increments [10]. The residual SRF after trend removal is a zero-mean fluctuation: X * (s) = X λ (s) + ǫ(s). The inference process focuses on determining a model for X λ (s) from a set of possibly noisy observations X * (s).
In statistical physics the probability density function (pdf ) of any fluctuation field X(s) governed by an en- In classical geostatistics, the Gaussian joint pdf for a set of fluctuations ij is the inverse covariance matrix, and summation is implied over repeated indices. Instead, Spartan Spatial Random Fields (SSRF's) [13] model spatial correlations in terms of 'interactions'. This change in viewpoint has important consequences for model inference and spatial prediction.

THE FGC MODEL
In [13] the fluctuation-gradient-curvature (FGC) SSRF model is defined and its properties investigated. The continuum FGC model involves the following H[X]: The model is characterized by four parameters: the scale coefficient η 0 , the covariance-shape coefficient η 1 , the characteristic length ξ, and the cutoff wavevector k max . Bochner's permissibility theorem [5] for the positive definiteness of the covariance function requires η 1 > −2 if k max → ∞. In statistical physics terminology, ℓ 1 = η 1 ξ 2−d /(2 η 0 ) and ℓ 2 = ξ 2−d /(2 η 0 ) represent the coupling strengths of the gradient and curvature terms. A coarse-graining kernel is used to cut off the fluctuations at k max [13,14], leading to bandlimited covariance spectral density. If k max is finite, the field's configurations are almost surely differentiable [14]. If k max is infinite, generalized gradient and constraints should be used. The coarse-graining kernel implies that the SRF X λ is a generalized SRF [10]. A moment-based method for parameter estimation was proposed and validated with simulated data [13]. The inference process is based on matching ensemble constraints E[S j (s)] with their sample counterparts, denoted by S j (s), for j = 0, 1, 2. The procedure is extended in [15].
Assume S m = {s 1 , . . . s N } is a set of sampling points on an irregular grid and X * (S m ) = {X * 1 , . . . , X * N } is the respective vector of measurement. On an irregular grid, the translation symmetry of the lattice is lost. The continuum FGC functional is then a more suitable model. For practical purposed, a tractable approximation of the continuum model is needed.
In [15], approximations for the sample averages of S 1 (s) and S 2 (s) are formulated in terms of kernel averages of the data values. In the following we use the notation: c , where the summation is over both indices (i, j = 1, . . . , N ) denotes the average of the quantity A i,j , weighted by the kernel K h (r) with bandwidth parameter h. The pair distance is denoted by s i,j = s i − s j , where r is the Euclidean norm of the distance vector r, and the field increment by Then, the generalized gradient constraint is given by where a 2 1 = s 2 i,j h1 . Sensible estimates of the spacing a 1 should account for the grid topology. E.g., let B 0 be the set of near-neighbor vectors of all the points in S m . If B 0 contains N 0 vectors and ∆ i denote the lengths of the vectors in B 0 , thenâ d where µ 1 and µ 2 are 1 + o(ǫ) constants that depend on the sampling network topology. The µ 1 , µ 2 are defined so as to satisfy asymptotic bias and consistency properties [15]. They introduce explicitly in the problem of model inference four parameters linked to the topology of the sampling network: the spacings a 1 and a 2 that replace the lattice constant, and the bandwidths h 1 and h 2 that determine the range of influence of the averaging kernel. The latter are determined from the consistency principle a 2p The predictions will be denoted by {X λ (z l ), l = 1, . . . , K} and the respective prediction vector byX λ (Z p ). The increments corresponding to V l will be denoted by α p (V l ), p = 1, 2. Typically, single-point prediction is applied sequentially over all points in Z p . Multiple-point prediction is possible in the SSRF framework, but this letter focuses on single-point prediction.

Optimal Linear Prediction
In geostatistics, spatial prediction is based on the Best Linear Unbiased Estimator (BLUE), commonly known as Kriging [1,12]. Different variants of kriging exist, depending on the hypotheses about the normality of the data and the behavior of the mean. These methods are generalizations of the linear minimum mean square error (LMMSE) estimators, also known as Wiener filters [16]. Ordinary kriging (OK) is the most common variety. It is applied to normally distributed data, with an unknown mean that can be considered as locally constant. A single-point prediction is obtained as a superposition X(z l ) = M j=1 λ j X(s j ), where s j are all the points inside a local search neighborhood, B(s l ), around z l . The prediction error is defined as ε(s l ) =X(z l )−X(z l ). The optimal linear coefficients should minimize the mean square error conditional on the zero-bias constraint M j=1 λ j = 1, i.e., the expression E ε 2 (s l ) +µ M j=1 λ j − 1 , where µ is a Lagrange coefficient. This leads to the linear system C X (s i − s j ) λ j + µ = C X (s i − z l ), ∀ i = 1, . . . , M and M j=1 λ j = 1, where C X (r) is the centered covariance function. OK is an exact interpolator, meaning that {X(s i ) = X * (s i ), ∀s i ∈ S m }. Exactitude is not always desirable, since it ignores measurement errors and over-constrains the predictions. For a fixed-size search neighborhood, the numerical complexity of an M -point OK prediction is O(K M 3 ).

Spatial Prediction based on FGC Functional
Once the parameters of the FGC model have been determined from the data, prediction of the SRF at z l is possible by means of at least two different approaches.
First, the corresponding covariance function is determined and spatial predictions are then obtained using the OK predictor. In this case, the only difference introduced by the SSRF functional is the covariance estimator.
Here we propose a different predictor, obtained by maximizing the conditional probability density , the prediction is obtained by maximizing f X [X λ (V l )]. In principle, this requires solving the equation δH fgc /δX λ (z l ) = 0, where δ [.] δX λ (z l ) is the variational derivative of the functional given by Eq. (1) with respect to X λ (z l ). In practice, H fgc is replaced by a discretized estimator,Ĥ fgc . SinceĤ fgc is a bilinear functional, the prediction follows from the solution of the linear equation: H fgc is obtained by means of the estimators {S j (s), j = 0, 1, 2}, using the ergodic hypothesis ds S j (s) ≈ |Ω| S j (s), which leads to: where the spatial averages involve the sampling points and the prediction point as well. In light of (2), (3), and (5), equation (4) leads to the following linear predictor where q 1 = q 2 = 1, q 3 = q 4 = −1, X * l h is the kernel average of the sample, centered at the prediction point and the linear coefficients {c i , i = 1, 2, 3, 4} are given by The summation in g h (V l ) extends over all the N (N −1)/2 non-identical and non-repeating pairs of sampling points. Defining the linear weights the prediction is expressed aŝ

Properties of the FGC Mode Predictor
The present formulation of the FGC mode predictor (FGC-MP) is closer to simple kriging than OK, since the mean is assumed to be known. However, unlike simple kriging the mean does not have to be constant, provided that it changes slowly so that the energy contributions due to the square gradient and curvature of the mean can be ignored compared to the fluctuations. In this respect, the predictor resembles OK, which allows for slow (but unknown) variation of the mean. Predictions of the FGC-MP are independent of η 0 , while the prediction variance is linearly proportional to η 0 .
The FGC-MP is linear and unbiased. Since the joint FGC pdf is Gaussian, the mode estimate is equivalent to the minimum mean square estimate. Thus, the FGC-MP is an optimal linear predictor. The main differences with OK result from the use of the energy functional in the FGC SSRF: (1) The FGC-MP is not an exact interpolator, because it does not use the data at the prediction point. (2) The single-point FGC-MP provides an explicit expression for the prediction, while kriging requires solving a linear system. (3) The FGC-MP does not require specifying a search neighborhood around the prediction point; in kriging definition of a search neighborhood requires an iterative procedure based on cross-validation of the predictions with the data. (4) The FGC-MP incorporates two sets of parameters: the first set determines the spatial dependence of the SRF, while the second set depends on the topology of the sampling network. The influence of the sampling topology is not explicitly accounted for in kriging. (5) The uncertainty estimate involves the SSRF covariance function, for which there are no explicit solutions in d = 2, unlike d = 1, 3 [14]. Obtaining the covariance in d = 2 requires performing numerically a univariate (for isotropic dependence) integration of the spectral density. (6) Regarding multiplepoint estimates the FGC-MP has a numerical complexity O(K 3 ), derived from solving a linear system of K coupled equations at the prediction points, while the numerical complexity of kriging is O(K M 3 ).

PREDICTION USING SIMULATED SAMPLES
At 400 randomly distributed points on a square domain of length L = 100 we generate 100 independent "samples". These represent realizations of a Gaussian random field with m x = 50, and an exponential covariance function C x (r) = σ 2 x exp(− r /b e ), where σ x = 10, and b e = 10. The Cholesky LU decomposition method is used for the simulations. We partition the 400 points into a training set S m of 100 randomly selected points, and a prediction set, Z p , including the remaining points. We use the first set to determine the optimal SSRF parameters, and then predict the values of the field at the locations of the prediction set. The triangular kernel is used in the FGC-predictor mode. Predictions are also generated using the Ordinary Kriging method. The performance of the predictors is evaluated using the bias, the mean absolute error (mae), the root mean square error (rmse), the mean absolute relative error (mare), the root mean square relative error (rmsre) and the linear correlation coefficient (R 2 ). The means are calculated with respect to the values at the 300 prediction points. Statistics of these quantities over the 100 samples are shown in Tables I and II. The kriging predictor is applied with the a priori parameters of the exponential covariance (instead of the inferred covariance model from the data). This choice aims at testing the FGC-Mode Predictor against the "true" model. The results show that the two predictors perform very similarly.

CONCLUSIONS
A fast linear optimal predictor, with applications in the analysis of spatial data, is proposed. The predictor is based on generalized random fields which represent the spatial dependence in terms of interactions. An explicit expression for single-point prediction is obtained. The reduced numerical complexity of the FGC-Mode predictor may promote the use of cross-validation procedures for model parameter inference, instead of the commonly used parametric methods. The SRF representation, which is based by construction on an objective function, provides a unified framework for model parameter estimation, spatial prediction and constrained (respecting the data) simulation. This is in contrast with classical approaches that require the introduction of ad hoc objective functions [4,6] for simulations (e.g., by means of simu-lated annealing.) Expressions for the prediction uncertainty and a linear system for multiple-point prediction have also been derived and will be reported elsewhere [17]. The multiple-point predictor accounts for interactions between the prediction points that may lower the total "energy". Such interactions are missed in singlepoint prediction. Finally, the FGC focuses on short-range interactions, but long-range dependence can be incorporated in the SSRF framework with suitable modifications of the energy functional.


extfieldsofstudy:
Computer Science
Medicine

text:
A scalable machine-learning approach to recognize chemical names within large text databases.

MOTIVATION
The use or study of chemical compounds permeates almost every scientific field and in each of them, the amount of textual information is growing rapidly. There is a need to accurately identify chemical names within text for a number of informatics efforts such as database curation, report summarization, tagging of named entities and keywords, or the development/curation of reference databases.

RESULTS
A first-order Markov Model (MM) was evaluated for its ability to distinguish chemical names from words, yielding approximately 93% recall in recognizing chemical terms and approximately 99% precision in rejecting non-chemical terms on smaller test sets. However, because total false-positive events increase with the number of words analyzed, the scalability of name recognition was measured by processing 13.1 million MEDLINE records. The method yielded precision ranges from 54.7% to 100%, depending upon the cutoff score used, averaging 82.7% for approximately 1.05 million putative chemical terms extracted. Extracted chemical terms were analyzed to estimate the number of spelling variants per term, which correlated with the total number of times the chemical name appeared in MEDLINE. This variability in term construction was found to affect both information retrieval and term mapping when using PubMed and Ovid.

Introduction
Automated approaches to term identification within large corpora are becoming increasingly valuable as the amount of text-based information increases. MEDLINE, for example, is growing at a rate of ~4% per year, with approximately 672,000 new records added in 2005. Manual identification of key terms within large corpora such as this is tedious, time-consuming, costly, difficult to evaluate in terms of error rates, and often involves a minimum amount of expertise. Thus, data-mining approaches to identify trends, associations and patterns within text are being used more frequently [1,2] and an increased emphasis has been placed upon this automated recognition and extraction of terms within text [3], which usually serves as a stepping-stone towards other informatics applications, such as creating term association networks. These networks can in turn be used to identify commonalities shared by a set of terms [4,5] or to infer new associations between individual terms [6]. Accurate term recognition is also essential to automated or semi-auto-(page number not for citation purposes) mated database creation [7,8] and for straightforward information retrieval.
Considerable effort so far has centered upon the recognition of gene and protein names [9,10], presumably because of the growing number of high-throughput technologies in genomics, transcriptomics and proteomics. Surprisingly, not as much attention has been paid to the recognition of chemical names within text. Not only do most fields utilize chemistry, even aside of obvious ones such as pharmacology, toxicology, biochemistry and genetics, but chemical metabolites are an integral part of the proteomic and transcriptional network that has been the focal point for efforts thus far. Because new chemicals are constantly being synthesized, reference databases become increasingly out-of-date from the time they are first compiled. There is also a persistent need for computer aided indexing of relevant terms within text and a means of extracting chemical information from published sources faster and cheaper. For example, the American Chemical Society and PubChem have both spent considerable time and effort constructing their chemical databases, and the issue of who should pay for access has recently become a topic of controversy [11].
Spelling variation has long been recognized as a problem in information retrieval [12], and chemical names are known to be problematic. Early approaches to matching chemical names utilized approximate string matching techniques [13], such as the use of n-grams to compare chemical names [14]. Most approaches developed to handle these spelling variations, however, are designed with the intention of matching a user-entered term with one or a few entries within a database of chemical names. Identifying or "tagging" chemical names within text is another matter -authors are usually concerned more with reporting their results and less concerned with adhering to nomenclature standards, especially when it is clear to others in their field what they are referring to.
Heuristic approaches have been employed to identify chemical names within text, searching for characteristic patterns found in chemical names such as core chemical prefixes or suffixes, with one study reporting 93% precision and 86% recall [15]. However, only 55 abstracts were used in the evaluation, and they were obtained by searching on keywords related to acetylation, thus it is not at all clear how extensible these results are to larger corpora or other chemical names. Wilbur compared segmentation and Naïve Bayesian (NB) classification methods of recognizing chemical names, training and testing on the UMLS Metathesaurus [16]. However, the segmentation approach is again based upon component term definitions and it is not clear how adaptable it is to new morphological constructions of chemical names. The NB method yielded an impressive 96% precision, but it was tested using the same dictionary it was constructed from, and it is not clear how well it would perform on new terms, especially those buried within scientific text, which contains less standardized terms than are found within a curated database.

Using an MM to Identify Chemical Names
We hypothesized that a first-order Markov Model (MM) could be used to effectively discern chemical names, due to the fact that chemical component terms (also known as "morphemes") have a large fraction of consistent patterns that might make them highly amenable to MM analysis. After being trained to recognize both chemical and nonchemical names, an MM should be able to effectively judge new words by how well they conform to these patterns. A machine-learning approach such as a MM offers several advantages over heuristic approaches: First, it is capable of learning by example and is more tolerant of ambiguity. Second, MMs conveniently offer statistical confidence scores associated with term classification, and permit a user to adjust precision and recall rates to suit their needs by merely changing the confidence score cutoff. Third, by adjusting the training set, an MM-based approach can attempt to distinguish specific types of chemical compounds (e.g. sulfamides, phosphodiesterases) if the user is interested in such. Finally, no specialized lexicon or dictionary of prefixes/suffixes is required for term recognition. The trade-off, however, is that a large training set is required.
We anticipate that this machine-learning approach will perform much better in identifying chemical formulas than trade or brand names (e.g. Sulforhodamine-101 is better known as "Texas Red"). Trade names are designed specifically to sound more like English words than chemical names, making them easier to pronounce and shorter so they may be remembered more easily. Arguably, this is the biggest drawback of using this method. However, such trade names are often defined proximal to the chemical name within text. Thus, accurately locating the chemical name provides a way to potentially identify and associate both names. The ChemID database contains a mixture of the two.

Systems and Methods
Code was developed on a Pentium IV 3 GHz machine with 1 GB RDRAM and 109 GB of SCSI hard drive space, using Visual Basic 6.0 (SP5) with ODBC connections to an SQL database. The National Library of Medicine graciously provided XML files containing MEDLINE records with publication dates ranging from 1966 to March 2004 (which includes records indexed prior to publication), as well as a copy of the ChemID plus database http:// chem.sis.nlm.nih.gov/chemidplus/, which contained 367,821 records at the time of this study. Only chemical entries in English were processed (some chemicals have foreign name equivalents).
Originally, to train the MM to recognize non-chemical words, we tried to obtain abstracts we thought would not have many chemical names, by drawing from fields we viewed as substantially different from chemistry, such as astronomy, optics, anthropology, math and demography. Upon testing, however, we found many chemical names therein. The optimal training set, of course, would be a random sample of the corpus to be scanned minus chemical names. Since this is not available and each of these "non-chemical" abstract sets was found to have chemical names, we decided to go with an older scientific corpus that would not contain most or any modern chemical names. For this, we used Charles Darwin's "Descent of Man" and "Origin of Species" combined (3.1 MB of text total). For testing, we used Tolstoy's novel "War and Peace" (3.2 MB of text). The electronic full-text of all these corpora can be obtained via Project Gutenberg http:// www.gutenberg.net/index.shtml.
A first-order Markov Model (MM) was developed based upon 2 character transition frequencies. The MM is termed "first-order" because it is assumed that the next state is dependent only upon the current state. Higherorder MMs can take into account more previous states. Words within text are treated as consecutive strings of ASCII symbols, which will be primarily alphanumeric but may also contain non-alphanumeric symbols. A state transition matrix was constructed to track transitions between characters with ASCII values ranging from 32 to 125. Because characters outside this ASCII range occur at generally low frequencies in both words and chemical names, they are all treated as "wildcard" characters having a value of zero. Also, brackets ("][") are converted to parentheses prior to MM evaluation, but are preserved when entering putative chemical names found within text into a database. All words were formatted prior to MM scoring by removing surrounding parentheses, brackets and quotation marks (single & double). Furthermore, certain "tag-along" word prefixes and suffixes were noted where the rightmost hyphen effectively ended the chemical name and began the next English word (e.g. "methoxyspecific", "non-hydrochloride", "glutamine-rich"). Words were stripped of suffixes that followed the following patterns prior to processing: ('t, 's, (s), -or, -to, -and, -the,old, -rich, -specific). The prefix "non-" was also stripped. These represented the more common patterns and are not an exhaustive list of "tag-alongs". Only chemical names 255 characters in length or shorter were recorded. After processing all MEDLINE abstracts, only 65 chemical names were found to be > 255 characters long. Long chemical names are anticipated to be more common in full-text analysis, since abstract space is usually restricted.
When using an MM to identify and classify a string of characters, the goal is to determine the most likely sequence of tags (states) that generates the characters in the word. In other words, given a word V, calculate the sequence U of tags that maximizes P(V|U). A paper by Rabiner [17] provides a good tutorial on the use of MMs (including HMMs) overall, while Charniak discusses MMs more specifically within the context of sentence and word processing [18]. Because there is a considerable amount of literature on MM theory and construction, it will not be discussed in detail here. Figure 1, however, provides an example of how words are scored and evaluated under different MM models.
To discriminate between the highest scoring model and the next highest, their log 10 ratio is calculated. This ratio reflects the statistical confidence in choosing the highest scoring model over the next highest and is referred to as the confidence score (which is sometimes also referred to as the log-likelihood ratio). Because some chemical names are very long (>150 characters), probabilities were calculated using a double-precision floating-point variable (8 bytes). To avoid sparseness of the state transition matrix (STM), a pseudo-value of 0.001 was used in place of zero-values. This way, the probability of a given character sequence not previously observed within one model is penalized, but does not automatically assign a value of zero regardless of the other characters observed. Alternatively, one could use a pseudo-value of 1/(# of states)^2, which would be closer to 0.0001, but initially, the MM was case-insensitive and had a lower number of states, so the value was closer to 0.001.

Results
A first-order MM was first trained using approximately the first half of the ChemID database, which consisted of 194,000 entries (primary names + synonyms). Values of the state transition matrix were tracked during the training to observe model convergence, and gain an idea of how many examples are required to effectively train the MM on chemical names. Figure 2 graphically illustrates the results of the training, where changes in the state transition matrix (STM) values are summed each time the MM is trained on a new word, yielding a value (delta) that corresponds to how much the STM probabilities have changed (given as an absolute value) upon seeing a new example. For example, if the probability of transitioning from the letter A to the letter B was 0.03 after X examples were observed and upon seeing example word X+1, this value changed to 0.02, the magnitude of this change would be 0.01 and delta would be calculated by summing all the changes. In these graphs, delta is calculated over every 10 training examples. As more training examples are used, fewer new patterns are seen by the MM and delta should converge towards zero. Without the character handling mentioned in the Systems and Methods section, a stable convergence was difficult to reach even with 194,000 examples. However, when rare characters are treated as "wildcards" (e.g., relatively rare characters such as "~" and "|" would be treated as the same symbol), MM convergence occurs faster (data not shown). For comparison, training set convergence is shown for words in scientific abstracts (Figure 2b

MM Recall Rates on ChemID Test Set
Abstracts are processed by sentence and each sentence is broken into words by separating the sentence based upon the presence of spaces. Only words with at least 4 characters are scored. Because chemical names can either be contiguous or a series of terms (e.g. "chloroquine sulfate", "13-Docosynoic acid", "Glycine ethyl ester hydrochloride"), proximal terms are concatenated when each term is above the scoring threshold.
After MM training, a test set of 20,000 entries was selected from ChemID that were not included in the training set. The entire test set should be correctly predicted to be chemicals, so any that were not so predicted were classified as false-negatives (FNs). Each individual word within the ChemID entry was passed to the MM for evaluation in the same manner words within sentences would be processed (e.g. if the entry was "2-hydroxy-benzyl alcohol" then each word would be sent separately). By definition, there are no false-positives in this set, so this step was designed to estimate recall rates. Precision was measured by testing the MM on a set of non-chemical words and determining how many were falsely classified as chemicals. Example of the principle by which a first-order MM works using the words "ethanol" and "booze" Figure 1 Example of the principle by which a first-order MM works using the words "ethanol" and "booze". State transition frequencies are calculated for each letter in a word (including spaces on both sides of the word) and compared with models the MM has been trained on; in this case chemicals and words. The probability of observing a sequence of letters within each model is calculated as the product of each state (character) transition. To reflect a statistical distance between two models, the log 10 ratio is taken.
From these 20,000 entries, there were a total of 9,723 unique terms (e.g. the word "methyl" appeared in many different chemical names, but for evaluation purposes was only counted once). Without using a cutoff score, a total of 509 chemical component terms (5%) were erroneously classified as words and 7,697 out of 304,650 non-chemical words submitted (2.5%) were erroneously classified as chemicals. However, there were only a total of 480 unique words within these 7,697. Figure 3 shows how the choice of a cutoff score affects the precision and recall of the system, with recall being defined as True Positives/(True Positives + False Negatives) and precision being defined as True Positives/(True Positives + False Positives). Precision is also commonly referred to as specificity and recall as sensitivity. Most entries receiving very low scores (i.e. those classified as a word with high confidence) did not contain chemical groups, but were more like alphanumeric identifiers (e.g. U-58176, K442), while others were words used to describe a chemical compound or its preparation (e.g. brilliant, brown, mixture, bark, powder).

Recognizing full chemical names
The previous step measured the ability of the MM to identify individual component terms, but not the ability to recognize entire terms, which will be important when analyzing text. The number of components within a chemical name was also tracked, and the ability of the MM to correctly identify all components of a term was also high. The first 20,000 chemical terms of the test set were processed, totaling 8,283 entries. Of these, 6,243 database entries had all their component terms receive a score above 1 (75.4%), 1,781 terms had at least one component term receive a score above 1 (21.5%) and 258 terms had no component scoring above 1 (3.1%). It was particularly problematic for the MM to correctly identify short terms (1-4 characters) found in some chemical names (e.g. "Actinomycin D", "Strychnos gum" "Antifoam B"), especially if the term was a trade name or description (e.g. "Sun Yellow K", "Swascofix E 45", "Idet 20").
Note that even though precision per word is very high (see Figure 3), this small error rate can translate into many errors when analyzing large corpora. For example, if we assume MEDLINE contains 7 million abstracts at an average 200 words per abstract that equals 1.4 billion words. At a 1% error rate, that would total approximately 14 million errors. Not all errors will necessarily come from different words, and so the total number of unique errors may be far different. To evaluate this, we processed all of MEDLINE, using a cutoff score of 1, which is estimated by these measurements to yield approximately 92.8% recall (per chemical name present) and 99.5% precision (per word analyzed).

MM Precision on MEDLINE abstracts
A total of 13,154,593 MEDLINE records were processed, containing 7,439,689 abstracts. Each word at least 4 characters long within an abstract was sent to the MM for evaluation using a cutoff score of 1. Each word scored as a chemical name was marked within the abstract and consecutive words receiving a cutoff score greater than one were concatenated into a single entry for deposition into an SQL database. Exceptions were made when a comma followed by a space was found within the entry. In these cases, the entries were treated as separate chemicals (i.e. a list). If a chemical name was found more than once, a frequency counter was incremented for that term.
After all abstracts had been processed, a total of 33,929,499 putative chemical recognition events were recorded, yielding a total of 1,052,654 unique putative chemical names recognized within MEDLINE. From this database, random samples of 100 entries were taken for several ranges of cutoff scores. Each putative chemical name entry in this database was extracted with its surrounding sentence for manual evaluation. Random sampling was repeated 3 times to permit an average and standard deviation to be calculated. A database entry was considered to be correct if the entry was the name of a chemical compound, a chemical group or side-chain, or the name of a family of chemical compounds. If an extra The effects on precision and recall rates from using a cutoff score Figure 3 The effects on precision and recall rates from using a cutoff score. Test sets containing chemical names and words were evaluated with an MM trained on both types of data and cutoff scores ranging from 10 to zero were used to define which entries were valid. The data points from left to right reflect the precision and recall rates obtained by using each cutoff value, shown in descending order from 10 (far left) to zero (far right). The optimal tradeoff between precision and recall appears to be somewhere between a cutoff of one and two.
word flanked the chemical on either side, it was not considered an error as long as the rest of the term was a chemical name. For example, in the entry "hydrolyzed alphanapththyl acetate", the word "hydrolyzed" is not part of the proper name, but the proper name "alpha-napththyl acetate" is nonetheless identified and thus not counted as an error. Similarly, the entry "disoxaril/ml" was extracted from the sentence "0.3 mg disoxaril/ml" and not counted as an error. Protein entries were counted as errors, but not single amino acids. Gene names were also counted as errors, unless the gene was named after a chemical process (e.g. Alkaline Phosphatase). Table 3 summarizes the results of this analysis. The number of false-positive errors rises significantly upon large-scale analysis of a biomedical corpus, but fortunately remains within a reasonable range. The most problematic entries were those with the lowest cutoff, as expected, but it was encouraging to see a significant number of chemical names receiving high scores.
A number of words erroneously recognized as chemicals had at least one syllable that closely resembled a common pattern found within chemical names (e.g. "examine", "suicide", "prophylactic", "paramecium"), or were descriptive words used in chemical nomenclature (e.g. cyclic, solid, hydrophilic, alpha).

Chemical Name Variance Within MEDLINE
Although the International Union for Pure and Applied Chemistry (IUPAC) has set forth well-established guidelines on chemical nomenclature (see http:// www.chem.qmw.ac.uk/iupac/), and software is also available to generate standard IUPAC names from chemical structures and vice versa http://www.acdlabs.com/prod ucts/name_lab/name/, it is not known how consistently authors follow these conventions. Table 1 offers an example of morphological (spelling) variation for the chemical 8-SPT, illustrating the many permutations that can be derived from a single chemical name. To test how this variation affects information retrieval, several of the more common variations of this chemical name were selected. First, Ovid was used to map the terms to a medical subject heading (MeSH term). Second, the PubMed search engine was queried using the same terms to see how many articles would be retrieved. Table 2 shows that this variation in the construction of a chemical name is not necessarily a trivial matter, since it affects the number of records retrieved per PubMed query as well as attempts at mapping terms to subject headings. In the cases where PubMed found over 200 entries, the term was successfully mapped to the MeSH term "8-(4-sulfophenyl)theophylline", which is classified as a "substance name". This dependency upon specific term construction profoundly affects information retrieval. Thus, we sought to get a bet-  ter estimate of how much variation there is within MEDLINE in the construction of chemical names.
Our goal was to identify chemical names that are used to refer to the same chemical compound, yet vary in their morphological construction. Table 1 offers a good example of the considerations that must be taken into account while doing this. For the chemical 8-SPT, the most common morphological construction is 8-(p-sulfophenyl)theophylline. Within the list, a number of variations on this can be seen. Existence and placement of either parentheses or hyphens account for most of the variation, but there is also a variation within component terms. The "p" is used to indicate the presence of a para group, and in five out of 24 cases is not present. Some entries, apparently errors, list this "p" as a "4" or a "rho", both of which strongly resemble a "p" (perhaps errors that occurred during data-entry or optical character recognition?). In 8 out of 24 cases, the sulfur group is spelled with a "ph" instead of "f". Finally, one variant spells "theophylline" without the "e", which is probably a spelling error rather than an intentional variation. These last few examples suggest that simple rules for comparing terms, such as removing punctuation and spaces, will not adequately capture term variation. Aligning terms and evaluating them by percent similarity would solve these problems, but raises another. In some cases, such variation is critical to the nature of the compound. For example, consider enantiomer designations of L-alanine versus D-alanine, which can also be represented as (+)-alanine or (-)-alanine, amines versus amides or imines, methyl groups versus ethyl groups, R versus S chirality, and numeric placement of side chains. All these terms vary by one character, and thus evaluating them by percent similarity would falsely suggest that these types of terms are equivalent when they are not. An imperfect solution is proposed so that an estimate can be obtained, by using a heuristic acronym-definition resolution routine to resolve acronyms when explicitly defined within the text [19,20]. The rationale and assumption for pairing chemical names with their acronyms is that authors should usually be aware of which minor (fewcharacter) distinctions signify a closely related yet chemically distinct compound and will strive to reflect this distinction when defining an acronym for the compound, to avoid both nomenclature ambiguity and confusing the reader. We first test how well this assumption holds up by examining how many of the R/S, D/L and (+)/(-) variants in chemical names are both defined using only one acronym.

Pairing Chemical Names with their Acronyms
Querying the January 2004 version of the ARGH database, 435 acronym-definition pairs were found beginning with either "(+)" or "(-)", and 9 acronyms were used for both the (+) and (-) designations; for the 1,514 acronym-defi-nition pairs beginning with the patterns "R-*" or "(R)*" or the patterns "S-*" or "(S)*", 8 acronyms were used for both the R and S designations; and for the 3,380 acronymdefinition pairs beginning with either D-or L-, 22 acronyms were used for both the D and L designations. On average then, within the samples taken, a unique acronym does not distinguish stereo descriptor variants 0.7% (39/ 5329) of the time. From this, it seems reasonable to assume that pairing chemical names with their acronyms permits an additional quality control check when trying to ensure that the variation observed between two similar terms is indeed variation of the same chemical name. A disadvantage is that not all chemical names will have their acronyms defined within each abstract, but this should not prevent obtaining an estimate of term variance.
Definitions from the ARGH database were scored by the MM and their acronym retrieved if they were scored as a chemical name. Each definition having the same acronym as the chemical name was then aligned using a dynamic programming algorithm similar to the FASTA algorithm [21]. A similar approach using BLAST was successful in identifying gene names within text [22], although in this case we are adding an additional control to ensure the two terms refer to the same compound. If two definitions shared the same acronym as well as 75% of their characters upon alignment, they were considered spelling variants. Analysis was restricted to chemical names with a confidence score of 1 or greater and those that were mentioned within MEDLINE at least twice. All comparisons were conducted in a case-insensitive manner. A total of 12,155 acronym definitions were classified as chemical names, and 4,345 had at least one spelling variant. A total of 15,288 variants were detected by these criteria, giving an average number of spelling variants per chemical name of 1.26. However, because the distribution in the number of variants found follows an inverse power-law distribution, taking a simple average is perhaps not the most appropriate means of expressing variation -there is an extreme disparity in how many times each of these chemical names is mentioned within MEDLINE. A more informative way of visualizing this variation is to examine the relationship between the number of times a chemical name is published and the number of spelling variants observed.
As Figure 4 shows, the number of variants per chemical name was correlated with the number of times the chemical name appeared in the literature, suggesting that variation in the precise construction of many chemical names is, to a degree, inevitable and a function of how many times it is written. Some names, such as norepinephrine, are mentioned many times within MEDLINE yet have very little variance because they have few component terms.
Using the 510 chemical names that had their acronyms defined at least 50 times within MEDLINE, whether a spelling variant was detected for them or not, we found that 490 (96%) had at least 1 variant. When the most commonly observed spelling form is expressed as a percentage of the total number of observations for chemical names (see Table 1 for an example), on average it comprises the majority of total definitions observed (71% ± 26%). This suggests that the most common spelling form of any chemical name can be used to retrieve the majority of occurrences of that chemical name within a textual database, but will fail to retrieve a large percentage of significant records in the absence of methods to identify potential variants.

Discussion
The results of this report suggest that using a Markov Model provides a straightforward and accurate way to recognize chemical names within any textual source. The overall precision rates were highly encouraging; especially considering such a large corpus had been analyzed. The biggest limitations of the MM in identifying chemical names within text were two-fold: First, and most noteworthy, there were many "tag-along" prefixes and suffixes that accompanied many of the chemical names. As a consequence, the total number of unique chemical names in MEDLINE would be overestimated by this study (e.g. "doxorubicin" and "doxorubicin-based" should be the same, but have separate entries). Second, and particularly for the lower-scoring chemical names, the MM was unable to correctly determine starting and ending points for the named chemical, especially when one of the ends is defined by a short (1-4 character) word. Encouragingly, though, because the MM does have a relatively high precision in identifying chemical morphemes, that provides a good starting point for further refinements in extracting the full-name. This did not seem to be as much of a problem as when chemical prefixes were separated by English words -the MM was able to pick up the prefixes, but not to pair them with their name (e.g. "Activities for tyrosinephenol were measured along with the related substitutions -toluene and -benzene").
One possibility for further refinement that was not explored in this report is the construction of a higherorder MM. That is, a MM that takes into account transition frequencies between 3 or more characters at once. As per the example given in Figure 1, this would entail calculating the probability for both words and chemicals that the letters e-t-h would occur in that order for each model. Because the STM would become sparser (i.e. there would be more transition values equal to zero because certain transition patterns will never be observed within a given model and limited training set), it is reasonable to hypothesize that a gain in precision could be achieved. However, it is neither clear how recall would be affected, nor the size of the required training set. Also a possibility for improvement, specifically in the area of identifying the shorter prefixes, suffixes and infixes associated with chemical names, is the construction of a Hidden Markov Model whereby word substructures are represented as the hidden state and the model trained to maximize the probability of a phrase boundary being reached.
The number of spelling variants for a given chemical name is correlated with the number of times it has appeared within the literature Figure 4 The number of spelling variants for a given chemical name is correlated with the number of times it has appeared within the literature. Here the number of spelling variants per chemical name is plotted against the total number of times the chemical name and all variants appeared within MEDLINE. The black line represents a 100-period moving average.