Emmanuel Hainry

Emmanuel Jeandel

Romain Péchoux

Olivier Zeyen

ComplexityParser: an automatic tool for certifying poly-time complexity of Java programs

ComplexityParser is a static complexity analyzer for Java programs providing the first implementation of a tier-based typing discipline. The input is a file containing Java classes. If the main method can be typed and, provided the program terminates, then the program is guaranteed to do so in polynomial time and hence also to have heap and stack sizes polynomially bounded. The application uses antlr to generate a parse tree on which it performs an efficient type inference: linear in the input size, provided that the method arity is bounded by some constant.

Introduction

Motivations. The use of tiering techniques to certify program complexity was kick-started by the seminal works of Bellantoni-Cook [START_REF] Bellantoni | A new recursion-theoretic characterization of the polytime functions[END_REF] and Leivant-Marion [START_REF] Leivant | Lambda calculus characterizations of poly-time[END_REF], that provide sound and complete characterizations of the class of functions computable in polynomial time FP. Tiering was later adapted to several other complexity classes such as FPSPACE [START_REF] Leivant | Ramified recurrence and computational complexity II: substitution and poly-space[END_REF], NC [START_REF] Bonfante | Two function algebras defining functions in NC k boolean circuits[END_REF][START_REF] De Naurois | Pointers in recursion: Exploring the tropics[END_REF][START_REF] Leivant | A characterization of NC by tree recurrence[END_REF], or L [START_REF] De Naurois | Pointers in recursion: Exploring the tropics[END_REF].

Despite these numerous theoretical results, tiering, until now, had no practical application in automatic complexity analysis because of a lack of expressive power. Indeed, the tiering discipline severely constrains the way first order functional programs can be written. This problem has been solved by the cornerstone work of [START_REF] Marion | A type system for complexity flow analysis[END_REF] that has exhibited and studied the relations between tiering and non-interference on imperative programs. It has been extended to fork processes [START_REF] Hainry | Type-based complexity analysis for fork processes[END_REF], object-oriented programs [START_REF] Leivant | Evolving graph-structures and their implicit computational complexity[END_REF][START_REF] Hainry | Objects in polynomial time[END_REF][START_REF] Hainry | A type-based complexity analysis of object oriented programs[END_REF], and type-2 polynomial time [START_REF] Hainry | A tier-based typed programming language characterizing feasible functionals[END_REF], hence showing its portability and paving the way for practical implementations.

The core idea is the design of a type discipline ensuring polynomial time termination. The type system, inspired by non-interference, splits program variables, expressions, and statements in two disjoint tiers, denoted 0 and 1, and enforces constraints on the data flow, the control flow and sizes:

-Data flow. Data flows from tier 0 to tier 1 are prohibited, e.g. if x is of tier 0 and y is of tier 1 then the statement y = x; cannot be typed, and data flows from tier 1 to tier 0 are prevented for non-primitive data. It forbids tier 1 data from increasing by side effects. -Control flow. Loop control flows depending on tier 0 data are forbidden. I.e. in a while(e){c} statement, the expression e is enforced to be of tier 1. This implies that all the variables of e are of tier 1.

-Size control. Tier 1 data cannot make the memory size increase, e.g. if x is of tier 1 then x = x-1; is typable but x = x+1; and x = new C(x); are not typable.

Theorem 1 ([15]). If a program is typable and terminates on input d then its runtime, heap space, and stack space are polynomially bounded in the size of d.

Contribution. This paper describes the architecture of ComplexityParser, a tier-based automatic cost analyzer for Java programs implementing the type system of [START_REF] Hainry | Objects in polynomial time[END_REF][START_REF] Hainry | A type-based complexity analysis of object oriented programs[END_REF] in Java, built using Maven, and whose source code is fully available at https://gitlab.inria.fr/hainry/complexityparser. The application receives as input a text file program and infers a type (called tier) as output.

If the type inference succeeds and the analyzed program terminates then: the program is certified to have a worst case execution time bounded polynomially, by Theorem 1. Even in case the full program cannot be typed, the success of typing some methods will be indicated, giving a complexity certificate for those methods provided they terminate.

ComplexityParser is, to our knowledge, the first implementation of a tierbased technique to a realistic programming language: the analysis can deal with an expressive fragment of Java programs with while loops, recursive methods, exception handlers, and inheritance (including overriding methods) and allowing the programmer to define inductive and cyclic data (List and Ring for example). This application is, with RAJA [START_REF] Hofmann | Efficient type-checking for amortised heap-space analysis[END_REF][START_REF] Hofmann | Automatic type inference for amortised heap-space analysis[END_REF] and RaML [START_REF] Hoffmann | Resource Aware ML[END_REF], one of the first practical type-based approaches for certifying program complexity. It provides the first implementation of a complete technique with respect to polynomial time. Its code is open source (Apache 2.0 license), and its performance is good: the type analysis is linear in the size of the input program in practice. Moreover, it is fully automatic as types (tiers) are inferred and do not need to be explicitly provided by the programmer.

The implemented analyses [START_REF] Marion | A type system for complexity flow analysis[END_REF][START_REF] Hainry | Objects in polynomial time[END_REF][START_REF] Hainry | A type-based complexity analysis of object oriented programs[END_REF] are complete for the class of polynomial time computable functions, i.e. capture all functions. However they can yield false negatives, i.e. programs running in polynomial time that cannot pass the type inference, which cannot be avoided as the problem of knowing if a program computes a polytime function is not decidable [START_REF] Hájek | Arithmetical hierarchy and complexity of computation[END_REF].

Related works. We know of few alternative tools studying the complexity of Object Oriented programs.

-AProVE [START_REF] Frohn | Complexity analysis for java with AProVE[END_REF], initially a termination tool, was expanded to treat complexity by translating constraints into integer constraints, then using an external integer programming solver. AProVE works on Java bytecode and supports most features of the language except recursion. It outputs O(n k ) bounds.

costa [START_REF] Albert | Cost analysis of Java bytecode[END_REF][START_REF] Albert | Cost analysis of object-oriented bytecode programs[END_REF] infers symbolic costs upper bounds on Java bytecode by generating recurrence equations relatively to a chosen cost measure and then by finding an upper bound on a solution to these equations. The upper bounds it computes are combinations of polynomials and logarithms.

raja [START_REF] Hofmann | Automatic type inference for amortised heap-space analysis[END_REF] automatically computes linear bounds on the heap space used by a Featherweight Java program. It translates the memory constraints into graphs and solves linear cases. Exceptions, overloading and variable shadowing are also not treated. Note that this tool captures LinSpace.

speed [START_REF] Gulwani | SPEED: symbolic complexity bound analysis[END_REF][START_REF] Gulwani | SPEED: precise and efficient static estimation of program computational complexity[END_REF]

ComplexityParser Overview

ComplexityParser concretizes the principles presented in Section 1. It is implemented in Java with around 5000 lines. To illustrate the analyzed language, a reduced example is given in Figure 1. More examples are available in the repository 1 .

Example 1. Figure 1 implements a BList class (representing binary numbers as lists of booleans). It is annotated with the tiers inferred by the type system. For methods, the tier is of the form α 0 × • • • × α n → α to denote that the current object is of tier α 0 , the n arguments have tiers α i , for i ≥ 1, and the output has tier α.

-Getters have two possible tier signatures: 0 → 0 or 1 → 1, illustrating the fact that if the current object is of tier α, its fields are of tier α; -setTail modifies a field, hence current object and argument must have the same tier. Since it can make the current object grow, this tier must be 0; BList ( boolean v , BList q ) { value = v ; tail = q ; } Input and parse tree generation. The input is a string encoding of a text file containing a collection of Java classes. As illustrated in Figure 1, some statements in the main method can be encompassed between #init tags to be treated as the input data of the complexity analysis. No tier-based complexity analysis is performed on these statements and, consequently, they are not subject to the typing constraints described in Section 1. While this block is necessarily fixed in our textual examples, it should be understood as a modifiable block: it is the way for the user to build the input on which the program should run. We chose this somewhat clunky way of representing input instead of simply passing them as arguments of the main method because Java only allows String arrays as arguments and translating such inputs would blur the point. The program uses antlr2 , a lexer/parser generator, and creates a new parser instance based on the full Java grammar described in [START_REF] Parr | The definitive ANTLR 4 reference[END_REF] extended with an input tag #init, a declassification tag #declass, and variable tier declarations (e.g. int<0> x;).

Stages of type inference. Tiers and typing judgments of [START_REF] Hainry | A type-based complexity analysis of object oriented programs[END_REF] are implemented in an object hierarchy. The class Tier contains the constants T0, T1 and None for representing the tiers 0, 1, and "undefined", plus some useful static methods on tiers. A method can have several types that will depend on its caller context (encoded in an environment tier field env). When typing a method, the tiers of the this object and of input arguments should be mapped to the tier of the output.

Type inference is performed in 3 stages (see Figure 2) to compute the admissible method tiers and finally visiting the parse tree to check if the whole program types. The methods' admissible tier list, which is initialized as all the combinatorial possible tiers for each input and output in the 1 st stage, is progressively reduced to encompass only the set of admissible tiers in the 2 nd stage. The 3 rd stage checks for admissible constructor tiers. The typing discipline is performed using visitors that are specialized for each node type of the parse tree. For example, the code of the while statement visitor is provided in Figure 3. It implements the following rule (rephrased rule (Wh) from [START_REF] Hainry | A type-based complexity analysis of object oriented programs[END_REF]) enforcing any while statement to be controlled by a tier T1 expression: Γ ⊢ env ctx.expression() : T1 Γ ⊢ ctx.statement() : st env, st ∈ {T0, T1} Γ ⊢ while(ctx.expression()){ctx.statement()} : T1

Output. The output consists in the GUI displaying the "Final result", the tier of main method body. 0 and 1 represent success and entail, by Theorem 1, that if the program terminates then its runtime is polynomial. The final result can also be None, indicating a failure to type. This latter case does not imply that the main method complexity is not polynomial as there are false negatives. However some other method declarations in the program may have typed, which guarantees their complexity to be polytime under the termination assumption.

Complexity. Type inference for tier-based typing disciplines was shown to be linear in the size of the input program using a reduction to 2-SAT [START_REF] Hainry | Type-based complexity analysis for fork processes[END_REF][START_REF] Hainry | A type-based complexity analysis of object oriented programs[END_REF]. However ComplexityParser's inference algorithm is based on a brute force implementation that remains linear in practice but is exponential in theory.

Let |p| be the size (i.e. number of symbols) of the Java program given as input and ar(p) be the maximal number of parameters of a method in the program p.

The first part of our algorithm builds the parse tree of the considered program using the antlr ALL(*) algorithm that is in O(|p| 4 ) in theory [START_REF] Parr | Adaptive LL(*) parsing: the power of dynamic analysis[END_REF] and produces a parse tree of size linear in the size of the input program.

Then, the 3 stages of Figure 2 visit the parse tree nodes linearly often. In the 1 st stage, when visiting a method declaration node, all admissible tier combinations are added to the typing environment, costing O(2 n ), for a method with n parameters. Searching fixpoints in the 2 nd stage has a WCET in O(2 ar(p) |p|): at each step, either the list of possible tier combinations is decremented or the environment is unchanged and the program jumps to the 3 rd stage. Typing recursive methods relies on computing the strongly connected components of a graph using the standard Kosaraju DFS algorithm [START_REF] Sharir | A strong-connectivity algorithm and its applications in data flow analysis[END_REF] which also has linear complexity. The 3 rd stage performs in O(|p|) as it simply type-checks constructor bodies.

Putting all together, the complexity of the analysis is in O(2 ar(p) |p| + |p| 4 ). We argue that ar(p) should be a small constant independent of the program. Indeed, following [START_REF] Bloch | Effective Java, 2nd Edition. The Java series[END_REF], it is a good practice to "avoid long parameter lists. As a rule, three parameters should be viewed as a maximum, and fewer is better."

The O(|p| 4 ) part is due to antlr's complexity which, according to its authors, "performs linearly on grammars used in practice", such as the Java grammar. Finally, we claim that the whole analysis also has linear complexity in practice, as highlighted by our tests on sample programs.

Conclusion

ComplexityParser is an efficient and automatic high level complexity analyzer for Java programs. The analysis can deal with most well-known Java constructs. There are still some syntactic restrictions on the expressive power of the analysis such as not treating for loops. Plans for future work include the treatment of threads as in [START_REF] Marion | Complexity information flow in a multi-threaded imperative language[END_REF], and symbolic computation of the polynomial bounds as in [START_REF] Hainry | A type-based complexity analysis of object oriented programs[END_REF] on execution time, heap space, and stack space. Unfortunately, due to object data controlling the flow, tight bounds are difficult to infer. Our approach requires a termination certificate (see Theorem 1). This issue can be overcome by combining our tool with existing termination techniques, e.g. [START_REF] Lee | The size-change principle for program termination[END_REF][START_REF] Podelski | Transition predicate abstraction and fair termination[END_REF] or loop invariant generation techniques, e.g. [START_REF] Ben-Amram | On the linear ranking problem for integer linearconstraint loops[END_REF][START_REF] Ben-Amram | Tight worst-case bounds for polynomial loop programs[END_REF][START_REF] Shkaravska | Test-based inference of polynomial loop-bound functions[END_REF]. We also consider interfacing with existing termination analyzers working on Java such as Julia [START_REF] Spoto | A termination analyzer for java bytecode based on path-length[END_REF], or other complexity analyzers that prove termination like AProVE or costa.

1 public 2 visitChildren ( ctx ) ; 3 4 6

 12346 Object visitState m en t _w h il e (... ctx ) { Tier t = getTier ( ctx . expression () ) ; Tier env = getEnviron me n tT i er ( ctx . expression () ) ; 5 incrementW h il e Co u nt () ; Tier res ;

7

  if ( g e t R e c u r s i v e C a l l s C o u n t () != 0) { 8 res = Tier . None ; 9 env = Tier . None ;

10 } 11 if 19 }Fig. 3 .

 1011193 Fig. 3. Visitor method for while statements in BaseStatementVisitor

  infers symbolic complexity bounds on the number of statements executed by a C++ program. It relies on integer counters inserted in the program by the programmer. As such, it is not fully automatic and does not treat objects as first class citizens.-TcT[START_REF] Avanzini | TcT: Tyrolean complexity tool[END_REF][START_REF] Moser | From Jinja bytecode to term rewriting: A complexity reflecting transformation[END_REF] is a generic complexity tool which, for what interests us analyzes Jinja bytecode. It translates code into term rewriting systems for which it uses integer programming techniques. Jinja bytecode does not support recursion and cyclic data but otherwise has all language features we checked.A summary of the above tools' features is presented in the following table. For each tool, we check language features support (recursion, exceptions, inheritance, cyclic data), whether it gives explicit bounds, whether it works on a High-Level language (HLL) or on bytecode, and last if it is fully automatic.

	Tool	Recursion Exceptions Inheritance Cyclic Bounds HLL Auto
	ComplexityParser	Yes	Yes	Yes	Yes	No	Yes Yes
	AProVE	No	Yes	Yes	Yes	Yes	No Yes
	costa	Yes	Yes	Yes	No	Yes	No Yes
	raja	Yes	No	Partial	Yes	Yes Yes Yes
	speed	Yes	No	No	No	Yes Yes No
	TcT	No	Yes	Yes	No	Yes	No Yes

  length is recursive hence input tiers must be 1; -isEqual iterates on the current object and on other they must be of tier 1.-Variables b1, b2 created inside the #init block automatically get tier 1; -The next lines of method main check, except the last one (line 35) which tries to apply isEqual on an object of tier 0 instead of tier 1.ComplexityParser's behavior is described by the state diagram of Figure2. We will describe this behaviour in detail in the rest of this section.

	6 7	boolean getValue () { return value ; } antlr input 1 st stage 2 nd stage 3 rd stage // 0 → 0 or 1 → 1 output visit() visit(ctx)
	8 9	void setTail ( BList t ) { tail = t ; } Table of symbols BList getTail () { return tail ; } Typing listener visit() Call graph loops while method tiers	// 0 × 0 → 0 // 0 → 0 or 1 → 1
		are modified
		Fig. 2. Program state diagram
	20	# init
	21	BList b1 = new BList ( true , null ) ;
	22	b1 = new BList ( false , b1 ) ;
	23	b1 = new BList ( true , b1 ) ;
	24	BList b2 = new BList ( true , null ) ;
	25	b2 = new BList ( false , b2 ) ;
	26	// b1 : 1; b2 : 1
	27	# init
	28
	29	BList tail1 = b1 . clone () ;	// tail1 : 0
	30	tail1 = tail1 . getTail () ;	// tail1 : 0
	31	boolean res = b1 . lessOrEqual ( b2 ) ; // res : 1
	32	res = b1 . isEqual ( b2 ) ;	// res : 1
	33	b1 . concat ( b2 . clone () ) ;	// OK
	34	res = tail1 . isEqual ( b1 ) ;
	35	// Fails as isEqual needs tail1 to be of tier 1
	36	}
	37	}
		Fig. 1. Binary numbers as lists (extract from example11.txt)

10 void concat ( BList other ) { /* ... */ } // 1 × 0 → 1 11 int length () { /* recursive method */ } // 1 → 0 12 boolean isEqual ( BList other ) { /* simple while loop */ } 13 // isEqual : 1 × 1 → 1 14 boolean lessOrEqual ( BList other ) { /* while loop */ } 15 // lessOrEqual : 1 × 1 → 1 16 } 17 18 class Exe { 19 void main ( String [] args ) {

https://gitlab.inria.fr/hainry/complexityparser/-/tree/master/examples

www.antlr.org


Xue-Gong Li
email: xuegongli@idsse.ac.cn

; Ze-Xi Jiao

Huan-Huan Zhang

Jun Xu
email: xujunn@sjtu.edu.cn

Wei-Jia Zhang

Xiao-Qing Qi

Long-Fei Wu

Complete genome sequence of Crassaminicella sp. 143-21, isolated from a deep-sea hydrothermal vent

Keywords: CDS, coding sequence, COG, clusters of orthologous groups, GO, gene ontology, KEGG, Kyoto Encyclopedia Crassaminicella, Chemoorganotroph, Hydrothermal vent, Adaptation, Complete genome

Crassaminicella sp. 143-21, a putative new species isolated from deep-sea hydrothermal vent chimney on the Central Indian Ridge (CIR), is an anaerobic, thermophilic and rod-shaped bacterium belonging to the family Clostridiaceae. In this study, we present the complete genome sequence of strain 143-21, comprising 2,756,133 bp with a G+C content of 31.1 %. In total, 2,427 protein coding genes, 121 tRNA genes and 33 rRNA genes were obtained. Genomic analysis of strain 143-21 revealed that numerous genes related to organic matter transport and catabolism, including peptide transport, amino acid transport, saccharide transport, ethanolamine transport and corresponding metabolic pathways. Further, the genome contains a large proportion of genes involved in translation, ribosomal structure, and signal transduction. These genes might facilitate microbial survival in deep-sea hydrothermal vent environment. The genome of strain 143-21 will be helpful for further understanding its adaptive strategies in the deep-sea hydrothermal vent environment.

Introduction

Hydrothermal vents are a typical deep-sea ecosystem that possesses a steep gradient in terms of temperature, redox potential, pH, and substrate concentration when hot venting fluids mix with the surrounding cold sea water [START_REF] Martin | Hydrothermal vents and the origin of life[END_REF]. Microorganisms inhabiting such ecosystems are mainly chemolithotrophic, which exploiting the chemical disequilibrium provided by the mixing of reducing hydrothermal fluids and oxidizing seawater, and harnessing this energy to fix inorganic carbon into biomass [START_REF] Dick | The microbiomes of deep-sea hydrothermal vents: distributed globally, shaped locally[END_REF][START_REF] Nakagawa | Deep-sea vent chemoautotrophs: diversity, biochemistry and ecological significance[END_REF]. These microbial communities are important primary producers and fuel the vent ecosystems. Culture-dependent and culture-independent approaches have exposed a vast diversity of chemotrophic microorganisms in hydrothermal vent ecosystems [START_REF] Nakagawa | Deep-sea vent chemoautotrophs: diversity, biochemistry and ecological significance[END_REF][START_REF] Fortunato | Spatially distinct, temporally stable microbial populations mediate biogeochemical cycling at and below the seafloor in hydrothermal vent fluids[END_REF][START_REF] Sievert | Chemoautotrophy at Deep-Sea Vents Past, Present, and Future[END_REF][START_REF] Wang | The oxidation of hydrocarbons by diverse heterotrophic and mixotrophic bacteria that inhabit deep-sea hydrothermal ecosystems[END_REF], however, only a few of them are culturable [START_REF] Orcutt | Microbial ecology of the dark ocean above, at, and below the seafloor[END_REF]. Most of investigations of deep-sea hydrothermal vents focused on thermophilic and hyperthermophilic microorganisms, only a few number of moderate thermophiles were isolated [START_REF] Slobodkina | Clostridium tepidiprofundi sp. nov., a moderately thermophilic bacterium from a deep-sea hydrothermal vent[END_REF]. Therefore, these cultivatable moderate thermophiles are likely to provide us with valuable insights into life in the deep-sea hydrothermal systems.

The phylum Firmicutes includes a very heterogeneous assemblage of bacteria, some of them were identified as dominant groups in the deep-sea hydrothermal vents [START_REF] Cao | Microbial Sulfur Cycle in Two Hydrothermal Chimneys on the Southwest Indian Ridge[END_REF][START_REF] Sinha | Polyphasic approach revealed complex bacterial community structure and function in deep sea sediment of ultra-slow spreading Southwest Indian Ridge[END_REF]. The genus Crassaminicella belongs to the Clostridiaceae family within phylum Firmicutes and was first reported in 2015 [START_REF] Lakhal | Crassaminicella profunda gen. nov., sp. nov., an anaerobic marine bacterium isolated from deep-sea sediments[END_REF]. Members of this genus are often obligate anaerobes and heterotrophs that use organic matter such as tryptone and glucose [START_REF] Lakhal | Crassaminicella profunda gen. nov., sp. nov., an anaerobic marine bacterium isolated from deep-sea sediments[END_REF][START_REF] Li | Genome analysis of Crassaminicella sp. SY095, an anaerobic mesophilic marine bacterium isolated from a deep-sea hydrothermal vent on the Southwest Indian Ridge[END_REF]. At the time of writing, this genus comprises only one species of hydrothermal origin, Crassaminicella profunda Ra1766H T , which was isolated from geothermal sediments of the Guaymas Basin at a depth of 2,002 m [START_REF] Lakhal | Crassaminicella profunda gen. nov., sp. nov., an anaerobic marine bacterium isolated from deep-sea sediments[END_REF]. Recently, we have isolated a potential new species of genus Crassaminicella, strain SY095, from a deep-sea hydrothermal vent on the Southwest Indian Ridge. Genomic analysis showed that strain SY095 genome harbors multiple prophages, some of them carry additional genes that may be involved in the regulation of sporulation [START_REF] Li | Genome analysis of Crassaminicella sp. SY095, an anaerobic mesophilic marine bacterium isolated from a deep-sea hydrothermal vent on the Southwest Indian Ridge[END_REF]. The genome information expanded our understanding of the adaptation strategies of genus Crassaminicella to the deep-sea hydrothermal vent high pressure and high temperature environments. In this study, strain 143-21 was isolated from a chimney sample that was collected at the depth of 2,440 m from the site Kali (25.32° S, 70.04° E) located in the Kairei hydrothermal field of the intermediate spreading Central Indian Ridge (CIR) using the manned submersible "Shen Hai Yong Shi" during the TS10-3 cruise of R/V "Tan Suo Yi Hao" on February 2019. Physiological analysis showed that strain 143-21 is obligate anaerobic and heterotrophic moderate thermophiles with an optimum growth temperature of 50 ℃. 16S rRNA gene sequence identities showed that it was most closely related to the C. profunda Ra1766H T (95.91 % identity), which indicated that strain 143-21 represent a novel species within the genus Crassaminicella. Here we report the complete genome sequence of strain 143-21 for facilitating an understanding of microbial adaptation to deep-sea hydrothermal vent habitats.

Data description

Strain 143-21 grown on JCM 909 medium (https://jcm.brc.riken.jp) at 50 ℃ was harvested in late exponential-phase by centrifugation (4,500 g, 20 min). Genomic DNA was extracted using a MagAttract DNA Kit (Qiagen, USA) according to the manufacturer's instructions and sequenced on the PromethION and MGI-SEQ 2000 systems at Wuhan Nextomics Biosciences Co., Ltd. (Wuhan, China). About 2.5 Gb clean data were generated to reach approximately 837-fold depth of coverage. Clean reads were assembled using the Unicycler version 0.4.8 [START_REF] Wick | Unicycler: Resolving bacterial genome assemblies from short and long sequencing reads[END_REF] and polished using Pilon v1.22 [START_REF] Walker | Pilon: an integrated tool for comprehensive microbial variant detection and genome assembly improvement[END_REF]. Gene predictions were made using Prodigal version 2.6.3 [START_REF] Hyatt | Prodigal: prokaryotic gene recognition and translation initiation site identification[END_REF]. Gene annotation was performed by a sequence similarity search against the non-redundant protein database available from the National Center for Biotechnology Information, Clusters of Orthologous Groups (COG) database [START_REF] Galperin | Expanded microbial genome coverage and improved protein family annotation in the COG database[END_REF] and Gene Ontology (GO) database [START_REF] Ashburner | Gene Ontology: tool for the unification of biology[END_REF]. The carbohydrate-active enzymes (CAZymes) were predicted by the dbCAN meta server [START_REF] Yin | dbCAN: a web resource for automated carbohydrate-active enzyme annotation[END_REF] using the CAZy database [START_REF] Lombard | The carbohydrate-active enzymes database (CAZy) in 2013[END_REF]. Metabolic pathways were predicted by using KEGG Automatic Annotation Server (KAAS) [START_REF] Kanehisa | Data, information, knowledge and principle: back to metabolism in KEGG[END_REF]. The rRNA and tRNA genes were identified using RNAmer version 1.2 [START_REF] Lagesen | RNAmmer: consistent and rapid annotation of ribosomal RNA genes[END_REF] and tRNAscan-SE version 2.0 [START_REF] Lowe | tRNAscan-SE On-line: integrating search and context for analysis of transfer RNA genes[END_REF], respectively. Clustered regularly interspaced short palindromic repeat (CRISPR) arrays were analyzed using the Minced program version 0.4.2 [START_REF] Bland | CRISPR Recognition Tool (CRT): a tool for automatic detection of clustered regularly interspaced palindromic repeats[END_REF], and genomic island was identified using Islander program version 1.2 [START_REF] Hudson | Islander: a database of precisely mapped genomic islands in tRNA and tmRNA genes[END_REF]. The graphic circular map of the genome was generated using Circos version 0.69 [START_REF] Krzywinski | Circos: an information aesthetic for comparative genomics[END_REF]. ), are lower than the other two strains. These differences may reflect the adaptation of strains to its local habitat.

Organic matter catabolism and energy metabolism

Strain 143-21 is chemoheterotrophic that can grow on amino acids, tryptone and saccharides. Correspondingly, its genome encoded for several transport systems that might participate in the uptake of peptides, amino acids, glucose, ribose, fructose, and raffinose/stachyose/melibiose. We further analyzed the utilization pattern of carbon source with the Carbohydrate-Active Enzymes (CAZy) database. The result showed that strain 143-21 genome contains 35 CAZymes including 18 glycosyltransferases (GTs), 10 glycoside hydrolases (GHs), 6 Carbohydrate esterases (CEs), and 1 carbohydrate-binding modules (CBM). GTs could catalyze glycosyl group transfer to a nucleophilic group and form a glycoside, which may be involved in the amino sugar and nucleotide sugar metabolism. Among GHs, genes related to degradation of N-acetylglucosamine, glycogen, cellobiose, maltose, and fructose were found. We speculated that these genes could be helpful for the survival of strain 143-21 in deep-sea vent habitats by reinforcing acquisition of nutrients from the extreme environment. Strain 143-21 contained a great number of genes that encoded complete glycolysis/gluconeogenesis pathway and pentose phosphate pathway. In addition, 12 families of peptidases and 10 kinds of aminotransferases were annotated, which digest peptides to produce a variety of amino acids and further metabolism.

In the genome of strain 143-21, thirty genes encoding ethanolamine utilization-related proteins were observed in two clusters (Fig. 2). Gene cluster I (KVH43_01845-01895) contains the key genes of ethanolamine utilization, eutB and eutC, which encoding the two subunits of the ethanolamine ammonia lyase and breaks ethanolamine down into the gases acetaldehyde and ammonia [START_REF] Kaval | Ethanolamine Utilization in Bacteria[END_REF]. In addition, some accessory genes and regulatory genes can be found in this cluster. Gene cluster II (KVH43_06710-06800) mainly contains genes encoding the bacterial microcompartments, where the catabolic reactions occurred efficiently [START_REF] Kaval | Ethanolamine Utilization in Bacteria[END_REF].

Interestingly, such gene clusters were also presented in the strain SY095 genome, while absent in the genome of strain Ra1766H. All microbial cells are made of a bilayer of phospholipids, which contain the membrane lipid phosphatidylethanolamine. Ethanolamine can be produced when phosphodiesterases break down phosphatidylethanolamine, and is considered a valuable source of carbon and/or nitrogen for bacteria capable of its catabolism [START_REF] Kaval | Ethanolamine Utilization in Bacteria[END_REF]. Deep-sea vent ecosystem is the vast reservoir of microorganisms, it is plausible that cell membrane decomposition will accompany the release of ethanolamine. Thus, possessing ethanolamine utilization genes provide substantial competitive advantages for microbes surviving in such extreme environment. Genomic analysis also predicted an electron transport complex encoding gene cluster, which is assumed to encode a membrane-bound enzyme complex with six subunits (RnfCDGEAB). Rnf complex is a respiratory enzyme that oxidizes reduced ferredoxin and reduces NAD, coupled to ion (Na + ) transport across the cytoplasmic membrane and generate an electrochemical gradient for ATP synthesis [START_REF] Kuhns | The Rnf complex is a Na(+)coupled respiratory enzyme in a fermenting bacterium,Thermotoga maritima[END_REF][START_REF] Li | Electron transport in the pathway of acetate conversion to methane in the marine archaeon Methanosarcina acetivorans[END_REF].

Moreover, ten genes encoding F0F1 ATP synthase were observed in strain 143-21 genome. Intriguingly, we also identified similar gene clusters encoding Rnf complex and F0F1 ATP synthase in the genomes of strain SY095 and strain Ra1766H. It is proposed that Rnf complex coupled with F0F1 ATP synthase form a simple respiratory chain to increase the ATP yield, which could help Crassaminicella species to survive in the deep-sea hydrothermal vent environment.

Environmental adaptation

Genomic analysis showed that strain 143-21 possesses a series of genes related to high pressure and high temperature adaptation. Firstly, according to the COG categorization, strain 143-21 genome contains a large proportion of genes (10.20 %) related to translation, ribosomal structure and biogenesis. It has been reported that increasing the synthesis of ribosome subunits and tRNA synthase could help vent microorganism to counteract the effects of HHP on the ribosome complex [START_REF] Michoud | High hydrostatic pressure adaptive strategies in an obligate piezophile Pyrococcus yayanosii[END_REF].

Secondly

Genome sequence accession numbers

The complete genome sequence of Crassaminicella sp. 143-21 was deposited at GenBank database under the accession number CP078093. The strain has been submitted to Marine Culture Collection of China, MCCC (http://www.mccc.org.cn/) with accession number MCCC 1K06400.

Fig. 1 .

 1 Fig. 1. Schematic representation of the Crassaminicella sp. 143-21 genome. Labeling

Fig. 2 .

 2 Fig. 2. The putative ethanolamine utilization gene clusters and gene organization of

Forming

  an endospore under extreme conditions and spore germination in suitable environments may help strain 143-21 surviving in the changing deep-sea hydrothermal vent environment. Fourthly, strain 143-21 genome harbor 89 transposases, which may facilitate genomic rearrangements and gene duplication. A high proportion of transposases confer strain a strong genetic plasticity to deal with changing vent environment. In addition, the strain 143-21 genome contains four CRISPR arrays comprising a total of 78 spacer sequences, significantly more than the spacers identified in strain SY095[START_REF] Li | Electron transport in the pathway of acetate conversion to methane in the marine archaeon Methanosarcina acetivorans[END_REF] and strain Ra1766H T (53). Variation in CRISPR array sequences among different Crassaminicella species is probably an adaptation to the local habitats. In conclusion, the genomic analysis has revealed the genetic basis of strain 143-21 and provided insight into the adaptation strategies used by Crassaminicella spp. in the deep-sea hydrothermal vent.

Table 1 .

 1 General features and genome sequencing project information forCrassaminicella sp. 143-21 according to MIGS recommendations Among the 2,427 CDSs, over half CDSs were annotated using the COG (82.04 %), GO (64.56 %), and KEGG (55.83 %) databases. Upon COG classification,

	Item	Description
	MIGS data
	Project_name	Crassaminicella sp. 143-21 genome sequencing and assembly
	NCBI BioProject	Accession: PRJNA743153
	NCBI BioSample	Accession: SAMN19999416

protein-coding sequences (CDS) were predicted, which covered approximately 85.59 % of the genome. The genome encodes 121 tRNA genes, 33 rRNA genes, and 4 loci of CRISPR.

prophages, transposons (X), are higher than that in Crassaminicella sp. SY095 and C. profunda Ra1766H (Fig

S1

). While other categories, including amino acid transport and metabolism (E), carbohydrate transport and metabolism (G), inorganic ion transport and metabolism (P), and secondary metabolites biosynthesis, transport and catabolism (Q

  At spore assembly stage, SpoVM functions as a landmark protein. In addition, there are also 21 genes associated with spore germination.

	stage of growth. Searching its genome, we discovered that a total of 73 genes are
	involved in sporulation initiation, sporulation regulation, DNA translocation,
	engulfment, cortex synthesis, coat formation and assembly. spo0A is the key gene for
	sporulation initiation, which was activated after phosphorylated by histidine kinases.
	Once Spo0A was phosphorylated, many genes will participate in the sporulation
	regulation, such as spoIIAA, spoIIAB, spoIIE, spoIIGA, spoIIM, spoIIR, sigE-H,
	spoIIIA-H, and spoIVA-B.
	, strain 143-21 genome contains 9.84 % of total COG related to signal
	transduction mechanisms, which is 7.76 % in Crassaminicella sp. SY095 and 10.88 %
	in C. profunda Ra1766H (Fig S1). For strain 143-21, twelve histidine kinase sensor
	and eleven diguanylate cyclase were identified. Histidine kinase acts as a sensor in a
	two-component signal transduction system, diguanylate cyclase are involved in the
	synthesis of global second messenger cyclic diguanosine monophosphate, which
	involved in many aspects, such as biofilm formation, motility, and resistance [30]. As
	reported, two-component regulatory systems are crucial for strains to sense changes of
	surrounding environment [31]. Thus, it is reasonable to suppose that possessing
	multiple signal transduction systems plays a role in microbial survival in deep-sea
	hydrothermal vent environment. Thirdly, strain 143-21 can form an endospore at late

Acknowledgements

This research was funded by grant 2018YFC0310704, 2018YFC0309904 and 2016YFC0304905-08 from the National Key R&D Program of China, grants NSFC 91751202 and 41806174 from the National Natural Science Foundation of China, grant ZDKJ2019011 from the Major Scientific and Technological Projects of Hainan Province, grant Y9719105 for Institute of Deep-sea Technology Innovation, Chinese Academy of Sciences and a grant for LIA-MagMC from the Centre National de la Recherche Scientifique. We are very grateful to all the participants of the TS10 cruise of R/V Tan Suo Yi Hao and the pilots of the Shen Hai Yong Shi for their professional service during this cruise.

Declaration of Competing Interest

The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.


Chen Si

Cui Kaixuan

Wenyan Zhang

Zhao Yicong

Xiao Tian

Wuchang Zhang
email: wuchangzhang@qdio.ac.cn

W U Long-Fei

Observations on a magnetotactic bacteria-grazing ciliate in sediment from the intertidal zone of Huiquan Bay, China *

Keywords: magnetically responsive protist, ciliate, magnetotactic bacteria, magnetosome, graze, magnetoreception

Magnetotactic bacteria (MTB) are a group of prokaryotes having the ability to orient and swim along geomagnetic field lines because they contain intracellular magnetosomes, which are synthesized through a biomineralization process. Magnetosomes have recently also been found in unicellular eukaryotes, which are referred to as magnetically responsive protists (MRPs). The magnetosomes have three origins in MRPs. In this study we characterized a MTB-grazing ciliated MRP that was magnetically collected from intertidal sediment of Huiquan Bay, China. Based on 18S rRNA gene sequence analysis, the ciliated MRP was tentatively identified as Uronemella parafilificum HQ. Using transmission electron microscopy, we observed that magnetosomes having 2-3 shapes were randomly distributed within this ciliate. Energy-dispersive X-ray spectroscopy and high-resolution transmission electron microscopy images of the magnetosomes were consistent with them being composed of magnetite. Magnetosomes having the same shape and mineral composition were also detected in MTB that occurred in the same environment as the ciliated MRP. Statistical analysis showed that the size and shape of the magnetosomes in the ciliated MRP were similar to those in MTB. The results suggest that this ciliated MRP can graze, ingest, and digest various types of MTB. It is certainly worth noting that this is the first record of MRPs in Asian aquatic sediment and suggesting they might be widely distributed. These results also support the assertion that MRPs probably contribute to the ecological cycles of iron, and expand possibilities for research into the mechanism of magnetoreception in eukaryotes.

INTRODUCTION

Magnetotactic bacteria (MTB) are widely distributed in freshwater and marine sediments [START_REF] Blakemore | Magnetotactic bacteria[END_REF][START_REF] Frankel | Magnetite in freshwater magnetotactic bacteria[END_REF]. Their morphologies include cocci, ovoid, rod, curved rod, spirillum, and multicellular forms (the multicellular magnetotactic prokaryotes: MMPs) [START_REF] Amor | Iron-biomineralizing organelle in magnetotactic bacteria: function, synthesis and preservation in ancient rock samples[END_REF][START_REF] Rodgers | Intercellular structure in a many-celled magnetotactic prokaryote[END_REF]. Among prokaryotic microorganisms, the MTB have for decades been known to have the ability to sense magnetic fields. Their magnetotactic behavior is based on intracellular magnetosomes that are formed by intracellular biomineralization, and these enable cell orientation relative to magnetic fields. Magnetosomes are composed of magnetite (Fe 3 O 4 ) or/and greigite (Fe 3 S 4 ) [START_REF] Zhang | Characterization and phylogenetic identification of a species of spherical multicellular magnetotactic prokaryotes that produces both magnetite and greigite crystals[END_REF], and occur in cells in diverse shapes and arrangements.

The shapes include elongated prisms, cuboctahedrons, bullet-shaped, and tooth-shaped forms; they are predominantly arranged in single, double, or multiple chains, although disorderly arrangements have also been reported [START_REF] Amor | Iron-biomineralizing organelle in magnetotactic bacteria: function, synthesis and preservation in ancient rock samples[END_REF]. The composition, morphology, arrangement, and sizes of magnetosomes are species specific among MTB, and are strongly correlated with MTB phylogeny [START_REF] Lefèvre | Monophyletic origin of magnetotaxis and the first magnetosomes[END_REF].

The first microeukaryote (a dinoflagellate) showing obvious magnetotactic behavior was found in 1986 (Torres de Araujo et al., 1986). Subsequently, a number of unicellular eukaryotes (including flagellates and ciliates) that can sense and respond to magnetic fields have been reported [START_REF] Bazylinski | Occurrence and distribution of diverse populations of magnetic protists in a chemically stratified coastal salt pond[END_REF]; these are termed magnetically responsive protists (MRPs), and their occurrence provides more evidence for magnetoreception among eukaryotes [START_REF] Leão | Magnetosome magnetite biomineralization in a flagellated protist: evidence for an early evolutionary origin for magnetoreception in eukaryotes[END_REF][START_REF] Martins | Grazing protozoa and magnetosome dissolution in magnetotactic bacteria[END_REF][START_REF] Monteil | Accumulation and dissolution of magnetite crystals in a magnetically responsive ciliate[END_REF][START_REF] Monteil | Ectosymbiotic bacteria at the origin of magnetoreception in a marine protist[END_REF]. Studies have shown that there are three sources of magnetosomes in MRPs: (1) intracellular biomineralization by the protists [START_REF] Leão | Magnetosome magnetite biomineralization in a flagellated protist: evidence for an early evolutionary origin for magnetoreception in eukaryotes[END_REF]Torres de Araujo et al., 1986); (2) ectosymbiotic MTB [START_REF] Monteil | Ectosymbiotic bacteria at the origin of magnetoreception in a marine protist[END_REF]; and (3) MTB preyed upon by the protists [START_REF] Martins | Grazing protozoa and magnetosome dissolution in magnetotactic bacteria[END_REF][START_REF] Monteil | Accumulation and dissolution of magnetite crystals in a magnetically responsive ciliate[END_REF].

The first MRP, isolated from sediments of a coastal mangrove swamp, was identified by morphological examination as Anisonema platysomum (Euglenophyceae) (Torres de Araujo et al., 1986), and was found to contain thousands of bullet-shaped magnetosomes within its cell.

However, the magnetosomes in MTB from the same environmental sample predominantly contained cuboctahedron and elongated pseudohexagonal prism-shaped magnetosomes. Therefore, it was concluded that the magnetosomes in A. platysomum are formed by internal biomineralization (Torres de Araujo et al., 1986). Four types of MRP were reported from the water column of a chemically stratified coastal salt pond [START_REF] Bazylinski | Occurrence and distribution of diverse populations of magnetic protists in a chemically stratified coastal salt pond[END_REF]. Two of these, a dinoflagellate and a cryptomonad, were presumed to biomineralize magnetosomes internally, based on the magnetotactic behavior and the morphology of the magnetosome-like particles. The other two MRPs will be discussed later in this section. A flagellated protist having bullet-shaped intracellular magnetosomes was recently reported from freshwater river sediment [START_REF] Leão | Magnetosome magnetite biomineralization in a flagellated protist: evidence for an early evolutionary origin for magnetoreception in eukaryotes[END_REF]. Although bullet-shaped magnetosomes were also observed in MTB in the same environment, there were significant differences in the shape, size, and crystal properties of the MRP and MTB magnetosomes. Hence, it was suggested that the flagellated MRP can synthesize magnetosomes autonomously [START_REF] Leão | Magnetosome magnetite biomineralization in a flagellated protist: evidence for an early evolutionary origin for magnetoreception in eukaryotes[END_REF]. However, detailed molecular analysis was unavailable for this MRP. A fascinating form of magnetoreception in eukaryotes is facilitated by magnetic ectosymbiotic bacteria (MEB), which live on the surface of an excavate protist (Euglenozoa) [START_REF] Monteil | Ectosymbiotic bacteria at the origin of magnetoreception in a marine protist[END_REF]. This symbiotic relationship enables access to more favorable habitats and efficient use of nutrients [START_REF] Monteil | Ectosymbiotic bacteria at the origin of magnetoreception in a marine protist[END_REF]. The above findings have provided insights into the origin and evolution of magnetoreception in eukaryotes.

In addition to the above two sources of magnetosomes, MRPs can also acquire magnetosomes by preying on MTB and accumulating their magnetosomes. Brazilian scholars isolated a ciliate (Euplotes vannus) from lagoon sediment and conducted experiments in which the ciliate was fed MMPs under laboratory conditions. This showed that the ciliates can graze MMPs and form acidic food vacuoles to digest the MMPs and magnetosomes. However, the ciliates did not respond to changes in the magnetic field, although this may have been because too few magnetosomes were accumulated within the ciliate cells [START_REF] Martins | Grazing protozoa and magnetosome dissolution in magnetotactic bacteria[END_REF]. In natural environments, such as the chemically stratified coastal salt pond noted above, one of the four types of MRPs (another cryptomonad) was considered to be capable of consuming MTB, based on observations of the presence of vacuole-like inclusions [START_REF] Bazylinski | Occurrence and distribution of diverse populations of magnetic protists in a chemically stratified coastal salt pond[END_REF]. Furthermore, a ciliate identified by morphological and molecular characteristics as Uronema marinum was able to graze large numbers of MTB and dissolve the magnetosomes in its vacuoles [START_REF] Monteil | Accumulation and dissolution of magnetite crystals in a magnetically responsive ciliate[END_REF].

All data suggested that MTB-grazing protists play an important role in the biogeochemical cycling of iron by dissolving the magnetosomes and returning iron to the environment. To date, few types of MTB-grazing protists have been found, and research remains limited to characterizing them and expanding knowledge of their diversity. Clearly, more research is needed to clarify the magnetic response mechanism in these eukaryotes. In this study we used morphological comparison and 18S rRNA sequence analysis to characterize a population of benthic ciliates that graze magnetotactic bacteria in a natural environment.

MATERIAL AND METHOD

Sampling site description, sample collection, microcosm setup, and magnetic enrichment

Sediment samples were collected from the intertidal zone of Huiquan Bay, Qingdao, China (36°03′36.69″N, 120°21′5.09″E) in July 2019. For sample collection we removed the surface gravel and yellow sediments, and collected the subsurface gray-black sediments and in-situ seawater in 500 ml plastic sampling bottles. Prior to magnetic enrichment of MTB and MRPs, the bottles containing sediment and water were incubated as microcosms for two weeks with the lids half open in the dark (to prevent photosynthesis) at room temperature (~25℃), and without agitation.

For magnetic enrichment, two permanent button magnets (16 mT each) were fixed relatively parallel to and slightly above the sedimentwater interface, one on each side of the microcosm, with the south pole towards the bottle. The water and sediment were then mixed evenly, and the bottles were again placed in the dark to enable settling of the sediment [START_REF] Pan | Characterization of a homogeneous taxonomic group of marine magnetotactic cocci within a low tide zone in the China Sea[END_REF]. After approximately 30 min, gray and black spots were evident on the inner wall of the bottle adjacent to the attached magnets. Pasteur pipettes were used to collect the material forming the gray-black spots. A sample of approximately 1 ml containing sediment and water was removed and placed in a 2 ml centrifuge tube. After the sediment settled at the bottom of the centrifuge tube, 510 µl of the sediment and water was removed to prepare a cover glass hanging drop for microscopy [START_REF] Schüler | The biomineralization of magnetosomes in Magnetospirillum gryphiswaldense[END_REF]. A parallel magnetic field was applied to the hanging drop by placing a permanent magnet (40 mT) on each side of the drop, and the microbes in the drop were observed using differential interference contrast (DIC) microscopy (Olympus BX51 microscope equipped with a DP80 camera system; Olympus, Tokyo, Japan). Samples containing MRPs and MTB were screened for purification. The 2-ml centrifuge tubes with samples containing protists and MTB were connected to a l-ml pipette tip and a PCR tube in sequence. The entire device was filled with filtered in-situ seawater and placed in a strong magnetic field created by two permanent magnets (54 mT each) placed in parallel (Fig. 1). After approximately 2 h the purified MRPs or MTB were obtained for subsequent experimental analysis.

Observations of MRP and MTB

The DIC system was used to observe the morphology and movement of individual protists and MTB exposed to the magnetic field, and images and videos were used for analysis.

For transmission electron microscopy (TEM) observations a 5-μl purified sample of MTB or protists was placed on a carbon-coated TEM grid. To increase cell adhesion, the grids were placed on the S pole of a magnet. As the drops of water were about to dry, the grids were washed 23 times using Milli-Q water, then left to air dry at room temperature [START_REF] Pan | A species of magnetotactic deltaproteobacterium was detected at the highest abundance during an algal bloom[END_REF].

The morphological characteristics of the MTB and MRP were observed using a Hitachi H8100 microscope operating at 100 kV. High resolution transmission electron microscopy (HRTEM), selected area electron diffraction (SAED), and X-ray energy-dispersive spectroscopy (XEDS) were carried out using a JEOL JEM-2100 TEM operated at 200 kV at the Institute of Geology and Geophysics, Chinese Academy of Sciences (IGGCAS).

Data processing and statistical analysis

The length and width of the MTB and MRP cells and magnetosomes were measured using Adobe Photoshop software. Gatan Digital Micrograph was used for the calculation of the diffraction pattern and measurement of the crystal lattice. Scatter plots of crystal length and width, the frequency distributions of magnetosome length, width, size (calculated as (length + width)/2), and shape factors (width/length) were conducted using Origin software.

Phylogenetic Analysis

Total DNA was extracted from purified samples using the DNeasy Blood & Tissue Kit (QIAGEN, Germany), and PCR amplification (Mastercycler; Eppendorf, Germany) was undertaken using the universal eukaryote primers EukA (5'-AACCTGGTTGATCCTGCCAGT-3') and EukB (5'-TGATCCTTCTGCAGGTTCACCTAC-3') [START_REF] Medlin | The characterization of enzymatically amplified eukaryotic 16S-like rRNA-coding regions[END_REF] (Sangon Biotech, Shanghai, China). The PCR reaction conditions described by [START_REF] Wang | Morphology and molecular phylogeny of two new species of Spirostrombidium (Ciliophora, Oligotrichia), with a key to the species of Spirostrombidium[END_REF] were modified as follows: 98°C for 30 s, 18 cycles of 98°C for 10 s, 6952°C touch down for 30 s, and 72°C for 1 min; then 18 cycles of 98°C for 10 s, 51°C for 30 s, and 72°C for 1 min; and a final extension at 72°C for 10 min. The PCR product was purified using TaKaRa MiniBEST Agarose Gel DNA Extraction Kit Ver. 4.0 (TaKaRa, Dalian, China). The purified PCR products were cloned into the pMD18-T vector (TaKaRa, Dalian, China), and transformed into competent E. coli TOP10 cells.

Randomly selected single clones were full-length sequenced by TsingKe Biological Technology (Qingdao, China).

The 18S rRNA gene sequences were analyzed using the BLAST search program on the NCBI website (http://www.ncbi.nlm.nih.gov/BLAST/). Relevant 18S rRNA gene sequences were selected from the NCBI GenBank database for the phylogenetic analyses, and sequences were aligned using the ClustalW algorithm. A phylogenetic tree was constructed using the maximum likelihood method in MEGA 6.0 [START_REF] Tamura | MEGA6: Molecular Evolutionary Genetics Analysis version 6.0[END_REF], with bootstrapping using 1000 replicates.

RESULT

Occurrence of magnetically responsive microorganisms

A large number of MTB and one protist type were observed in the droplets of magnetically purified samples observed using optical microscopy (Fig. 2A1). The protist swam quickly and with rapid forward and reverse movements around the edge of the droplet, rotating around its longitudinal body axis (video S1). The cells were elongate obovate, had an average size of 22.47 ± 1.94 × 10.25 ± 1.70 µm (length × width; n = 7), and were approximately 6.85 ± 0.72 µm thick.

The cytoplasm was colorless and transparent, and contained opaque particles (Fig. 2A2).

Phylogenetic analysis of the ciliate

The 18S rRNA gene was cloned from the magnetically purified ciliates. In total, 50 clones were randomly selected for sequencing, and 26 complete 18S rRNA gene sequences were obtained; these sequences shared at least 99.4% identity and belonged to the same OTU, which was designated clone HQ (GenBank accession number MW082832). Among all 18S rRNA gene sequences in GenBank, the clone HQ sequence showed maximum sequence identities (99.1%, 99.2%, 99.1% and 99.0%) with Uronemella parafilificum (HM236337), Uronemita parabinucleata (KU199245), Uronemella filificum (EF486866) and Uronemella filificum (MH574793), respectively. However, only Uronemella parafilificum (HM236337) showed 100% query coverage to the clone HQ. Phylogenetic analysis based on 18S rRNA gene sequence analysis showed that the ciliate in our study is affiliated to the family Uronematidae. Hence, it is likely that clone HQ belongs to the species Uronemella parafilificum.

Characteristics of magnetosomes in MTB and the ciliate Uronemella parafilificum HQ

Generally, ciliate cells are too thick to be penetrated by the electron beam in transmission electron microscopy. However, ciliate cells are fragile and readily break up when dried on carbon-coated grids, and as a result magnetosome-like particles can be clearly observed. Two types of magnetosome-like particles were evident in the ciliate (Fig. 4A), including: prismatic particles (rectangular elongated, elongated, and slightly elongated) having an average size of 93 ± 25 × 64 ± 20 nm (n = 279, c = 9) (Fig. 5,A1A3); and bullet-shaped particles having an average size of 115 ± 9 × 39 ± 1 nm (n = 2, c = 1) (Fig. 5,A4). In the lysed cells on the carbon films the magnetosomes were randomly distributed within the cell and were always arranged in chains. Based on sample observation, magnetotactic cocci (Fig. 4B) were dominant MTB in the samples, which also contained small numbers of rod-shaped (Fig. 4C), curved rod, and spiral MTB.

The cell morphologies and magnetosome shapes and arrangements were similar to those of marine MTB previously reported to have been isolated from the same sampling site in Qingdao (Xing et al., 2008). The average cell size of the magnetotactic cocci was 1.89 ± 0.44 µm (n = 70). The magnetosomes in the magnetotactic cocci were arranged in single or multiple chains, or occurred irregularly. The magnetosome shapes included elongated prismatic particles (rectangular elongated, elongated, slightly elongated) having an average size of 85 ± 25 × 58 ± 20 nm (n = 718, c = 44) (Fig. 5,B1B3), and cuboctahedral particles having an average size of 80 ± 14 × 76 ± 11 nm (n = 13, c = 1).

Among the other MTB morphologies (rod-shaped, curved rod, and spirillum) the magnetosomes were arranged in chains and had shapes including elongated prismatic (average size: 90 ± 43 × 56 ± 23 nm; n = 361, c = 21), and bullet-shaped (average size: 105 ± 29 × 49 ± 9 nm; n = 46, c = 3) (Fig. 5,B4). TEM observation revealed that elongated prismatic magnetosomes were often present, while the bullet-shaped forms were occasionally present. Energy dispersive X-ray analysis indicated that the variously-shaped magnetosomes were composed of iron and oxygen (Fig. 5; A5 and B5). Measurement of the crystal lattice and analysis of the electron diffraction pattern showed that the crystals were anisotropic magnetite (Fig. 5; A6, A7, B6, and B7). Statistical analyses were performed comparing the magnetosomes in MTB and U. parafilificum HQ with respect to length, width, shape factor, and size (Fig. 6). The scatter plots generated show that the distributions of magnetosome length, width, and shape factor for U. parafilificum HQ were greater than that for the MTB, but the distributional trends was similar to that of the MTB (Fig. 6: A1, B1, A2, B2). The frequency histograms for length, width, and size were also consistent between U. parafilificum HQ and MTB magnetosomes (Fig. 6: A3A5, B2B5).

DISCUSSION

The species U. parafilificum was first isolated from the top layer of sediment at a muddy site on the Ganghwa tidal flat and named by [START_REF] Gong | Morphological descriptions of new and little-known benthic ciliates from Ganghwa tidal flat, Korea[END_REF]. Morphological comparison showed that the species was present at two sampling sites. In the present study the ciliate U. parafilificum HQ was shown to contain magnetic particles having various shapes. A given magnetotactic organism typically synthesizes only one kind of magnetosome [START_REF] Dieudonné | Magnetosomes: biogenic iron nanoparticles produced by environmental bacteria[END_REF][START_REF] Mann | Ultrastructure, morphology and organization of biogenic magnetite from sockeye salmon, Oncorhynchus nerka: implications for magnetoreception[END_REF]. We found that the magnetosomes in U. parafilificum HQ and in the MTB from the same sampling site were very similar in shape, composition, and crystal size, suggesting that those in the ciliate were obtained by grazing on the MTB. Previous studies have shown that U.marinum Mj (which was collected from Calanque of Méjean, near Marseille is also affiliated to the family Uronematidae), can graze and ingest various types of MTB, and the predation of U. marinum Mj1 was thought to be non-selective [START_REF] Monteil | Accumulation and dissolution of magnetite crystals in a magnetically responsive ciliate[END_REF]. In our study, characteristics of magmetosomes in U. parafilificum HQ were concordant with those in MTB. It seems that the predation of U. parafilificum HQ was not selective either.

Based on previous studies, MRPs share some common properties (Table 1): (1) they can be collected from natural environments using magnets; (2) they show similar magnetotactic behavior to MTB when observed by microscopy; (3) they contain magnetic particles; and (4) most magnetic ciliates can graze on MTB. In the present study the ciliate U. parafilificum HQ was obtained by magnetic collection from the sediment of an intertidal zone. It contained various shaped magnetic particles that were probably derived from grazing on MTB. However, typical magnetotaxis was difficult to observe in U. parafilificum HQ. Although numbers varied, based on our observations no more than 200 magnetosomes were present in U. parafilificum HQ cells, and there was variability in the orientation of the magnetosome chains within the cells (Fig. 4A). An average of 14 272 magnetosomes acquired from grazed MTB were present in each cell of U. marinum Mj1, which showed obvious magnetotaxis and a rapid response to magnetic field inversion; the arrangement of most magnetosome chains was also apparently along the long axis of this ciliate [START_REF] Monteil | Accumulation and dissolution of magnetite crystals in a magnetically responsive ciliate[END_REF]. Quantitatively, U. marinum Mj1 has > 700-fold the number of magnetosomes in U. parafilificum HQ, even though their body sizes are almost the same. By contrast, in a feeding experiment the large ciliate Euplotes vannus (78 × 53 µm) did not respond to changes in the magnetic field about 30 min after it had ingested MMPs [START_REF] Martins | Grazing protozoa and magnetosome dissolution in magnetotactic bacteria[END_REF] it was estimated that there were thousands of magnetosomes from MMPs in each E. vannus cell.

Thus, it may be that the magnetic response of ciliates when exposed to an applied magnetic field depends on the degree of accumulation of magnetosomes, and the arrangement of the magnetosome chains within each cell. The time taken for food particles to pass through a ciliate cell differs among species [START_REF] Bernard | Bacteria or microflagellates as a major food source for marine ciliates: possible implications for the microzooplankton[END_REF][START_REF] Dolan | Processing of ingested matter in Strombidium sulcatum, a marine ciliate (Oligotrichida)[END_REF][START_REF] Rassoulzadegan | Partitioning of the food ration of marine ciliates between pico-and nanoplankton[END_REF]. We found dissolved magnetosomes in ciliate cells (Fig. S1), and that the proportion of small particles (length < 30 nm) in ciliates (1.07%) was lower than in MTB (1.49%). This suggested that U. parafilificum HQ may have a digestion rate that is sufficiently fast to prevent a large number of magnetosomes from accumulating in its body. Video S1 shows that U. parafilificum HQ moved very rapidly in the hanging drop, and it may be that the rapid motion overwhelmed the weak magnetotaxis, making this phenomenon difficult to observe. Or, perhaps, its movement is fast enough for this type of ciliate to find sufficient food and a suitable habitat without help of magnetotaxis. Hence, the absence of a sufficient number of magnetosomes, fast digestion rate of the magnetosomes, and the disordered arrangement of magnetosome chains in U. parafilificum HQ may have resulted in it not showing any observable response to magnetic field changes. Based on morphological observations and 18S rRNA sequence analysis, we identified the species U. parafilificum HQ forming a population of benthic ciliates collected from intertidal sediments of Huiquan Bay (Qingdao, China). Uronemella parafilificum HQ was capable of grazing various types of MTB. Statistical analysis of the magnetosomes in U. parafilificum HQ cells and MTB from the same site suggested that the predation of U. parafilificum HQ appeared to be non-selective. The results add to knowledge of the broad diversity and wide distribution of MRPs, and provide opportunities for researching the mechanism of magnetoreception in eukaryotes.

DATA TRANSFER STATEMENT

The datasets generated and/or analyzed during the current study are available from the corresponding author on reasonable request.

Fig. 1

 1 Fig.1 Schematic diagram of the purification method.

Fig. 2

 2 Fig.2 Light microscope images of magnetotactic bacteria and ciliates. A1: co-occurrence of magnetotactic

Fig. 3

 3 Fig.3 Maximum Likelihood tree for Uronemella parafilificum HQ based on 18S rRNA gene sequences. The

Fig. 4

 4 Fig.4 Transmission electron microscopy images of magnetotactic bacteria and ciliates. A: Uronemella

Fig. 5

 5 Fig.5 Characteristics of the magnetosomes in Uronemella parafilificum HQ and magnetotactic bacteria from

Fig. 6

 6 Fig.6 Comparison of the characteristics of magnetosomes in MTB and U. parafilificum HQ. A1, B1: Dot

Table 1 .

 1 Characteristics of various MRPs

	Typical magnetotactic
	Magnetic collection
	motion

ACKNOWLEDGEMENT

We thank Tang Xu, Liu Peiyu, and Liu Yan in the Electron Microscopy Laboratory, Institute of Geology and Geophysics, Chinese Academy of Sciences (EML, IGGCAS), for their efforts to maintain operation in TEM experiments.

* Supported by the National Natural Science Foundation of China (Nos. 41776130 & 41776131) and the National Natural Science Foundation of China-Shandong Joint Fund for Marine Science Research Centers (U1706208).

Electronic supplementary material

Supplementary material (Supplementary Video 1, Supplementary Fig. 1) is available in the online version of this article at https://