Nathalie Aussenac-Gilles

Anne Condamines
email: anne.condamines@univ-tlse2.fr

Variation and Semantic Relation Interpretation: Linguistic and Processing Issues

Keywords: Pattern-based relation extraction, lexico-syntactic patterns, semantic relation, tool comparison, pattern variation 1

Studies in linguistics define lexico-syntactic patterns to characterize the linguistic utterances that can be interpreted with semantic relations. Because patterns are assumed to reflect linguistic regularities that have a stable interpretation, several software implement such patterns to extract semantic relations from text. Nevertheless, a thorough analysis of pattern occurrences in various corpora proved that variation may affect their interpretation. In this paper, we report the linguistic variations that impact relation interpretation in language, and may lead to errors in relation extraction systems. We analyze several features of state-of-the-art pattern-based relation extraction tools, mostly how patterns are represented and matched with text, and discuss their role in the tool ability to manage variation.

Introduction

Knowledge representation in most onto-terminological resources (ontology, terminologies, thesaurus…) refers to relational networks and more precisely, concepts related by binary relationships, either hierarchical like hypernymy, or not, like causality, possession, qualities or properties. When building this representation from text, the state-of-the-art talks about 'concept extraction' and 'relation extraction', which assumes that language produces direct evidences of these knowledge structures. Many relation extraction tools parse texts as if binary relationships could directly be associated with some predefined sequences of syntactic or lexical tokens. Among all possible implementations, we focus on pattern-based approaches. When using patterns, there is a strong temptation to look for schemes (i.e. noun_phrase/verb/noun_phrase sequences) in text and to map them to concept/relation/concept triples. Nevertheless human interpretation relies on much more subtle and complex linguistic associations and on hidden background knowledge. So far, a large variety of concept and relation extraction tools have been implemented for research purposes. They may either assist concept and relation identification in text, or run the entire process from language analysis to knowledge modelling.

It is not trivial to identify textual contexts that may reveal semantic relations, and then to decide of the relations that can be represented. Accounting for the linguistic features that contribute the relation interpretation is already complex, regardless of any automation perspective.

In this paper, we browse the various linguistic and technical issues that may arise at the various stages of this process. We discuss how existing studies or systems carry out these stages and manage (or not) to overcome these issues. Examples of such issues are: what are the relevant linguistic marks to identify concept/relation/concept triples? What are the observable variations that may affect the interpretation of semantic relations? How far can tools assist this process? How could tools better anticipate these variations? In first two sections we adopt a linguistic point of view. The next two sections aim to connect the issues raised by the linguistic observations with some of the features of pattern-based relation extraction systems. We conclude with perspectives to better support relation extraction with software tools.

Linguistic variation in lexical relation interpretation

Knowledge rich contexts are parts of text which may be interpreted by human as giving information about a term and even by giving it under structures such as term/relation/term. But this interpretation process faces two types of problems which make it hard to carry out by a software tool.

Variation affecting relation interpretation

In her paper [START_REF] Meyer | Extracting Knowledge-rich Contexts for Terminography: A Conceptual and methodological Framework[END_REF], Meyer speaks about knowledge rich contexts (KRC). The KRC term notifies that some parts of texts are richer than others concerning knowledge but it does not specify that these parts may be represented under a term/relation/term triple. The linguistic characterisation of KRC is complex [START_REF] Flowerdew | Definitions in Science Lectures[END_REF], [START_REF] Pearson | The Expression of Definition in Specialized Texts: A Corpusbased Analysis[END_REF], [START_REF] Marshman | Lexical Knowledge Patterns for the Semi-automatic Extraction of Cause-effect and Association Relations from Medical Texts: A Comparative Analysis of English and French[END_REF]. It requires analyses that go beyond the sentence level to take paragraphs into account; it requires not only to justify the relation label but also to locate the related terms. A valid interpretation and triple definition would require detailed and deep linguistic analyses. More generally, sentences that contain standard patterns are not very frequent or they may lead to some semantic relations that are not relevant to be included in a knowledge model.

Instability within discourse

Spotting term/relation/term in texts is not easy. The role of language, even in specialized fields doesn't consist in referring to knowledge by using explicit triples. In addition, speakers do not always intend to express domain knowledge. Some definition contexts are very implicit and may be considered as such only by the linguist, the terminologist, or the knowledge engineer who wants to define concepts. We identified the following four categories of problems, that is to say differences between an a priori interpretation of discourse functioning and the actual term-relation-term structure.

One of the terms-concepts is missing. In case of anaphora, a hypernymy relationship may link a first term in a phrase and another one in another phrase. For example in … a car. This vehicle…., this vehicle refers to the same object as car in the previous sentence and there is a hypernymy between vehicle and car. But in some cases, it is not possible to identify a term with which the second term may be related such as in:

(1) The configuration units to be modified must be identified […]. The result of this activity is the drawing up of the modifications file. Because this activity refers to something presented in the previous sentence, Activity can be identified as a hypernym. But no term in the previous sentence may be understood as a hyponym: the hyponym is meant by the whole phrase "the configuration units to be modified must be identified". T1 and T2 have not the same grammatical nature. In ontologies, most of the concept labels are noun phrases, but verbs or adjectives can also be found. Depending on the relation nature and on the term meaning, it may be odd or even erroneous to connect concepts with labels of a different grammatical nature (a noun and a verb for example). Though, such a connexion may exist in discourse. In example [START_REF] Flowerdew | Definitions in Science Lectures[END_REF] (2) The numbering of cables consists of identify and number each cable for an electrical cupboard. the first term (numbering of cables) is a noun phrase while the second one (identify and number…) is a verb phrase. The pattern consists of is well known as playing a role in definition so this context may be identified as expressing an equivalence between two terms. The first term probably is a kind of elliptical form of the second one: numbering of cables is equivalent to identifying and numbering each cable for an electrical cupboard.

Pattern and T2 are present in the same word. In some cases, a word matches both the pattern under prefix form and term2 of the triple. From example (3) one may deduce that calcium generally is a constituent of bone.

(3) This bone is decalcificated. The privative prefix de marks mainly that a component, generally present in the whole object, is suppressed (such as in decaffeinated). So, this prefix may be used as a meronymy mark. But it is not always the case. For example, from depolarization, it is not possible to deduce that there is a meronymic relation between polarization and the object which is depolarized. Morphological features are not easy to describe and even more to introduce in a tool.

For examples (1), [START_REF] Flowerdew | Definitions in Science Lectures[END_REF], and (3), discourse analysis is required to build a term/relation/term triple with the help of human interpretation. So far, tools are not suitable to account for such discourse behaviors. Some linguistic phenomena have not been really described from a linguistic perspective and even less with the aim of building ontologies or terminologies. There is a problematic lack of linguistic studies usable for designing tools.

Variation when building a representation

Six phenomena are examined in this paragraph: sub-relationships, polysemy of patterns, multiple possible meanings, implicit relationship, rhetorical effect and indirect interpretation.

Polysemy of patterns. Some patterns may correspond to two different relationships not necessarily specific of another relationship [START_REF] Meyer | Extracting Knowledge-rich Contexts for Terminography: A Conceptual and methodological Framework[END_REF]. It is the case of comme in French (corresponding to as in some English examples) [START_REF] Condamines | Taking genre into account for analyzing conceptual relation patterns[END_REF]. In [START_REF] Marshman | Lexical Knowledge Patterns for the Semi-automatic Extraction of Cause-effect and Association Relations from Medical Texts: A Comparative Analysis of English and French[END_REF], this pattern reveals a hypernymy (decorative flower is hypernym of rose) wheres as in [START_REF] Condamines | Taking genre into account for analyzing conceptual relation patterns[END_REF], the relation between the two nouns is rather co-hyponymy (Rose and orchid are both hyponyms of flower):

(4) La rose comme fleur de décoration est très appréciée (The rose, as a decorative flower, is very much appreciated).

(5) La rose comme l'orchidée sont très appréciées des clients. (Roses as well as orchids are very much appreciated by customers.)

In some cases, the difference between interpretations may be explained by syntactic context and by textual genre. But again, this characterization requires fine-grained and time-consuming analyses.

Multiple possible meanings: class vs instance. According to the aim, the same sentence can get different interpretations either at the class or the instance layer. For instance, [START_REF] Garcia | Analyse automatique des textes pour l'organisation causale des actions, Réalisation du système Coatis[END_REF] Roses are Marie's favorite flowers can be interpreted at a general level, to learn the <rose, sub_class_of, flower> triple, or < person, hasFavoriteFlowers, Roses>. The two interpretations sound correct but the first one (the hypernymic relation) will be preferred to be integrated in an ontology. But the same sentence could also provide a probe for a relation between instances like <Marie, hasFavoriteFlowers, rose> where rose could be an anonymous instance of the Rose class.

Implicit relationship. In some cases, a pattern that systematically means a relationship can have a better interpretation which refers to another relationship. That may be the case for example with the succession relation that can be interpreted as a causative one [START_REF] Marshman | Lexical Knowledge Patterns for the Semi-automatic Extraction of Cause-effect and Association Relations from Medical Texts: A Comparative Analysis of English and French[END_REF], [START_REF] Garcia | Analyse automatique des textes pour l'organisation causale des actions, Réalisation du système Coatis[END_REF]. Example [START_REF] Condamines | Corpus Analysis and Conceptual Relation Patterns[END_REF] expresses a succession to be interpreted as a cause: rain stopping causes the beginning of the show: [START_REF] Condamines | Corpus Analysis and Conceptual Relation Patterns[END_REF] The show will begin when the rain will stop. From a linguistic perspective, these cases are well known. Nevertheless, in some sentences when has to be associated only with a temporal interpretation (succession or concomitance) as in ( 8):

(8) It was very cold when I went to New York last year.

Rhetorical effect.

As parts of speech, patterns may be involved in rhetorical processes. Let's examine the sentence below.

(9) The component integration phase may begin when all the software elements have been implemented. This example should be understood as meaning that software elements must first have been implemented for the component integration phase to begin. Therefore the expressed relation looks like a temporal relation but it must be understood as a conditional one. So, what is presented as just temporal information has to be considered as an injunction. The aim of using a temporal connective is to weaken the order effect. In examples ( 7), ( 8) and ( 9), the same pattern when may be understood either as a temporal, a causative or a conditional one. Some linguistic elements of the context may be used in order to disambiguate these possible interpretations but in some cases, the whole situation (linguistic and extra-linguistic context) is necessary in order to obtain the good interpretation.

Indirect interpretation. This case is very interesting because it highlights the fact that linguistic and knowledge engineering needs may lead to different descriptions. This is the case with chez (that may be translated by among in English). Some sentences containing chez/among may be used in order to build a meronymic relation as in [START_REF] Barrière | TerminoWeb: a software environment for term study in rich contexts[END_REF], where it may be understood that there is a meronymic relation between nose and colobines.

(10) Among the colobines, the nose juts out over the upper lip. As described in [START_REF] Condamines | Taking genre into account for analyzing conceptual relation patterns[END_REF] and [START_REF] Condamines | Corpus Analysis and Conceptual Relation Patterns[END_REF], this interpretation appears in texts of didactic origin dealing with natural science: in such texts more than 50% of the sentences where chez occurs contain a meronymic relationship.

But it is not true to say that chez systematically leads to a meronymic relation: nobody spontaneously produces this preposition with a meronymic meaning and its etymology (from the Latin casa (house)) is in no way linked to such an interpretation. A detailed analysis shows that this preposition occurs in structures in topic position (at the beginning, the middle or the end of the sentence), i.e. in structures that introduce a new referent into the discourse. In didactic natural science texts, what is often said about these new referents (animals or plants) has to do with their anatomy or composition. Thus chez may be used as a sort of clue instead of really a complete pattern.

Multiple binary relations.

A final difficulty arises when looking for multiple binary relations or n-ary relations. Compared to what actually occurs in text, concept-relation-concept triples are not very convenient to represent n-ary relations. For example, it is complex to build the patterns that would identify a communication n-ary relation [START_REF] Condamines | Searching for and Identifying Conceptual Relasionships via a corpus-based approach to a Terminological Knowledge Base (CTKB): method and results[END_REF]: NP1 (person) communicates NP2 (information) to NP3 (person) through NP4 (mediaM) as in [START_REF] L'homme | Terminological Relationships and Corpus-based Methods for Discovering them: An Assessment for Terminographers[END_REF] Each subdivision transmits to CIGT a form related to complete site. In this example, the three verb arguments are intrinsically tied, it appears clearly that binary relations are restrictive and do not convey the fact that the 3 binary relations have to co-occur.

Textual Genre and Pattern Meaning

It is obvious that the interpretation of some conceptual patterns is genredependant [START_REF] Condamines | Taking genre into account for analyzing conceptual relation patterns[END_REF]. In other words, the probability for a word or a structure to be interpreted as a conceptual pattern is not equivalent in every text. Here is just the example of avec (with) and the results obtained from texts belonging to different genres. The corpus gathers texts belonging to five genres: A Zola novel: Germinal, 210,000 words, noted GER. A scientific handbook: "Manuel de géomorphologie", (Geomorphology handbook) 206,700 words (abbreviated as "GEO"). A toy catalogue (Catalogue de jouets Leclerc), 93,000 words (T.C). Real estate adverts collected from 3 web sites, 22,600 words (P.A). Itinerary descriptions (a corpus constituted for the purpose of a psycholinguistic study), 48,000 words (ITI).

The table 1 Two groups of corpora can be identified. In the first one (GER and GEO) the number of meronymic avec occurrences is very low. In the second one (T.C., P.A., ITI), the number of meronymic avec occurrences is very high. This observation warrants the claim that avec may be considered as a conceptual pattern with a high probability within this second group of corpora. During the last 20 years, the automatic search for semantic relations has been the goal of studies in information extraction [START_REF] Agichtein | Snowball: Extracting relations from large plain text collections[END_REF], terminology collection from corpora [START_REF] Barrière | TerminoWeb: a software environment for term study in rich contexts[END_REF], [START_REF] L'homme | Terminological Relationships and Corpus-based Methods for Discovering them: An Assessment for Terminographers[END_REF], [START_REF] Soler | Patrones léxicos para la extracción de conceptos vinculados por la relación parte-todo en español[END_REF], and ontology engineering from text [START_REF] Maedche | Discovering conceptual relations from text[END_REF], [START_REF] Aussenac-Gilles | Designing and Evaluating Patterns for Relation Acquisition from Texts with Caméléon[END_REF], [START_REF] Buitelaar | Ontology Learning From Text: Methods, Evaluation and Applications[END_REF], [START_REF] Malaisé | Mining defining contexts to help structuring differential ontologies[END_REF], [START_REF] Pantel | Expresso: leveraging generic patterns for automatically harvesting semantic relations[END_REF], [START_REF] Velardi | Evaluation of Ontolearn, a methodology for automatic learning of domain ontologies[END_REF]. Semantic relations may be either directly provided by domain experts, acquired from text or reused from existing lexical or semantic resources. We focus on systems that build semantic relations thanks to pattern matching because they are particularly efficient to identify domain-specific relations and to label them precisely. We evaluate their ability to capture the variations presented in section 2.

Searching for relations thanks to pattern occurrences in text relies on several foundational assumptions [START_REF] Hearst | Automatic Acquisition of Hyponyms from Large Text Corpora[END_REF]: (i) relation expressions are regular enough to be anticipated; (ii) relations can be found with similar formulations in any corpus; (iii) relation expressions match sequences of lexical entries and grammatical categories; (iv) in a body of text, a linguistic pattern is interpreted with a unique meaning. These hypotheses are being refined to find out efficient implementations that reduce noise and improve recall.

One limitation of pattern-based relation extraction is its low productivity: searched texts may contain very few explicit formulations of relations; depending on the text genre, patterns may occur very scarcely. Handbooks and lecture notes are acknowledged as adequate document genres for hypernymy and definition relation extraction. But novels for instance contain very few occurrences of Hearts's hypernymy patterns [START_REF] Hearst | Automatic Acquisition of Hyponyms from Large Text Corpora[END_REF]. Pattern matching has a moderate success because of variation, which lowers recall: relations occur with different meanings or formulations, so that patterns miss many occurrences. From now on, we will adopt a knowledge engineering perspective and consider patterns not only as means to account for linguistic phenomena, but also as tools to get linguistic clues of the knowledge to be represented.

Tools for pattern-based search for semantic relations

Our study relies on several state-of-the-art surveys [START_REF] Auger | Pattern based approaches to semantic relation extraction: a state-of-the-art[END_REF], [START_REF] Halskov | Web based extraction of semantic relation instances for terminology work[END_REF], [START_REF] Pantel | Automatically Harvesting and Ontologizing Semantic Relations[END_REF], [START_REF] Staab | Ontology Learning for the Semantic Web[END_REF]. Each of these papers reports a dozen of different tools, among which we identified four types of software that assist relation mining in text.

Text analysis platforms enable the deployment of natural language processing applications by combining basic components that apply at different linguistic levels. For instance, Gate1 includes the ANNotations In Context (ANNIC) plug-in to identify concepts and relations thanks to rules that implement patterns. ANNIC can be used to annotate a corpus or to query annotation contexts [START_REF] Maynard | NLP techniques for Term Extraction and Ontology Population[END_REF]. LinguaStream2 , Alvis3 or UIMA 4 are other such platforms. [START_REF] Morin | Patrons lexico-syntaxiques pour aider au dépouillement terminologique[END_REF], Caméléon [START_REF] Aussenac-Gilles | Designing and Evaluating Patterns for Relation Acquisition from Texts with Caméléon[END_REF] or RelExt [START_REF] Schutz | RelExt: A tool for relation extraction from text in ontology extension[END_REF] are dedicated to relation extraction either with or without the identification of related terms. [START_REF] Barrière | Building a concept hierarchy from corpus analysis[END_REF] proposes a tool to extract taxonomies from text, Terminoweb [START_REF] Barrière | TerminoWeb: a software environment for term study in rich contexts[END_REF], Expresso [START_REF] Pantel | Expresso: leveraging generic patterns for automatically harvesting semantic relations[END_REF] and Snowball [START_REF] Agichtein | Snowball: Extracting relations from large plain text collections[END_REF] are able to identify together a relation type and related terms.

Independant relation extraction tools: tools like Prométhée

Ontology engineering platforms that use text as knowledge sources: Platforms such as Text-To-Onto [START_REF] Soler | Patrones léxicos para la extracción de conceptos vinculados por la relación parte-todo en español[END_REF], OntoLearn [START_REF] Pantel | Expresso: leveraging generic patterns for automatically harvesting semantic relations[END_REF] or Terminae [START_REF] Aussenac-Gilles | The TERMINAE Method and Platform for Ontology Engineering from texts[END_REF] support a methodology and include tools to look for terms and semantic relations.

Specific relation extraction tools:

tools may be dedicated to a particular type of application or domain such as bioinformatics, for instance PASTA [START_REF] Gaizauskas | Protein structure and information extraction from biological texts : The PASTA system[END_REF], RelationAnnotator [START_REF] Mukherjea | Discovering biomedical relations utilizing the world-wide web[END_REF], works by [START_REF] Khelif | An ontology-based approach to support text mining and information retrieval in the biological domain[END_REF], [START_REF] Nédellec | Machine Learning for Information Extraction in Genomics -State of the Art and Perspectives[END_REF], or [START_REF] Ramakrishnan | Unsupervised discovery of compound entities for relationship extraction[END_REF].

Learning based tools: these tools exploit knowledge models or lexical resources (like WordNet) that provide pairs of related terms to learn new patterns from very large corpora. Because hypernyms are more easily observed in corpora, many of these tools learn taxonomic relations like [START_REF] Snow | Learning syntactic patterns for automatic hypernym discovery[END_REF] or TaxoLearn [START_REF] Navigli | A Graph-based Algorithm for Inducing Lexical Taxonomies from Scratch[END_REF]. Other relations like causality, parthood or domain specific relations are searched by [START_REF] Girju | Automatic Discover of Part-Whole Relations[END_REF], [START_REF] Feliu | Relacions conceptuals i terminologia: analisis i proposta de deteccio semiautomatica[END_REF] or with Prométhée [START_REF] Morin | Patrons lexico-syntaxiques pour aider au dépouillement terminologique[END_REF].

Variation and Pattern-based Relation Extraction

In the following, we will identify the help that a tool can provide to relation extraction. Automatic extraction is easier in systems dedicated to a restricted number of relation types or to a specific kind of corpus. The internal representation of patterns as well as the ability to adapt them impacts the system ability to manage variations in relation formulations, but it cannot be predicted from the degree of automaticity. Some systems enable pattern learning so that they can adapt to each new corpus or domain, in such a way that automation contributes to better anticipate variations and to define more efficient patterns.

Anticipating Variation during Pattern Definition or Learning

Pattern definitions can be adapted to variation in systems that allow pattern reuse, or the search for domain specific relations with ad-hoc patterns.

Pattern Definition Assumes Stability.

There is a strong paradox in trying to account for variation during pattern definition. Patterns try to account for regularity of relation expressions with regular expressions. This hypothesis is even stronger for "generic" patterns, like Hearst's patterns [START_REF] Hearst | Automatic Acquisition of Hyponyms from Large Text Corpora[END_REF]: hypernymy is supposed to be captured by the same set of patterns in any corpus whatever its domain and genre. Nevertheless, practical reuse of generic patterns shows that the hypothesis is reductive. Patterns may be more or less reliable and they may reveal relations with a different meaning from the one expected. Results of matching a set of patterns on several corpora prove to be very useful when reusing these patterns. Such lists can be found in Caméléon for French, in Terminoweb for English and French, in Skeleton [START_REF] Feliu | Relacions conceptuals i terminologia: analisis i proposta de deteccio semiautomatica[END_REF] for Catalan.

A first way to take variability into account at this stage is to allow for generic pattern reuse, evaluation and adaptation to the corpus, like in Caméléon or Terminoweb. Flexibility is increased by identifying corpus-specific patterns. Then users should be assisted in their definition, evaluation and adaptation. When defining a pattern, human interpretation is required to abstract relevant features from corpus sentences, to qualify the meaning of the relation and to select and represent a relevant pattern. The system can provide a database of reusable patterns and an interface for pattern definition or modification. Statistics about pattern use (number of occurrences, precision and recall in other corpora) are useful to guide pattern evaluation, selection or reject.

Pattern Learning from Corpora. Supervised machine learning algorithms offer promising perspectives to exploit abstract regularities from tagged corpora. Similar algorithms can be run to learn either semantic relations and taxonomies from textual evidences like [START_REF] Faure | A corpus-based conceptual clustering method for verb frames and ontology[END_REF] or [START_REF] Sierra | Definitional verbal patterns for semantic relation extraction[END_REF] do it, or lexico-syntactic patterns. A variety of techniques can be used to « induce recurrent patterns » [START_REF] Pantel | Automatically Harvesting and Ontologizing Semantic Relations[END_REF]. The ASIUM [START_REF] Faure | A corpus-based conceptual clustering method for verb frames and ontology[END_REF] pioneer tool classifies the contexts of each verb and abstracts patterns from them. Many such approaches adapt the DIPRE algorithm by Bri [START_REF] Halskov | Web based extraction of semantic relation instances for terminology work[END_REF] like Prométhée [START_REF] Morin | Patrons lexico-syntaxiques pour aider au dépouillement terminologique[END_REF], WWW2rel [START_REF] Halskov | Web based extraction of semantic relation instances for terminology work[END_REF], [START_REF] Ruiz-Casado | Automatising the learning of lexical patterns: An application to the enrichment of Wordnet by extracting semantic relationships from Wikipedia[END_REF] or [START_REF] Blohm | Using the Web to Reduce Data Sparseness in Pattern-Based Information Extraction[END_REF]. The learning process exploits pairs of related concepts and their labels in corpora. The learning cycle consists in (1) building patterns for each context where concept pairs occur in the same sentence, (2) generalizing similar patterns by abstracting each slot, (3) evaluating learned patterns to avoid over generalization. For instance, in [START_REF] Girju | Text mining for causal relations[END_REF] Wordnet is used to search for causal relation patterns in a web corpus. Patterns are expected to match the <NP1 verb NP2> structure where NP1 and NP2 belong to related synsets. For each sentence containing NP1 and NP2, a <NP1 verb NP2> pattern is defined after manual validation to filter out noisy patterns. An alternative algorithm used in Snowball [START_REF] Soler | Patrones léxicos para la extracción de conceptos vinculados por la relación parte-todo en español[END_REF] infers patterns made of surface grammatical features (like POS) that generalize the largest number of relation instances. Expresso [START_REF] Pantel | Expresso: leveraging generic patterns for automatically harvesting semantic relations[END_REF] uses a clustering algorithm to abstract related classes from the terms found in each relation occurrence. In any case, learning patterns requires not only pairs of related concepts as bootstrapping data, but also large corpora with many relation occurrences. For this reason, this method cannot be used to look for domain specific relations in small corpora of technical documents. Moreover, pattern learning assumes that learned patterns will have the same stable interpretation all over the corpus, and that all their occurrences will mean the same type of relation, which is often a too strong hypothesis.

Pattern Evaluation on Corpora. According to [START_REF] Snow | Learning syntactic patterns for automatic hypernym discovery[END_REF] a reliable pattern is one that matches a large set of documents with a high precision, even though its recall is low. Evaluating a pattern reliability requires to estimate the quality of the concept pairs found in a corpus thanks to this pattern. Measures like mutual information between the corresponding terms, Kappa measure [START_REF] Halskov | Web based extraction of semantic relation instances for terminology work[END_REF], or those listed in [START_REF] Buitelaar | Ontology Learning From Text: Methods, Evaluation and Applications[END_REF], can be used to check each learned relations. Related terms should have a stronger correlation value. Pattern quality is estimated by combining kappa values of each sentence extracted with this pattern. Reliability tends to promote precise patterns and leads to define numerous variants to account for linguistic variations. But pattern quality and reliability are not intrinsic pattern features [START_REF] Aussenac-Gilles | Designing and Evaluating Patterns for Relation Acquisition from Texts with Caméléon[END_REF]: they depend on the corpus domain and genre. An experiment on 8 corpora and 30 patterns showed that the same pattern can be frequent and precise in one corpus, and very noisy or rare in other ones.

Pattern structure and its relation with variation management

Pattern is a generic word that accounts for various kinds of structures with a variety of implementations. Each type of structure assumes a particular stability and ability to handle variation, and makes pattern definition and matching more or less complex. Here are some of the mostly used structures: *word1* [+ *word2*]. Patterns made of lexical forms only focus on the informative part of a pattern, i.e. chez (in [START_REF] Buitelaar | Ontology Learning From Text: Methods, Evaluation and Applications[END_REF]) can be a pattern for meronymic relations. Verbal patterns in [START_REF] Sierra | Definitional verbal patterns for semantic relation extraction[END_REF] are of this kind. Although easy to build up from lexical entries, they are not able to find the related terms and they lack abstraction: a large set of patterns is required to account for little variations.

A term1 B term2 C, where term1 and term2 are the related terms and A, B, and C characterize their lexical or grammatical context. In Caméléon [START_REF] Aussenac-Gilles | Designing and Evaluating Patterns for Relation Acquisition from Texts with Caméléon[END_REF], Marshman's work [START_REF] Marshman | Lexical Knowledge Patterns for the Semi-automatic Extraction of Cause-effect and Association Relations from Medical Texts: A Comparative Analysis of English and French[END_REF] and TerminoWeb [START_REF] Barrière | TerminoWeb: a software environment for term study in rich contexts[END_REF], terms and context items can be either POS, lexical or semantic classes, empty words, information about their localization, etc. Simplifications omit term1 and term2, or A and C. In Expresso [START_REF] Pantel | Expresso: leveraging generic patterns for automatically harvesting semantic relations[END_REF], patterns conform to a similar shape: ENTRY/NP is/VBZ a/DT type/NN of/IN TARGET where ENTRY is term1 and TARGET is term2, NP is a noun phrase, DT a determiner, VBZ a verb and IN a preposition.

In these first two cases, all the items that form a pattern are of equal importance. They are searched in linear order. Anticipating the variation presented in section 2 requires to list all possible formulations and to define as many patterns as needed. An alternative solution gives more weight to the most significant parts of the pattern, key features that form its core, and less weight to secondary items. Stability is more likely to apply to the core, that is expected in every occurrence, whereas variation affects the secondary items, that are likely to be optional without affecting the relation meaning. Setting up secondary items has an operational influence on the pattern efficiency but it does not change its semantics. The next three structures illustrate this option.

Left term1 Middle term2

Right, where middle is considered as more important than Left and Right. Here, the system will first look for the searched terms or their semantic categories and then, it matches Middle to their context. In SnowBall [START_REF] Agichtein | Snowball: Extracting relations from large plain text collections[END_REF], patterns have the following shape:

(<left>, <LOCATION, Seattle>, <middle>, <ORGANIZATION, Boeing>, <right>)

Today's merger positions Seattle -based Boeing the largest aircraft manufacture

A similar structure is used for pattern definitions in [START_REF] Sierra | Definitional verbal patterns for semantic relation extraction[END_REF]: <Left Verb_Def Nexus Right>, where the verb (Verb_Def) and its potential modifier (Nexus) are considered as more important than the terms in relationship which appear inside right and left fragments.

IF Initial clues THEN R (IF Contextual clues THEN R(Arg1,Arg2)) :

Implemented in systems like Coatis [START_REF] Garcia | Analyse automatique des textes pour l'organisation causale des actions, Réalisation du système Coatis[END_REF] or ContextO [START_REF] Minel | Filtrage Sémantique : du résumé automatique à la fouille de textes[END_REF], contextual exploration goes one step further [START_REF] Desclés | Exploration contextuelle et sémantique : un système expert qui trouve les valeurs sémantiques des temps de l'indicatif dans un texte[END_REF]. Patterns are rules that are fired in two steps: firstly, initial clues (verbs or semantic classes) are searched in sentences and secondly, the contextual clues are searched only in results of the first step. Initial clues characterize the relation type and tend to be stable across domains or textual genre. Contextual clues are expected to be modified to adapt the rule to new corpora and improve its efficiency to identify related terms.

Pattern Matching

The facilities provided for pattern matching on text determine the quality of the phrases identified as clues of linguistic relations. One of the difficulties when adjusting patterns is to know how they will be matched to text.

Linear Matching: Each pattern component is searched in sequence and with equal importance. The majority of pattern-based tools sequentially browse the corpus to find out sentences or phrases that match pattern components. As a consequence, the first components of the pattern are searched more often, even if they do not contribute much to sentence discrimination. So linear matching performs slowly on very large corpora when patterns contain a lot of frequent and non discriminative categories (like prepositions or determiners). But the simplicity of this algorithm makes it quite intuitive for users. It is implemented in Caméléon and Prométhée to browse technical books, as well as in systems where patterns are made of lemma or verbs [START_REF] Sierra | Definitional verbal patterns for semantic relation extraction[END_REF], [START_REF] Soler | Patrones léxicos para la extracción de conceptos vinculados por la relación parte-todo en español[END_REF].

Search Restricted to Focused Sentences: One way to reduce the search space when matching patterns to text is to focus on contexts that are more likely to contain linguistic clues of relations. The selection of such contexts relies on other types of knowledge. For instance, RelExt selects sentences where paired terms that often are in collocation cooccur; then it tries to match patterns only with these sentences [START_REF] Schutz | RelExt: A tool for relation extraction from text in ontology extension[END_REF]. In some domains, a semantic or lexical resource can provide pairs of related terms. Patterns are expected to characterize the contexts in which pairs of terms occur in the same sentence. This process is suggested by Hearst to indentify domain specific patterns [START_REF] Morin | Patrons lexico-syntaxiques pour aider au dépouillement terminologique[END_REF]. New patterns can be learned from these contexts using a supervised learning algorithms [START_REF] Navigli | A Graph-based Algorithm for Inducing Lexical Taxonomies from Scratch[END_REF] or [START_REF] Ruiz-Casado | Automatising the learning of lexical patterns: An application to the enrichment of Wordnet by extracting semantic relationships from Wikipedia[END_REF] or they can be hand-crafted reading the contexts [START_REF] Hearst | Automatic Acquisition of Hyponyms from Large Text Corpora[END_REF].

Focused Search using Priority Pattern Components: Some search strategies may give a higher priority to pattern components that play a more important role in relation interpretation. When explicitly mentioned, the verb is often considered as one of the strongest contributors to the relation meaning. Matching <Left Verbe-Def Nexus Right> patterns starts by searching the verb Verbe-Dedf; Nexus is used to reject non valid contexts, then Left and Right are tested with regular expressions to look for the related terms. In [START_REF] Agichtein | Snowball: Extracting relations from large plain text collections[END_REF] patterns are matched according to a similar rule: priority is given to the middle component, which is expected to convey the relation meaning. In contextual exploration rules [START_REF] Desclés | Exploration contextuelle et sémantique : un système expert qui trouve les valeurs sémantiques des temps de l'indicatif dans un texte[END_REF], the focus is determined by the initial clues. Then contextual clues are searched to identify additional linguistic features that express the terms in relationship [START_REF] Minel | Filtrage Sémantique : du résumé automatique à la fouille de textes[END_REF]. This process accelerates text browsing and identifies complex formulations of relations or variants in these formulations.

Limitations of pattern-based relation extraction

Many pattern matching implementations do not account for all linguistic phenomena that may arise in language, in particular variation [START_REF] Blohm | Using the Web to Reduce Data Sparseness in Pattern-Based Information Extraction[END_REF]. For instance, the efficiency of patterns is measured with criteria such as precision (ability to identify valid sentences expressing a semantic relation) and recall (ability to find out all the occurrences of a pattern in the corpus). When trying to improve recall and precision to gain efficiency, patterns become more specific and numerous: each of them accounts for a way of expressing a relation. Such patterns share the same core linguistic clues. The paradox here is that patterns are supposed to be generic and to abstract linguistic phenomena at a higher level. Quantitative evaluations influence what is considered as a good pattern: it is a productive pattern, not one that best accounts for all the linguistic formulations of a relation. For instance, in some systems, learned patterns must have either at least 3 occurrences in the studied corpus or their recall must be higher than a given threshold. Language analysis is secondary while finding pattern utterances is the priority.

Two alternatives to "hard pattern" that manage flexibility

Learning approaches can improve relation extraction. We report here two alternatives to patterns that reduce some of the above-mentioned limitations.

Soft patterns:

The notion of soft pattern contributes to better handle the generality of patterns in real-world corpora like the Web [START_REF] Navigli | A Graph-based Algorithm for Inducing Lexical Taxonomies from Scratch[END_REF]. In GlossExtractor [START_REF] Velardi | Evaluation of Ontolearn, a methodology for automatic learning of domain ontologies[END_REF], candidates are pruned using more refined stylistic patterns and lexical filters to improve precision while keeping pattern generality. Soft patterns refine this idea thanks to probabilistic lexico-semantic patterns "that allow a partial matching" [START_REF] Girju | Automatic Discover of Part-Whole Relations[END_REF]. Instead of a Boolean result, the system calculates a degree of match probability. Soft matching may be carried out in two ways, using either an n-gram language model (Expectation Maximization algorithm), or Profile Hidden Markov Models.

Concept lattices:

Learned concept lattices can be an alternative to patterns: links represent hierarchical relations between words, and nodes are clusters of salient words aggregated using synonymy, similarity, or sub-trees of a thesaurus [START_REF] Carpineto | Using concept lattices for text retrieval and mining[END_REF]. However, some problems remain, like word selection and aggregation, or word sense disambiguation. The methodology proposed in [START_REF] Carpineto | Using concept lattices for text retrieval and mining[END_REF] aligns patterns using of wildcard (*) characters to facilitate sentence clustering. Each cluster of sentences is then generalized to a lattice of word classes. This approach is able to both identify definitions and extract hypernyms. These patterns generalize over lexico-syntactic patterns, and outperform them.

Conclusion

Pattern-based relation extraction is one of the most popular ways to identify semantic relations. Although patterns abstract some linguistic regularity, we identified three types of variation phenomena that influence patterns and their interpretations. We analysed this variation situation to illustrate how it turns relation identification and interpretation into a more complex and subtle task.

Confronting the pattern definitions with these variations questions the nature of patterns and even their relevance as a search structure. We raise the question of an alternative to patterns that could better account for variability in semantic relation identification and "understanding". Pattern-based relation extraction systems have more or less ability to anticipate linguistic and semantic variations. Flexible and adaptable relation definition is desirable to adapt to specific domains. The quality and precision of pattern matching depend on (i) the text pre-processing that is required, (ii) what is searched with the help of a pattern: just a context or a precise triple with a relation label and related terms, or labeled conceptual relations, (iii) the ability to evaluate a confidence degree of each proposed relation.

In short, the most frequent limitations identified for pattern-based approaches are the following: one of the related terms is missing; the pattern is not powerful enough to match with complex variations; there is confusion between arguments in the sentence and concepts in the triple; the estimated POS of some words are wrong; pattern search gives a similar weight to each word in the pattern; patterns are rigid and not adaptable. Relation finding is more efficient and linguistic variation phenomena is better when more complex linguistic variants can be matched to the pattern, and when patterns and target relations can be adapted to the corpus and domain.

From these observations, we stand up for the necessity for linguistics studies in prior to design tools and to integrate human interpretation when representing semantic relations from texts. In terms of research the main questions are: how to design tools that carry out a better linguistic analysis? How to integrate interpretation within the analysis process? How to facilitate the design of ad-hoc patterns? More cross-disciplinary studies (involving corpus linguistic and knowledge engineering) have to be carried out, to identify additional fine-grained linguistic indices for each type of relation. We also expect relation extraction systems to support relation modelling rather than automate it, so that the modelling goal could influence relation interpretation.

3 Pattern-based Relation Extraction Software 3 . 1

 331 Automating the Search for Semantic Relations

  below presents the results of the study.

		GER GEO T.C	P.A	ITI
	Avec	667 432	236	185	114
	Meronymic avec 3% 12.7% 68.2% 76,2% 64,6%

Table1: Quantitative Results for avec

http://gate.ac.uk

http://www.linguastream.org/

http://www-lipn.univ-paris13.fr/~hamon/PlateformeTAL-ALVIS/index.html

http://uima.apache.org/


Jing-Rebecca Li
email: jingrebecca.li@inria.fr

Donna Calhoun

Cyril Poupon

Denis Le Bihan

Numerical simulation of diffusion MRI signals using an adaptive time-stepping method

The effect on the MRI signal of water diffusion in biological tissues in the presence of applied magnetic field gradient pulses can be modeled by a multiple compartment Bloch-Torrey partial differential equation. We present a method for the numerical solution of this equation by coupling a standard Cartesian spatial discretization with an adaptive time discretization. The time discretization is done using the explicit Runge-Kutta-Chebyshev method, which is more efficient than the Forward Euler time discretization for diffusive-type problems.

We use this approach to simulate the diffusion MRI signal from the extracylindrical compartment in a tissue model of the brain gray matter consisting of cylindrical and spherical cells and illustrate the effect of cell membrane permeability.

Introduction

Biological tissue is a heterogeneous medium, consisting of cells of various sizes and shapes distributed in the extra-cellular space. The cells are separated from each other and from the extra-cellular compartment by the cell membranes. Diffusion magnetic resonance imaging (dMRI) is an imaging modality that subjects the tissue to various magnetic field gradients and gives a measure of the average displacement of water molecules over a time period on the order of tens of milliseconds.

If the water exchange time between the cells and the extra-cellular space is long compared to the measured diffusion time, then the cell membranes can be approximated as impermeable to water passage. In this case, various analytical and semi-analytical expressions have been obtained for the dMRI signal arising from inside the cells [START_REF] Crank | The mathematics of diffusion second edn[END_REF][START_REF] Callaghan | A simple matrix formalism for spin echo analysis of restricted diffusion under generalized gradient waveforms[END_REF][START_REF] Pfeuffer | Restricted diffusion and exchange of intracellular water: theoretical modelling and diffusion time dependence of 1H NMR measurements on perfused glial cells[END_REF][START_REF] Sukstanskii | Effects of restricted diffusion on MR signal formation[END_REF]. To generalize these results to the complex cellular geometries of biological tissues, geometrical models of the tissue as spherical and oriented cylindrical cells embedded in extra-cellular space were proposed for the brain white matter [START_REF] Assaf | Composite hindered and restricted model of diffusion (CHARMED) MR imaging of the human brain[END_REF][START_REF] Sen | A model for diffusion in white matter in the brain[END_REF] and gray matter [START_REF] Jespersen | Modeling dendrite density from magnetic resonance diffusion measurements[END_REF]. The dMRI signal is then decomposed as the sum of the signals from two different tissue compartments: with the signal from the cylindrical cells being an analytical expression, and the signal from the spherical cells plus the extra-cellular space being Gaussian with an effective diffusion tensor.

If the cell membranes are permeable, but not so permeable so that the whole tissue can be treated as one compartment, the analysis of the dMRI signal becomes more difficult. If the cells are assumed to be of a special shape: spheres, cubes, or cylinders, and placed on a periodic lattice, then various approximate analytical formulae have been obtained in the long diffusion time limit [START_REF] Latour | Time-dependent diffusion of water in a biological model system[END_REF][START_REF] Hasselman | Effective thermal conductivity of composites with interfacial thermal barrier resistance[END_REF][START_REF] Torquato | Effect of the interface on the properties of composite media[END_REF]. In [START_REF] Latour | Time-dependent diffusion of water in a biological model system[END_REF][START_REF] Szafer | Theoretical model for water diffusion in tissues[END_REF] approximate analytical formulae for the effective long time diffusion coefficient were applied to the dMRI signal.

Because the analytical results and models of the dMRI signal cited above are subject to certain assumptions such as long diffusion times, it is important to test the various assumptions against a richer numerical model of the dMRI signal that makes less stringent assumptions, as a bridge between analytical models and experimental conditions. Simulation using such numerical models can give new insights that may lead to more accurate analytical models of tissue water diffusion in the future, for use in the estimation of tissue parameters from the experimental signal.

In this paper, we focus on the multiple compartment Bloch-Torrey partial differential equation (PDE), which is a generalization of the Bloch-Torrey PDE [START_REF] Torrey | Bloch equations with diffusion terms[END_REF]) to heterogeneous diffusion spatial domains. This PDE models the water proton magnetization subject to diffusion-encoding magnetic field gradient pulses and the dMRI signal is given as the integral of the solution of the PDE at echo time. The numerical solution of the multiple compartment Bloch-Torrey has been considered in the past [START_REF] Hwang | An image-based finite difference model for simulating restricted diffusion[END_REF][START_REF] Xu | Numerical study of water diffusion in biological tissues using an improved finite difference method[END_REF][START_REF] Harkins | Assessment of the effects of cellular tissue properties on ADC measurements by numerical simulation of water diffusion[END_REF][START_REF] Russell | A finite difference method with periodic boundary conditions for simulations of diffusion-weighted magnetic resonance experiments in tissue[END_REF]. The main difference between our approach and those in the previous works is that we use an efficient adaptive time-stepping method, called the Runge-Kutta Chebyshev (RKC) method [START_REF] Sommeijer | RKC: An explicit solver for parabolic PDEs[END_REF], that takes time steps commensurate with the desired accuracy of the time integration at any given point in the simulation. In the case of moderate desired accuracy, we show that this approach is preferred to the explicit Forward Euler method used previously in [START_REF] Hwang | An image-based finite difference model for simulating restricted diffusion[END_REF][START_REF] Xu | Numerical study of water diffusion in biological tissues using an improved finite difference method[END_REF][START_REF] Harkins | Assessment of the effects of cellular tissue properties on ADC measurements by numerical simulation of water diffusion[END_REF][START_REF] Russell | A finite difference method with periodic boundary conditions for simulations of diffusion-weighted magnetic resonance experiments in tissue[END_REF] where the time step size is limited by numerical stability.

Finally, we use this numerical method to study a particular model of the dMRI signal in the brain gray matter given in [START_REF] Jespersen | Modeling dendrite density from magnetic resonance diffusion measurements[END_REF], where the neurites are modeled by cylinders. In particular, we examine two assumptions of this model. The first is that the extra-cylindrical compartment, which includes the extra-cellular space and non-cylindrical cells such as glial cells (that we model by spheres), can be considered to undergo Gaussian diffusion. The second is that the signal contribution from the cylinders can be considered to be in 'no-exchange' with the signal contribution from the extra-cylindrical compartment. We study the validity of these assumptions by simulating the dMRI signal at different diffusion times and varying the cell membrane permeabilities.

Theory

We model the effect on the MRI signal of the water proton magnetization in a biological tissue in the presence of magnetic field gradient pulses by a multiple compartment Bloch-Torrey partial differential equation [START_REF] Torrey | Bloch equations with diffusion terms[END_REF][START_REF] Price | A model for diffusive transport through a spherical interface probed by pulsed-field gradient NMR[END_REF]). In the most general case, each compartment corresponds to an individual cell, with an additional compartment being the extra-cellular space (which can be contiguous or not). We can also group all cells of a certain type into a single compartment. We denote the compartments by Ω l , l = 1, 2, 3, • • • , and their associated intrinsic diffusion coefficients by D l . If all the compartmental intrinsic diffusion coefficients are equal, then we will refer unambiguously to the intrinsic diffusion coefficient, and denote it with a superscript 0, as D 0 , where

D 0 = D l , l = 1, 2, • • •
The union of the compartments l=1 Ω l comprises the tissue. Supposing the diffusion-encoding sequence with the time profile f (t), and the diffusion gradient vector g containing amplitude and direction information of the linear magnetic field gradient, we use the Bloch Torrey PDE model in each compartment: for r ∈ Ω l , we have

∂M l (r, t|g) ∂t = -If (t)(γg • r) M l (r, t|g) + ∇ • (D l ∇M l (r, t|g)) - M l (r, t|g) (T 2 ) l , ( 1
)
where γ is the gyromagnetic ratio of the water proton, I is the imaginary unit, and (T 2 ) l gives the T 2 relaxation in Ω l . The magnetization in the entire sample is defined piecewise by the M l 's. The PDE in (1) needs to be supplemented by interface conditions where Ω l and Ω n come in contact. We denote the interface between Ω l and Ω n by Γ ln . One interface condition is the continuity of flux:

D l ∇M l (a, t|g) • n l (a) = -D n (∇M n (a, t|g) • n n (a)) , a ∈ Γ ln , (2)
where n l (a) and n n (a) are the outward-point normals to Ω l and Ω n at a, so in fact n l (a) = -n n (a). This ensures the conservation of magnetization. The second interface condition is:

D l ∇M l (a, t|g) • n l (a) = κ ln M l (a, t|g) -M n (a, t|g) , a ∈ Γ ln .(3)
This incorporates a permeability coefficient κ ln across Γ ln which models the ease with which water crosses the interface. The larger the κ ln , the easier the passage of water.

For a Pulsed-Gradient Spin Echo (PGSE) [START_REF] Stejskal | Spin diffusion measurements: Spin echoes in the presence of a time-dependent field gradient[END_REF] sequence, made of two rectangular pulses (duration δ, separated by a time interval ∆ -δ) the profile f (t) is:

f (t) =      1, t 1 ≤ t ≤ t 1 + δ, -1, t 1 + ∆ < t ≤ t 1 + ∆ + δ, 0, elsewhere, (4)
where t 1 is the start of the first pulse with t 1 + ∆ > T E/2, TE is the echo time when the signal is measured.

The PDE and interface conditions in (1,2,3) must be supplemented with an initial condition:

M (r, 0|g) = ρ l , r ∈ Ω l , for l = 1, 2, • • • , (5)
where ρ l is the water density in Ω l . The total signal attenuation is:

S(g, t) := l r∈Ω l M l (r, t|g) dr l ρ l V l , ( 6
)
where V l is the volume of Ω l . In the case of a compartment Ω l that does not exchange water with the domain outside of Ω l , if we want to study the contribution to the dMRI signal from this compartment, we define the partial signal attenuation due to Ω l :

S l (g, t) := r∈Ω l M l (r, t|g) dr ρ l V l , (7)
which will be useful to study the contribution to the total signal from the different physical compartments. The dMRI signal is measured at echo time t = T E ≥ ∆ + δ.

In a homogeneous medium, the signal attenuation is e -D 0 b , where D 0 is the intrinsic diffusion coefficient, and the b-value is a weighting factor that combines the effects of the imaging and diffusion gradients (Le [START_REF] Bihan | MR imaging of intravoxel incoherent motions: application to diffusion and perfusion in neurologic disorders[END_REF]) and which is:

b(g, δ, ∆) = γ 2 g 2 δ 2 (∆ -δ/3) (8)
for the PGSE sequence [START_REF] Stejskal | Spin diffusion measurements: Spin echoes in the presence of a time-dependent field gradient[END_REF]. In biological tissue, the signal attenuation is not a simple decaying exponential in b and the slope of log S(b) at b = 0 is not simply related to the intrinsic diffusion coefficients of the physical compartments. Theoretical analysis of the signal attenuation as a function of the b-value is difficult for general gradient pulses and is usually done only in the narrow pulse limit. Let u(r, t, |r 0 ) be the probability of finding water molecules originally at r 0 (t = 0) in position r at time t, then the signal in the narrow pulse (NP) limit is:

S N P ( g δγ, ∆) = r0∈R 3 r∈R 3 e -I g δγ(r-r0)•ug u(r, ∆, |r 0 )dr dr 0 ,( 9
)
where u g := g/ g is the normalized gradient direction. We chose the independent variable in S N P to be g δγ because the interior integral over r in ( 9) is just a one dimensional Fourier transform, with the Fourier variable being g δγ and the spatial variable being (r-r 0 )•u g , leading us to the property relating derivatives of the Fourier transform and the moments of the original function:

I 2n d 2n S N P d ( g δγ) 2n ( g δγ, ∆) = r0∈R 3 r∈R 3 e -Igδγ(r-r0) ((r -r 0 ) • u g ) 2n u(r, ∆|r 0 )dr dr 0 .
In a dMRI experiment, the pulse sequence profile f (t) is most often fixed while g is varied in amplitude, so we can treat ∆ as a constant and use the new independent variable b = γ 2 g 2 δ 2 ∆ to obtain for S N P (b):

d n S N P d b n (0, ∆) = (-1) n n! (2n)! 1 ∆ n r0∈R 3 r∈R 3 ((r -r 0 ) • u g ) 2n u(r, ∆|r 0 )dr dr 0 . ( 10
)
Thus in the narrow pulse limit, the analytical derivatives of S give the moments of the probability density function u(r, t, |r 0 ), averaged over all starting positions r 0 . For general pulse sequences, ( 10) is not exact. The first and second analytical derivatives of S can be related to the Apparent Diffusion Coefficient and the Apparent Kurtosis [START_REF] Chabert | Diffusion tensor imaging of the human optic nerve using a non-CPMG fast spin echo sequence[END_REF][START_REF] Jensen | Diffusional kurtosis imaging: The quantification of non-Gaussian water diffusion by means of magnetic resonance imaging[END_REF][START_REF] Frohlich | Effect of impermeable boundaries on diffusionattenuated {MR} signal[END_REF]) computed in dMRI:

ADC 0 = - d log S db (0) = - dS db (0), (11)
AK 0 = 3 d 2 log S db 2 (0) d log S db (0) -2 = 3 d 2 S db 2 (0) dS db (0) -2 -3, ( 12
)
where we denoted the quantities by ADC 0 and AK 0 , respectively, to emphasize that the analytical derivatives of log S(b) are taken at b = 0. The ADC 0 and the AK 0 are interesting because the ADC 0 gives an indication of the mean squared distance traveled by water molecules, averaged over all the compartments, and AK 0 gives an indication of the deviation from Gaussian diffusion. We computed ADC 0 and AK 0 by fitting log S(b) at a set of b by polynomials in a least squares sense. We start with a polynomial of degree 1 (where the second derivative is set to 0) and increase the polynomial degree until the ADC 0 of the polynomial fit of degree n and the ADC 0 the fit of degree n + 1 are within 1 percent (relative error) of each other and for AK 0 we allow 5 percent relative error.

Method

Our approach solves the multiple compartment Bloch-Torrey PDE in three dimensions by coupling a standard Cartesian spatial discretization that allows permeable membranes to the Runge-Kutta-Chebyshev (RKC) method [START_REF] Sommeijer | RKC: An explicit solver for parabolic PDEs[END_REF]), which is an adaptive time-stepping method that enforces a user-specified time integration error tolerance at each spatial discretization point.

Cartesian spatial discretization

In the spatial discretization, we use a rectangular computational domain

C = [0, L] × [0, L] × [0, L]
that contains a configuration of cells and a Cartesian discretization of C.

We use the same transformation on the Bloch-Torrey PDE as [START_REF] Russell | A finite difference method with periodic boundary conditions for simulations of diffusion-weighted magnetic resonance experiments in tissue[END_REF], where a change of variable is made so that the unknown function to be solved becomes

m(r, t|g) := M (r, t|g)e Iγg•r R t 0 f (s)ds . ( 13
)
We include here the interface condition at the intersection of two different compartments because this was not explicitly described in [START_REF] Russell | A finite difference method with periodic boundary conditions for simulations of diffusion-weighted magnetic resonance experiments in tissue[END_REF]. We denote by {x 1 ,

• • • x W } and {y 1 , • • • , y W } and {z 1 , • • • , z W } the
discretization points in the x, y, z coordinates, respectively:

x i = ih -h/2, y j = jh -h/2, z k = kh -h/2,
where the h is the side length of one discretization element. The diffusion coefficient at r ijk ≡ (x i , y j , z k ) will be denoted by D ijk . We define g := (g x , g y , g z ) and

A := (A x , A y , A z ) := (g x , g y , g z )γ t 0 f (s)ds.
The discretization formula for m is:

∂m ijk (t) ∂t = - m ijk (t) (T 2 ) ijk + 1 h 2 D * i+ 1 2 ,jk e -IAxh m i+1,j,k (t) -m ijk (t) -D * i-1 2 ,jk m ijk (t) -e IAxh m i-1,j,k (t) + D * i,j+ 1 2 ,k e -IAyh m i,j+1,k (t) -m ijk (t) -D * i,j-1 2 ,k m ijk (t) -e IAyh m i,j-1,k (t) + D * ij,k+ 1 2 e -IAzh m ij,k+1 (t) -m ijk (t) -D * ij,k-1 2 m ijk (t) -e IAzh m ij,k-1 (t) . (14) If the diffusion coefficient is continuous in x at x i+ 1 2 , y j , z k , then D * i+ 1 2 ,jk = D ijk . Otherwise, D * is given by D * i+ 1 2 ,jk = 1 1 2 1 D(xi+1) + 1 D(xi) + 1 κ i,i+1 h . ( 15
)
Similarly in the other coordinate directions. Same as [START_REF] Xu | Numerical study of water diffusion in biological tissues using an improved finite difference method[END_REF][START_REF] Russell | A finite difference method with periodic boundary conditions for simulations of diffusion-weighted magnetic resonance experiments in tissue[END_REF], we assume the computational domain C is extended by periodic copies of itself to handle the diffusion of water molecules close to the boundary of C. The boundary conditions on m are periodic on the faces of C, as was shown in [START_REF] Russell | A finite difference method with periodic boundary conditions for simulations of diffusion-weighted magnetic resonance experiments in tissue[END_REF]. The spatial discretization in ( 14) gives rise to a system of ODEs in time which we will solve by a time stepping method described in the next section.

RKC time stepping method

We solve the system of ODEs in ( 14) using the Runge-Kutta-Chebyshev (RKC) method [START_REF] Sommeijer | RKC: An explicit solver for parabolic PDEs[END_REF]. We briefly describe this method as it applies to the solution of

d{m ijk (t)} dt = F (t, {m ijk (t)}),
where F is the discrete Laplacian plus the T 2 decay term defined in the right hand side of ( 14). The details of the RKC method can be found in the paper referenced above. To go from

{m ijk } n ≈ {m ijk (t n )} to {m ijk } n+1 ≈ {m ijk (t n+1
)}, the following s stages are taken:

Y 0 = {m ijk } n , Y 1 = Y 0 + µ 1 τ F (t n , {m ijk } n ), Y j = µ j Y j-1 + ν j Y j-2 + (1 -µ j -ν j )Y 0 + μ τ F (t n + c j-1 τ, Y j-1 ) + γ τ F (t n , Y 0 ), 2 ≤ j ≤ s, {m ijk } n+1 = Y s ,
where τ = (t n+1 -t n ) and the coefficients are determined by Chebyshev polynomials.

The two important things to note about the RKC method are that the local time error at t n+1 can be estimated as:

err n+1 = 1 15 12({m ijk } n -{m ijk } n+1 ) + 6τ F (t n , {m ijk } n ) + F (t n+1 , {m ijk } n+1 ) ,
and that the time step can be made stable no matter how large it is by increasing the number of stages s. Specifically, the stability criterion is [START_REF] Sommeijer | RKC: An explicit solver for parabolic PDEs[END_REF]):

(t n+1 -t n ) RKC ≤ ∆t max RKC := 0.653s 2 max eig(jac F (t, {m ijk }(t))) ≈ 0.653 s 2 h 2 6D 0 . ( 16
)
Essentially, the RKC method chooses a t n+1 where the error term above is smaller than the user-specified tolerance and the number of stages s is increased so that t n+1 -t n is a stable step. Because the time step can be enlarged as O(s 2 ) whereas the computational time only increases as O(s), this means that the RKC method with larger time steps computes the solution faster than taking many smaller steps of the Forward Euler method. The number of stages s is typically between 30-50 in the simulations we have performed. In addition, because of the existence of a threeterm recurrence relation for Chebyshev polynomials. the storage requirement does not increase with s, it stays constant at 5 times the number of unknowns.

In contrast, for the Forward Euler method, the stability criterion for a spatial discretization h is

t n+1 -t n F E ≤ ∆t max F E := h 2 6D 0 . ( 17
)
For moderate accuracy requirements, it is usually much more efficient to increase s according to (16) to get a time step that is appropriate for the desired accuracy than being limited by the stability condition of (17). Because it is difficult to judge the computational time which depends on the computer on which the simulation was performed, we define a quantity called the computational efficiency of the RKC method over the Forward Euler method, E RKC (t n ) at the RKC time point t n , in the following way:

E RKC (t n ) = (t n+1 -t n )/P RKC (t n , t n+1 ) ∆t max F E , (18)
where P RKC (t n , t n+1 ) is the number of Laplacian evaluations in advancing from t n to the next t n+1 using the RKC method. The maximum time step of the Forward Euler method ∆t max F E is given in ( 17). The number of Laplacian evaluations in advancing from t to t+∆t using the Forward Euler method is 1. The quantity E RKC (t n ) measures how much faster the RKC method runs compared to the Forward Euler method on the interval [t n , t n+1 ].

Numerical results and discussion

We implemented the above method as a Fortran90 program. The implementation of the RKC method comes from the publicly available Fortran code downloaded from http://www.netlib.org/ode/rkc.f. Our simulations were performed on a Dell network server (Intel Xeon E5-2667 processor 2.90GHz), running the program as a serial code.

A dMRI signal model for brain gray matter

In the brain gray matter, neurons, consisting of a large neuronal body and long extensions (axons and dendrites), are densely packed. There are also glial cells which do not have these long extensions. The extra-cellular space accounts for only a small fraction of the total volume. In [START_REF] Jespersen | Modeling dendrite density from magnetic resonance diffusion measurements[END_REF]), a simplified model of the dMRI signal was proposed:

S(b) = (1 -v c ) e -D ec b + v c S c (b), ( 19
)
where v c is the volume fraction of all the diffusion compartments exhibiting cylindrical symmetry and everything outside of these cylindrical compartments is assumed to undergo Gaussian diffusion with an effective diffusion coefficient D ec , where the superscript "ec" stands for extra-cylindrical. The term S c (b) is the signal due to the cylindrical compartments under the assumption that they are impermeable with respect to the extra-cylindrical compartment. In the gray matter, where there is no a-priori orientation preference for the neurites (axons and dendrites), the cylindrical compartments consist of the neurites themselves. We are interested in simulating the dMRI signal from regions of the brain where the neurites can be thought of as oriented more or less randomly.

DMRI signal from the extra-cylindrical compartment

First we study the dMRI signal from the compartment consisting of the extracellular space and the spherical cells. We begin by constructing a geometry consisting of generally oriented cylinders and spheres. In the computational box C = [-12.5µm, 12.5µm] 3 , we placed N c = 250 randomly-placed points (uniformly distributed in C). At each point, we extended an infinite cylinder of radius R c oriented in a random direction (drawn uniformly from the unit sphere) and cut the cylinder off at the boundaries of C. The size of C is chosen for the simulation of the extracylindrical space, where we observed that the effective diffusion coefficient was no more than 10 -3 mm 2 /s, meaning a diffusion distance of 15µm in 40ms. This size ensures that most molecules see C no more than twice during 40ms. The cylindrical volume fraction will be denoted v c . We also distribute N s = 10 randomly-placed spheres of radius R s in C and denote the spherical cells volume fraction by v s . The volume fraction of the extra-cellular space will be denoted v e = 1 -v c -v s . See At the start of the simulation, we placed water molecules uniformly in the spherical cells and the extra-cellular space and placed no water molecules inside the cylinders.

We made the cylindrical cells impermeable so that the water molecules are blocked from entering the cylinders during the simulation.

We varied the spherical cell permeability: κ s = 0m/s(impermeable), 10 -5 m/s, 10 -4 m/s, ∞(infinitely permeable), and we computed the ADC 0 and AK 0 from b-values: 0, 250, 500, 750, 1000, 1250, 1500, 1750, 2000s/mm 2 . The RKC tolerance was set to tol = 10 -4 , after doing a preliminary simulation for free diffusion where we saw that the relative signal error was less than 0.005 at b = 2000s/mm 2 , which is sufficiently accurate for the dMRI application where there is significant experimental noise in the measured signal.

We chose a constant intrinsic diffusion coefficient D 0 = 3 × 10 -3 mm 2 /s in the cells and the extra-cellular space and neglected the T 2 relaxation term. The diffusion-encoding gradient sequence simulated was PGSE, δ = 2.5ms and we varied ∆ = 10ms, 20ms, 30ms, 40ms. We simulated the dMRI signal on two meshes with h = 0.25µm and h = 0.125µm.

We examine the results for the mesh with h = 0.125µm (marked by stars). In Fig. 2, we see that at κ s = 0m/s (solid line) and κ s = 10 -5 m/s (dash-dots), the ADC 0 decreases from 0.4 × 10 -3 mm 2 /s to 0.2 × 10 -3 mm 2 /s as the diffusion time is increased from 10ms to 40ms, while the AK 0 goes from 1.8 to 2.7 for κ s = 10 -5 m/s and from 2 to 3.5 for κ s = 0m/s. At κ s = 10 -4 m/s (dashes), the ADC 0 decreases from 0.55 × 10 -3 mm 2 /s to 0.45 × 10 -3 mm 2 /s, while the AK 0 stays around 1.2. At κ s = ∞m/s (dots), the ADC 0 decreases from 1.05×10 -3 mm 2 /s to 0.85×10 -3 mm 2 /s, while the AK 0 stays around 0.6. Thus we see that the AK 0 is quite high between 10ms and 40ms for the different values of the spherical cells permeability. Because the AK 0 is so high at finite permeability, this set of simulations put to question the assumption that the extra-cellular space and the spherical cells can be considered as one physical compartment experiencing Gaussian diffusion at the above diffusion times when the b-values are as high as 2000s/mm 2 .

From the same Figure, we also see that when we use a coarser mesh with h = 0.25µm (marked by circles), the values of ADC 0 and AK 0 are slightly shifted, with the ADC 0 being lower at the coarser discretization, which is easily explained by the cylinders having more 'jagged' surfaces. However, the behavior of the ADC 0 and AK 0 as a function of κ s and diffusion time is consistent with the results from the finer mesh. To study the effect of R c and R s on the dMRI signal, we set κ s = 0 and computed the ADC 0 and AK 0 in the extra-cellular and the spherical compartments separately. Making κ s = 0 means we do not have to account for the exchange between them and can focus on the shape of the compartments. We fixed the positions of the cylinders and spheres as the previous example and simulated three cases: We see that it is the extra-cellular space that dominates the ADC 0 of the combined compartment in the range of diffusion times 10 -40ms. When the spheres are larger, even though the diffusion inside of the spheres is more significant, it does not compensate for the decreased diffusion in the extra-cellular space. Thus, to study the cell features beyond the extra-cellular space, one must look beyond the ADC 0 and to information contained in the higher b-values.

(i) R c = 1µm, R s = 4µm, v e = 0.28, v s = 0.15 (circles in Fig 3), (ii) R c = 1µm, R s = 5µm, v e = 0.25, v s = 0.25 (crosses in Fig 3), (iii) R c = 1.25µm, R s = 4µm, v e = 0.

Performance of the numerical method

We show the efficiency of the RKC time-stepping method over the Forward Euler method for the example shown in Fig. 2 for the PGSE sequence, δ = 5ms, ∆ = 40ms, at b = 1000s/mm 2 , using the two spatial meshes: h = 0.25µm and h = 0.125µm. The efficiency at a RKC time step [t n , t n+1 ] is defined as the ratio of the number of Laplacian evaluations needed by the RKC method to advance the solution from t n to t n+1 to the number of Laplacian evaluations required by the Forward Euler method to advance from t n to t n+1 . We see in Fig 4(a) that during the time the gradient is turned off: 2.5ms ≤ t ≤ 40ms, the efficiency of the RKC method varies from 1 to 90, meaning, as a rough estimate, the RKC method is about 45 times faster than the Forward Euler method during the full simulation. When h = 0.125µm, efficiency of the RKC method varies from 1 to 40, meaning a rough estimate that RKC is 20 times faster than the Forward Euler method during the full simulation. The reason for the difference is that on a coarse spatial mesh, the solution error cannot be reduced by time refinement. In this case, RKC takes very large time steps, with a large number of stages. When h is smaller, then the time discretization error can be made lower by making the time steps smaller. In this case, RKC takes small time steps. Reassuringly, we see that RKC takes small steps when the gradient suddenly changes value: at t = 0, 2.5ms and t = 40ms, because the time refinement is needed there. Thus, we see that in general the RKC method is much faster than the Forward Euler method for diffusion problems where the time accuracy requirement is much less restrictive than the numerical stability requirement for Forward Euler. Also, the RKC time steps are completely adapted to the problem to be solved, refining where the gradient suddenly changes. The computational time on the mesh h = 0.25µm (100 3 unknowns) is around 2 minutes per b-value and it is 30 minutes per b-value on the mesh h = 0.125µm (200 3 unknowns) on a Dell network server (Intel Xeon E5-2667 processor 2.90GHz), while running the program as a serial code.

To simulate the total tissue with cylindrical cells in water exchange with the the extra-cylindrical compartment, it would be indispensable to create a geometry of densely packed thin cylinders, where the cylinders do not cross each other. We were not able to define such a geometry because straight cylinders cross each other × 100 for "xy-dir" cylinders at ∆ = 10 ms. The line connecting the four data points is the linear fit of the logarithm of h to the logarithm of the ADC 0 error. at many places if there are a lot of them in a small volume. This problem of defining non-crossing cylinders was not important in the previous section where we simulated the diffusion in the extra-cylindrical compartment because we only needed the space outside of the cylinders. However, this problem prevents us from simulating the complete problem of diffusion in a tissue model containing densely packed, randomly oriented, permeable cylindrical cells.

Instead, here we simply study the discretization errors associated with the 'jagged surface' of a slanted cylinder due to a Cartesian mesh when simulating diffusion inside this cylinder. This may be useful in the future when the problem of non-crossing cylinders placement has been solved and the simulation of the full tissue model can be done. For a thin straight impermeable cylinder oriented along the direction o, the dMRI signal due to water diffusion inside the cylinder is approximately e -(D 0 cos 2 α)b , where cos α = g•o/ ( g o ), making the theoretical ADC cyl 0 = D 0 cos 2 α, AK cyl 0 = 0. We simulated the PGSE sequence: δ = 2.5ms, ∆ = 10ms. The intrinsic diffusion coefficient was set to D 0 = 3 × 10 -3 mm 2 /s inside the impermeable cylinder. First we placed a straight cylinder of length 50µm and radius R c = 1µm oriented parallel to the x-axis (o = [1, 0, 0]) and set the gradient direction to be 45 degrees from the x-axis:

g/ g = [1, 1, 0]/ √ 2,

Effects of cylindrical cells permeability

If all the cylinders are thin and straight with their orientations uniformly distributed in a sphere, and are impermeable (as supposed in the model of [START_REF] Jespersen | Modeling dendrite density from magnetic resonance diffusion measurements[END_REF])), then it is easy to show that:

S c (b) ≈ π φ=0 2π θ=0 e -D 0 cos φ 2 b sin φdθdφ 4π , log S c (b) = - D 0 3 b + 2 45 (D 0 ) 2 b 2 , ADC cyl 0 = D 0 3 , AK cyl 0 = 12 5 .
Now, we use an indirect calculation to show that if the cylindrical cells are permeable and the permeable signal is fitted to the no-exchange model of ( 19), then a first order effect on v c is that v c would be under-estimated, a simulation result that supports the finding of [START_REF] Jespersen | Neurite density from magnetic resonance diffusion measurements at ultrahigh field: Comparison with light microscopy and electron microscopy[END_REF], in the case where the cylinders model dendrites (which are permeable to water). We do this indirectly because of we were not able to do a direct simulation of densely packed randomly oriented non-crossing cylinders embedded in the extra-cellular space, due to the difficult of defining the positions of the non-crossing cylinders, as explained previously. We suppose that, in the absence of cylindrical cell permeability, the signal is given by ( 19). We note here that, of course, we have shown in the previous section that the Gaussian diffusion assumption in the extra-cylindrical compartment may not be accurate, but in this section we will just assume the Gaussian diffusion because we want to isolate the effect of the no-exchange assumption.

At relatively low b-values, we can use the following simple approximation of S c (b):

S c (b) = e -ADC cyl 0 b+ 1 6 (ADC cyl 0 ) 2 AK cyl 0 b 2 . ( 20
)
We use (20) rather than the more complicated analytical representation in [START_REF] Jespersen | Modeling dendrite density from magnetic resonance diffusion measurements[END_REF]) because we just want to calculate a leading order change in the estimated v c . Thus, it is sufficient to just use two terms in the b-value to approximate S c (b). We fix ADC cyl 0 = 1.0×10 -3 mm 2 /s and AK cyl 0 = 12/5 to be the values that we analytically computed above for straight cylinders with orientations that are uniformly distributed on the unit sphere, where we supposed that the intrinsic D 0 = 3.0 × 10 -3 mm 2 /s. In addition, we assume the true volume fraction of the cylindrical cells to be v c = 0.7 and the effective diffusivity of the combined compartment of the spherical cells and the extra-cellular space to be D ec = 0.3 × 10 -3 mm 2 /s, as simulated for v s = 0.15, v e = 0.15 previously (see Fig. 2), where we chose the value associated with the κ s = 10 -5 m/s and ∆ = 40ms.

Given v c , D ec , ADC cyl 0 , AK cyl 0 defined above, we can now compute the ADC 0 and AK 0 of the no-exchange model:

ADC 0 = (1 -v c )D ec + v c ADC cyl 0 , (21)
AK 0 = 3(1 -v c )(D ec ) 2 + 3v c (ADC cyl 0 ) 2 + v c (ADC cyl 0 ) 2 AK cyl 0 -3(ADC 0 ) 2 (ADC 0 ) 2 . ( 22
)
Then we create a permeable signal by arguing that at relatively low (but non-negligible) cylindrical cells permeability, the ADC 0 should remain unchanged, while the AK 0 should decrease. Thus, we ask the question, if one lowers the AK 0 of the no-exchange model to AK 0 (1 -ǫ) to account for cylindrical cells permeability while keeping the ADC 0 the same, what happens to the estimated v c and D ec if we fix ADC cyl 0 and AK cyl 0 at their original values? We note here that of course, it is not possible to write down the complete permeable signal just from knowing the impermeable signal and the permeability coefficient κ. What we assume about the permeable signal is just that the ADC 0 stays the same with respect to the impermeable signal and the the AK 0 is decreased by a certain amount compared to the impermeable signal.

We set the two expressions in (21-22) equal to ADC 0 = ADC 0 and AK 0 = AK 0 (1 -ǫ), and solve for the v c and D ec associated with the permeable signal, while keeping the original ADC cyl 0 and AK cyl 0 . We show the results in Fig 5 for ǫ from 0 to 50 percent. We see that v c is under-estimated compared to its true value of 0.7 as ǫ increases. We also see that D ec is over-estimated compared to its true value of D ec = 0.3 × 10 -3 mm 2 /s. This is a simple analysis of one factor that may contribute to the under-estimation of v c due to permeable cylindrical cells observed in [START_REF] Jespersen | Neurite density from magnetic resonance diffusion measurements at ultrahigh field: Comparison with light microscopy and electron microscopy[END_REF]). There of course may also be other contributing factors that we did not account for in this analysis. 19,20). As ǫ, the percentage reduction of AK 0 , increases, e v c is more and more under-estimated compared to its true value of 0.7 and g D ec is more and more over-estimated compared to its true value of D ec = 0.3 × 10 -3 mm 2 /s.

Conclusions

We presented a method for the numerical solution of the multiple compartments Bloch-Torrey partial differential equation by coupling a standard Cartesian spatial discretization with an adaptive time discretization using the explicit Runge-Kutta-Chebyshev method and showed that it is more efficient than the Forward Euler time discretization. This method can be easily implemented on multiple processors to shorten the computational time because all interactions between the unknowns are local and it suffices to divide the computational domain into sub-domains that are loaded on the different processors.

We used this method to simulate the extra-cylindrical compartment dMRI signal in a tissue model of the brain gray matter consisting of cylindrical cells, spherical cells, and the extra-cellular space, and noted that the signal contribution from the extracylindrical compartment may not be Gaussian at some relevant dMRI diffusion times. We also computed that, as a first order effect, neglecting cylindrical cells permeability would result in an under-estimation of the cylindrical cells volume fraction if using a no-exchange model of the diffusion signal attenuation.

  Fig 1(a) for a rendering of the geometry with R c = 1.25µm, R s = 4µm, v e = 0.15 and v s = 0.15. We discretized C by a regular mesh with spatial spacing h. See Fig 1(b) for a cross section view of the discretized mesh at h = 0.125µm.

Figure 1 .

 1 Figure 1. Left: a rendering of the simulation geometry consisting of 250 randomly placed and oriented cylinders and 10 randomly placed spheres (zoomedin view). Right: a cross section view of the discretized mesh of the geometry with h = 0.125µm (zoomed-in view).

Figure 2 .

 2 Figure 2. In the extra-cylindrical compartment comprising of the spherical cells (v s = 0.15) and the extra-cellular space (v e = 0.15) and where the water molecules are stopped from entering the cylindrical cells, the ADC 0 and the AK 0 are computed for the signal arising only from this compartment. Four values of spherical cell permeability: κ s = 0m/s (solid line), κ = 1 × 10 -5 m/s (dash-dots), κ = 1 × 10 -4 m/s (dashes), κ = ∞m/s (dots), were simulated on two meshes with spatial discretization h = 0.25µm (circles) and h = 0.125µm (stars).

  15, v s = 0.15 (stars in Fig 3). In Fig 3 we show the ADC 0 of the extra-cellular compartment (EX), the spheres compartment (SPH), and the combined extra-cylindrical compartment (EX+SPH).

Figure 3 .

 3 Figure 3. Fixing the positions of the cylinders and spheres as in Fig 2 and setting κ s = 0 to study the ADC 0 of the spherical cells and the extra-cellular space separately as R c and R s are varied. Legend: Circles: R c = 1µm, R s = 4µm (v e = 0.28, v s = 0.15). Crosses: R c = 1µm, R s = 5µm (v e = 0.25, v s = 0.25). Stars: R c = 1.25µm, R s = 4µm (v e = 0.15,v s = 0.15).

Figure 4 .

 4 Figure 4. Left: Efficiency of RKC over the Forward Euler time stepping method for two discretizations of the extra-cylindrical compartment whose results are shown in Fig 2. The efficiency of the RKC method is how much faster the RKC method runs than the Forward Euler method during the course of simulation (=E RKC defined in (18)). Center and right: study of numerical error associated with slanted cylinders when using a Cartesian discretization mesh. DMRI signals were computed by putting water molecules only inside a single impermeable cylinder oriented 45 degrees with respect to the diffusion gradient direction. "xdir": cylinder oriented parallel to [1,0,0]. "xy-dir": cylinder oriented parallel to [1,1,0]. Center: For both cylinder orientations, the log S(b) are straight lines in b, but with slightly differing The theoretical value of ADC 0 should be ADC cyl 0 = D 0 /2 = 1.5 × 10 -3 mm 2 /s. Right: ADC 0 relative error in percent= (ADC 0 -ADC cyl 0 )/ADC cyl 0

  making α = π/4 and ADC cyl 0 = D 0 /2 = 1.5 × 10 -3 mm 2 /s. We placed water molecules in the center of the cylinder, covering 4µm along the length of the cylinder. The computation box is C = [-25, 25]µm × [-2, 2]µm × [-2, 2]µm and the mesh has spatial discretization h = 0.25µm. Next, we rotated the cylinder to o = [1, 1, 0]/ √ 2 and now measured the diffusion in the direction g/ g = [1, 0, 0]. The theoretical ADC cyl 0 is the same. We use the computation box C = [-25, 25]µm × [-25, 25]µm × [-2, 2]µm and three meshes with spatial discretizations h = 0.25, h = 0.125, h = 0.0625µm. We see in in Figure 4(b) that the log S(b) curves are straight lines in b for all the configurations but their slopes differ. This is numerical error associated with the Cartesian discretization of the slanted cylinder so we conducted a convergence study of the ADC 0 of the "xy-dir" cylinders at four discretization steps: h = 0.25, 0.125, 0.0625, 0.0315µm, using the computational domain C = [-25, 25]µm × [-25, 25]µm × [-h/2, h/2]µm. We computed the ADC 0 from two b-values: ADC 0 = -(log S(250) -log S(0)) /250. We see in Fig 4(c) that ADC 0 converges to the exact value ADC cyl 0 with first order in h.

Figure 5 .

 5 Figure5. The results of fitting ADC 0 = ADC 0 and AK 0 = AK 0 (1 -ǫ) of a permeable signal to the no-exchange model in(19,20). As ǫ, the percentage reduction of AK 0 , increases, e v c is more and more under-estimated compared to its true value of 0.7 and g D ec is more and more over-estimated compared to its true value of D ec = 0.3 × 10 -3 mm 2 /s.

Acknowledgment

This work was funded in part by the Agence Nationale de la Recherche project "SIMUDMRI".