R Ologeanu-Taddei

D Morquin

C Vitari

Perceptions of an Electronic Medical Record (EMR): lessons from a French longitudinal survey

Keywords: Hospital, Clinical Information Systems, Electronic Medical Records, Ease of Use

The goal of this longitudinal study is to examine the evolution of the perceptions, namely anxiety, ease of use, usefulness, misfit (not customization), trust and usefulness, related to an Electronic Medical Record (EMR) for the clinical staff in a French Teaching hospital. Two surveys were conducted first in September 2013 and second in December 2015, based on a questionnaire consisting of items on the Likert scale. As results, the correlation of all the variables between the two surveys is very significant (except for usefulness, for which the relationship is significant). This is not surprising, given previous studied focused on habits and learning related to technology adoption. Nevertheless, the increase is not spectacular and it makes necessary to evaluate EMR satisfaction and perceptions in order to elaborate a measure standard enabling comparisons and benchmarking among hospitals.

Introduction

Electronic Medical Records (EMR) are electronic records of patient health information that include progress notes, problems, medication, vital signs, past medical history, immunizations, laboratory data and radiology reports [START_REF] Xiao | Meaningful Use" of ambulatory EMR: Does it improve the quality and efficiency of health care?[END_REF]. In hospitals, EMR are intended to facilitate the sharing and storage of medical information across departments. EMR were implemented in most health organizations in several countries in order to improve quality of health, enhance patients' safety and improve efficiency [START_REF] Bates | Reducing the frequency of errors in medicine using information technology[END_REF]. Fulfilling these promises needs proactive uses and EMR adoption for clinical staff. Nevertheless, physicians' and nurses' perceptions regarding ease of use and usability of EMR is generally very low [START_REF] Gadd | Assessing physician attitudes regarding use of an outpatient EMR: a longitudinal, multi-practice study[END_REF]Penrod 2001, Rahimi, Timpka et al. 2009). Several studies highlighted usability and ease of use problems related to EMR satisfaction [START_REF] Gadd | Assessing physician attitudes regarding use of an outpatient EMR: a longitudinal, multi-practice study[END_REF]Penrod 2001, Khajouei, Wierenga et al. 2011). This issue may be related to innovation process and time needed for improving experience and creating new habits [START_REF] Ammenwerth | Evaluation of health information systems-problems and challenges[END_REF]. Nevertheless, this is a postulate and not proven evidence about if and how the satisfaction levels reflect the newness of the technology and the learning effects associated with mastering the new technology [START_REF] Vishwanath | The impact of electronic medical record systems on outpatient workflows: a longitudinal evaluation of its workflow effects[END_REF]. Poissant et al. found that almost all longitudinal studies since 1984 focused on evaluations at only one point in time after implementation [START_REF] Poissant | The impact of electronic health records on time efficiency of physicians and nurses: a systematic review[END_REF]. Hence, little research was provided about EMR evolutions of physicians' satisfaction over time. Moreover, these longitudinal studies use broad thumb rules of 3 months-1 year as arbitrary limits [START_REF] Vishwanath | The impact of electronic medical record systems on outpatient workflows: a longitudinal evaluation of its workflow effects[END_REF]. [START_REF] Vishwanath | The impact of electronic medical record systems on outpatient workflows: a longitudinal evaluation of its workflow effects[END_REF] provided a recent longitudinal studies on EMR effects over time. The aim was to track physician satisfaction levels 3 months and 20 months after the stage of the EMR implementation. As a result, authors stated a significant difference between preimplementation expectations and satisfaction levels 3 months after this stage. In all cases, satisfactions levels The goal of our study is to compare perceptions of an EMR by clinical staff in a French hospital during the postimplementation stage.

In the first section we will present the theoretical framework used for the study. In the second section we will describe the methodology design. The third section will present main findings, which will be discussed in the last section.

Theoretical framework

Literature on implementation of information technologies has highlighted the importance of users' attitudes and satisfaction related to these technologies. The technology acceptance model (TAM) is a theoretical model commonly used for predicting and explaining user behavior and IT usage (Davis 1989, Holden and[START_REF] Holden | The technology acceptance model: its past and its future in health care[END_REF]. Nevertheless, several criticisms have been made to the TAM, such as follows:

• Parsimony concerning categories and their too generic definitions [START_REF] Bagozzi | The Legacy of the Technology Acceptance Model and a Proposal for a Paradigm Shift[END_REF]) and fuzzy extensions of TAM concepts that impede comparisons [START_REF] Benbasat | Quo vadis TAM?[END_REF].

• TAM is based on binary variables and it was studied especially in connection with simple technologies. More generally, adoption is envisaged as a binary mode: an individual uses or uses not the technology. However, complex information systems, including Enterprise Resource Planning (ERP), give rise to more or less advanced uses. Some functionalities may be used, while others not.

• TAM was designed and principally used to evaluate the intention to use in voluntary contexts, but the ERP uses are mandatory in organizations.

For these reasons, we believe that TAM is not suitable for understanding the HIS acceptance specifically in a context where its use is mandatory.

Nevertheless, we do believe that the key concepts of the model are relevant to assess users' perceptions and we propose to gather quantitative measures of these items. Previous research pointed out main factors adoption decision or users' satisfaction: ease of use, usefulness [START_REF] Venkatesh | Technology acceptance model 3 and a research agenda on interventions[END_REF], anxiety, perceived behavioral control., which is defined as "one's belief in his or her ability to execute a particular task/job using a computer the degree to which an individual believes that an organizational and technical infrastructure exists to support use of the system" [START_REF] Venkatesh | Technology acceptance model 3 and a research agenda on interventions[END_REF], system quality, information quality, service quality [START_REF] Petter | Measuring information systems success: models, dimensions, measures, and interrelationships[END_REF]) and trust [START_REF] Cho | A study of the roles of trusts and risks in information-oriented online legal services using an integrated model[END_REF]. Furthermore, customization or fit to clinical workflows is considered a key issue for adoption of EMR in healthcare (Vishwanath, Singh et al. 2010, Cresswell and[START_REF] Cresswell | Organizational issues in the implementation and adoption of health information technology innovations: an interpretative review[END_REF].

Nevertheless, little research was made on the influence of time on perceptions and attitudes evolution. Venkatesh & Davis [START_REF] Venkatesh | A theoretical extension of the technology acceptance model: Four longitudinal field studies[END_REF] provided an analysis focused on the cross-temporal correlations of intention of use and its direct determinants. They found that individuals relied less on social information in forming perceived usefulness and intention but continued to assess a system's usefulness on the basis of potential benefits resulting from use (job relevance, performance benefits). It seems that a consensus has emerged regarding the key issue of time for shaping new habits and adoption of innovation including EMRs [START_REF] Ammenwerth | Evaluation of health information systems-problems and challenges[END_REF].

Given this background, it may be expected that EMR assessments will increase over time. Consequently, we will measure correlations between EMR perceptions in the post-implementation stage.

Research method and design

Context

The study was conducted in a French Teaching Hospital that has more than 2500 beds and covers all the clinical specialties and an Emergency department. The EMR was implemented in 2012 according to a "big bang" strategy, in order to support all the departments and specialties in 9 months. This EMR incorporates computerized physicians order entry, medical and nursing observation, laboratory tests results, medical prescription, operating room process management, planning and billing management. It is a fully integrated system consisting of different modules as admission, discharge and transfer, computerized provider order entry, treatment planning (nursing and medication administration), resources and appointment scheduling system, clinical data warehouse (CDW). Results from Author name / Procedia Computer Science 00 (2016) 000-000 ancillary subsystems (e.g., laboratories, imaging, and pharmacy) are automatically integrated into the EMR as pdf. files.

The aim of the study was to measure clinical staff perceptions related to EMR, namely information and system quality (security and liability), ease of use, not customization (to the clinical process and needs), self-efficacy, anxiety and usefulness. We made the choice to investigate perceptions for all the clinical staff (including physicians, surgeons, anesthesiologists, nurses, nurse managers, medical secretaries) because they are all implied in the clinical process (medication prescription and administration, treatment sheet, vital signs). We have to mention that the intensity of use of the EMR is not an important issue because all the medical examinations and medical histories of patients, prescriptions, planning schedule for patients and administrative documents has to be documented in the EMR. Thus, all clinical staff has to notify or to use information notified by others in their daily workflow. Nevertheless, this process may be more or less optimized, according to the workflow, EMR knowledge and habits of every clinical team or individual. For example, some physicians document the information related to their patients on papers sheets before entering this information on the EMR. Some physicians dictate the conclusions of the medical examinations directly in EMR by using a speech-to-text software while the records of other physicians are taped by medical secretaries.

Method

A survey was administrated to clinical staff first in December 2013 and second September 2015, consisting in an online questionnaire. The level of 21 months was not decided at the beginning of the assessment process but was empirically decided in relation with the hospital top management agenda, which considered that the second survey might be administrated several months after a change of EMR version and exclude summer holydays.

We collected 1942 answers for the first questionnaire and 1292 for the second one, for a population of 6443 clinical employees. The final representative sample was composed of 290 answers for each questionnaire. Each variable is measured using a question derived from a review of previous studies, adapted from different scales [START_REF] Morris | Age differences in technology adoption decisions: Implications for a changing work force[END_REF][START_REF] Chau | Investigating healthcare professionals' decisions to accept telemedicine technology: an empirical test of competing theories[END_REF][START_REF] Wixom | A theoretical integration of user satisfaction and technology acceptance[END_REF][START_REF] Petter | Measuring information systems success: models, dimensions, measures, and interrelationships[END_REF][START_REF] Holden | The technology acceptance model: its past and its future in health care[END_REF][START_REF] Chen | An investigation on physicians' acceptance of hospital information systems: a case study[END_REF] and each question was answered using a seven-point Likert scale, with one indicating "strongly disagree" and seven indicating "strongly agree."

We decided to use a representative sample that was shaped after responses, by stratification, in order to adequately replicate the larger group according to characteristics (occupations stratus) of the hospital population (table 1). For a better understanding of the EMR context and local setting, we conducted four interviews (in 2013 and in 2015) with the two physicians involved in the EMR evolution and customization and additional data were collected by internal reports.

Results

To evaluate how clinical staff perceptions expectations changed overtime, a correlation analyze was conducted for the first and the second questionnaire. We found that age has an impact on perceived anxiety, self-efficacy, ease of use, trust, not customization, trust and usefulness. The relationship is very significant for the first five variables and significant for the sixth one.

The results are summarized in the table 2

Discussion

A rapid view of these results shows time has an impact of perceptions. Anxiety, self-efficacy, ease of use and trust increase overtime for all clinicians, while non customization perception of EMR to clinical workflow decreases. Thus, it is possible to consider an experience and learning effect [START_REF] Vishwanath | The impact of electronic medical record systems on outpatient workflows: a longitudinal evaluation of its workflow effects[END_REF]) on EMR perceptions. We have to mention that between 2013 and 2015 several actions were made in the hospital specifically training programs for all the clinical staff and customization of EMR forms for medical departments and occupations.

First of these actions is a new version of the EMR, which was implemented in July 2014. The second action is related to the development of an e-learning platform for prescribing, since September 2014, which is mandatory for residents. The third action consists on the continuous customization of EMR. More precisely, two physicians were mandated by the top management of the hospital to customize and adapt the EMR (for different medical departments and specialties) and they have trained several physicians in order to enable them to configure templates for their departments. This customization was made in collaboration with the Information Systems Department. The total work of technical customization by physicians and computer specialists was assessed as 2260 hours in 2013, 2812 hours in 2014 and 2083 in 2015, not including time spent by the mandated physicians to explain possibilities of configuration and to provide help to define and refine specific needs for medical specialists, what is the technical process used to customize specific EMR views or favorites and to automate outpatients referral letters and requests.

Author name / Procedia Computer Science 00 (2016) 000-000 The physicians of the hospital are very interested in automating requests, as requests related to patients, which enable physicians to discuss particular and complex cases during multidisciplinary team meetings, or requests related to health issues to drive outcomes for epidemiology supervision and research. Both physicians involved in the customization of EMR are also mediators that help every physician, which ask for, to explain his/her needs and objectives, allowing them to suggest specific forms. Once they have agreed about the form design with the applicant, they transfer the request to computer specialists of the Information Systems Department for technical configuration and to request access to administrator modules, to allow the applicant to set up and modify the specific form he or she has asked for.

The forth action has focused on the indexation of folders and files in EMR. Since 2013, a specific committee, including physicians, medical secretaries, information systems engineer or technicians and medical informatics specialists, has organized regular meetings to simplify and facilitate readability of the EMR architecture. This action was is direct response to the lack of readability that was main issue of the first survey [START_REF] Ologeanu-Taddei | Understanding the acceptance factors of an Hospital Information System: evidence from a French University Hospital[END_REF].

Besides, all changes between 2013 and 2015 are not linear and positive. In September 2014, a complete EMR breakdown (without backup) has occurred for 7 hours during the day.

We consider that the evolution of the results is not spectacular. Every variable is better assessed but, generally, EMR is not considered easy of use and clinicians do not state great self-efficacy. This assumption raises the question of the EMR assessment and barometer: how and when could we consider that EMR is a success for clinicians? Ease of use and self-efficacy do they have to be evaluated at 4, 5 or 6 on the Likert scale? For example, Hadj et al. [START_REF] Hadji | 14 Years longitudinal evaluation of clinical information systems acceptance: The HEGP case[END_REF]) considered that the assessment of 4.9 of global satisfaction means a success for a clinical information system. This is a subjective interpretation and more studies are needed in order to have comparisons and benchmarking.

Our results have to be related also to differences of perceptions among clinical occupations in the same hospital. In a previous paper we showed a very significant correlation of perceived ease of use, usefulness and self-efficacy with occupations. Anesthesiologists, physicians and surgeons report the lower rate of ease of use and usefulness [START_REF] Ologeanu-Taddei | Understanding the acceptance factors of an Hospital Information System: evidence from a French University Hospital[END_REF]. We suggested that this finding could be explained by the medical responsibility related to prescribing.

We think that more efforts have to be done by hospitals managers on these issues. This means that change management, organizational support and training programs have to be continuous even in post-implementation stage. EMR have to be consider as a work tool, and efforts must be done by hospitals in order to make the technology more workable [START_REF] Markus | Technochange management: using IT to drive organizational change[END_REF]. Use of EMR is not intuitive [START_REF] Ologeanu-Taddei | Understanding the acceptance factors of an Hospital Information System: evidence from a French University Hospital[END_REF] and requires learning and developing skills related to particular clinical process of medical specialties.

Conclusion

Research has recently started to assess clinical information systems as EMR taking into account users' perceptions, acceptance and satisfaction. While this studies are generally conducted at a specific time, our study provides evidence related to a longitudinal survey (on 21 months) in order to assess a significant increase of clinicians' self-efficacy, anxiety, trust, ease of use, usefulness and misfit (not customization) perception. Contrary to previous studies, we assess our results on a representative sample.

The level of 21 months can be discussed because it was not decided on scientific arguments but related to the top management agenda.

Nevertheless, the EMR evolution (e.g. changes of versions), training programs and organizational support in order to customize EMR forms do not allow us to conclude if the results are related to (only) an experience curve. Furthermore, we highlight the importance of defining objective for EMR assessment and users' satisfaction.

Table 1 .

 1 Population, Answers to questionnaires and representative sample.

	Professional categories	Population	Answers	Answers	Rate Q1	Rate Q2	Stratus
			Q1	Q2
	Caregivers	1740	103	78	5,92%	4,48%	78
	Anesthesiologists	131	73	28	55,73%	21,37%	6
	Social assistants	59	32	45	54,24%	76,27%	3
	Care managers	250	79	56	31,60%	22,40%	11
	Surgeons	172	56	35	32,56%	20,35%	8
	Dentists	71	9	5	12,68%	7,04%	3
	Nurses	2014	656	426	32,57%	21,15%	90

Table 2 .

 2 Variables results.

	Variable	Significance	Quest1	Quest2	Quest1	Quest2	Total	Total
		level	Mean	Mean	SD	SD	Average	SD
	Anxiety	<0.001	3,57	3,44	2,158	1,866	3,51	2,017
	Not	<0.001	4,29	3,9	2,27	1,983	4,09	2,138
	Customization
	(Misfit)
	Self-efficacy	<0.001	3,37	3,66	2,267	1,953	3,52	2,12
	Usefulness	<0.01	4,09	4,49	1,902	1,637	4,29	1,785
	Ease of use	<0.001	2,88	3,66	1,922	1,76	3,27	1,883
	Trust	<0.001	3,5	4,31	2,035	1,663	3,91	1,901


R Ologeanu-Taddei

C Vitari

D Morquin Ab

What could we learn from the influence of age on perceptions of a CIS by the clinical staff of a French hospital ?

Keywords: Hospital, Clinical Information Systems, Electronic Medical Records, Perceptions, Ease of Use, Clinical process

The goal of this study was to examine the relationship between age and perceptions of a Clinical Information System (CIS). A survey was conducted in September 2015 in a French Teaching Hospital, based on a questionnaire consisting of items on the Likert scale. As results, the impact of age is inversely proportional to Perceived Ease of Use and Perceived Behavioral Control. These results are not consistent with literature. We propose an explanation consisting in the importance of clinical process and organization knowledge and skills while general technology skills of young generations may be less significant.

Introduction

In recent years, a significant amount of research has been conducted on comparing the level of technology adoption between younger and older age employees. A recent trend of research is focused on generational differences [START_REF] Wey Smola | Generational differences: revisiting generational work values for the new millennium[END_REF] and gap attitudes to technology between different generations. Generation is defined as groups, which are identifiable in terms of year of birth, age, location, and significant events at critical developmental stages [START_REF] Kupperschmidt | Multigeneration employees: strategies for effective management[END_REF]. Currently mains authors consider Generation Z [START_REF] Prensky | Digital natives, digital immigrants part 1[END_REF], named also Digital Natives or Millennial Generation (born after [1985][1986][1987][1988][1989][1990] as having more "sophisticated technological skills" [START_REF] Margaryan | Are digital natives a myth or reality? University students' use of digital technologies[END_REF]) which should transform the use of new technologies in the workforce.

Nevertheless, research pointed out that the generation is not homogeneous in its use and appreciation of new technologies [START_REF] Jones | Net generation or Digital Natives: Is there a distinct new generation entering university?[END_REF]. Furthermore, literature has not come to identify if differences in technology skills and forms of technologies uses are related to generation or age effect.

Another trend of research is focused on the age effect on technology adoption level. Authors highlighted age differences in information processing have an impact on older workers' performance of computer-based tasks (e.g., data entry, file maintenance, and inventory management) [START_REF] Sharit | Ageing, computer-based task performance, and stress: issues and challenges[END_REF]. The longitudinal study conducted by [START_REF] Morris | Age differences in technology adoption decisions: Implications for a changing work force[END_REF] showed age has important influences on technology adoption and sustained usage decisions. Specifically, younger workers appear to be more driven by a cost and benefices evaluation of the use of technology whereas older workers are more motivated by social norm and the perception of their competency to use the technology. Authors suggest this difference may be related to generation effect taking into account that workers were familiarized with information technologies during their scholarship. Consequently, young workers may be more reliant on the use of technology for job accomplishment while older workers may be much more habituated to seeking and applying "un-technological" solutions to job-related tasks.

Generally, older workers have a more difficult time adapting to changes in the work environment and would prefer methods that are familiar to them [START_REF] Sharit | Ageing, computer-based task performance, and stress: issues and challenges[END_REF]). An older staff is negatively related to the probability of introducing new or significantly improved technologies [START_REF] Meyer | Workforce age and technology adoption in small and medium-sized service firms[END_REF].

Given this background, it may be expected that age factor influences clinical use and adoption of a Clinical Information System (CIS). Nevertheless, little or any evidence is offered to support this relationship. The aim of this paper is to measure the link between age and perceptions of the CIS in a French teaching hospital.

Theoretical framework

Research focused on technology adoption or on Information Systems evaluation by users identified main factors adoption decision or users' satisfaction: ease of use, usefulness [START_REF] Davis | Perceived usefulness, perceived ease of use, and user acceptance of information technology[END_REF], perceived behavioral control [START_REF] Venkatesh | User acceptance of information technology: Toward a unified view[END_REF], anxiety (Venkatesh & Bala, 2003), system quality, information quality, service quality [START_REF] Petter | Measuring information systems success: models, dimensions, measures, and interrelationships[END_REF]) and trust (Cho, V. A study of the roles of trusts and risks in information-oriented online legal services using an integrated model. Information & Management, 43, 4 (2006), 502-520.). Ease of use and customization are main indicators of system quality [START_REF] Petter | Measuring information systems success: models, dimensions, measures, and interrelationships[END_REF]. System quality represents the desirable characteristics of an information system, as ease of use, flexibility, system reliability, and ease of learning, as well as system features of intuitiveness, sophistication, flexibility, and response times (Petter, De-Lone et al. 2008). Thus, ease of use is one dimension of system quality. Information quality is shaped by four dimensions: completeness as the degree to which the system provides all necessary information; accuracy, meaning the user's perception that the information is correct, format, meaning the user's perception of how well the information is presented, and currency or timeliness, representing the user's perception of the degree to which the information is up to date [START_REF] Wixom | A theoretical integration of user satisfaction and technology acceptance[END_REF].

Self-efficacy refers to the extent to which individuals feel able to complete specific tasks using an information system [START_REF] Venkatesh | User acceptance of information technology: Toward a unified view[END_REF].

Research method and design

Context

Our investigation was conducted in September 2015 in a large French University hospital. The target was composed by the care staff (6 000 employees), including anesthesiologists, physicians, surgeons, medical secretaries, nurses, auxiliary nurses, midwives, residents, physiotherapists, social workers, pharmacists. The aim was to measure the link between age and the users' perceptions related to CIS of the hospital, namely information and system quality (security and liability), ease of use, customization, behavioral control, anxiety, trust and usefulness..

The CIS incorporates computerized physicians order entry, medical and nursing observation, laboratory tests results, medical prescription, operating room process management, planning and billing management.

Method

A questionnaire was developed and administered online to the care staff. 1292 questionnaires were collected, which means a response rate of 19%. Each variable is measured using a question derived from a review of previous studies, adapted from different scales [START_REF] Morris | Age differences in technology adoption decisions: Implications for a changing work force[END_REF][START_REF] Chau | Investigating healthcare professionals' decisions to accept telemedicine technology: an empirical test of competing theories[END_REF][START_REF] Wixom | A theoretical integration of user satisfaction and technology acceptance[END_REF][START_REF] Petter | Measuring information systems success: models, dimensions, measures, and interrelationships[END_REF][START_REF] Holden | The technology acceptance model: its past and its future in health care[END_REF][START_REF] Chen | An investigation on physicians' acceptance of hospital information systems: a case study[END_REF], and each question was answered using a seven-point Likert scale, with one indicating "strongly disagree" and seven indicating "strongly agree." Age is measured through 4 ordinal categories: less than 35, 35-45, 45-55, more than 55 years old. We applied the Kruskal Walls test to assess if age has an impact on the information systems variables.

We have to specify that these categories are very closely of professional status categories because the age of residents is less than 35 while permanent employment is in general more than 35. For the clinical staff, median age is 45.

Results

We found that age has an impact on perceived information and system quality, customization, anxiety, ease of use, behavioral control. Nevertheless, age has no influence on trust and perceived usefulness. These results are summarized in the

Discussion

A rapid view of these results shows age has an effect on different perceptions of the CIS. But, surprisingly, the relationship is not the same as expected. The impact of age factor is very strong on Perceived Ease of Use and Perceived Behavioral Control, but age is inversely proportional to Perceived Ease of Use. The growth of these relationships is continuous over the 4 age categories. This means younger staff reported to be less comfortable with technology than orders. These results may be explained by the fact that using CIS is not intuitive (Ologeanu-Taddei, Morquin, AMIA) and requires learning and developing skills related to particular clinical process of medical specialties. Other explanation may be focused on the gap between younger staff' habits to use intuitive and ludic applications, which contrast with CIS ergonomics. Furthermore, older staff reported more facilities to contact CIS support if they need to. Thus, the lack of sufficient clinical and organizational knowledge of younger staff predominate over general technology skills.

The impact of age is also very strong for Anxiety, but this relationship is not continuous. There are the middle categories (35-45 years and 45-55 years) that reported the higher rate of anxiety. Moreover, younger staff reported less anxiety. Both results may be explained by the fact that middle categories are more concerned by care management and different responsibility and monitoring tacks (as medical responsibility for physicians seniors while residents fulfill hospital a patient's discharge). For medical tasks, residents, which belong to the first category of age, are supervised by seniors.

The impact of age is little on Information and System Quality. This relationship is continuous. It may be correlated to the impact of age on Perceived Ease of Use. Thus, younger staff stated less Perceived ease of Use and Less Information and System Quality (perceived information security). The impact of age is also little on Customization, but there are the middle categories that reported less perceived customization. This result may be explained but the greater medical and organizational knowledge and responsibilities of these categories and, consequently, the gap between their representation of clinical process and the configuration of clinical process by CIS.

Last, the impact of age is not significant on Usefulness neither Trust. These mixed results do not confirm previous studies on age impact on technology use. First, the specificity of clinical process, by occupations and specialties, seems to be more important than general technological skills (Ologeanu-Taddei, Morquin, AMIA). More in-depth research is needed to explore the link between clinical specialties (e.g. Pediatrics, Gerontology) and CIS perceptions. Second, age has not the same effect on different variables. Perceived Behavioral Control, Ease of Use and Anxiety seem to be more discriminant than other variables.

Conclusion

While literature pointed out generation and age effects on technology perceptions and attitudes, related to younger people technological skills, our study showed that age does have an effect of Perceived Behavioral Control and Ease of Use but indirectly proportional. In other words, younger staff reported less Perceived Behavioral Control and Ease of Use, probably because they have less knowledge about clinical and organizational process. Other perceptions related to CIS are less or not at all correlated with age. We conclude that age factor is not the most relevant for the analysis of CIS perceptions.

table below :

 below

		Significance
		level	Average (on Likert scale) for	Total
				the different ages		Average
		* =<0,05
		**=<0,01		35-	45-	>
	Item	***=<0,001 <35	45	55	55
	Perceived Behavioral
	control	***	3,44	3,71	3,98	4,33	3,79
	Anxiety	***	3,17	3,73	3,63	3,41	3,49
	Ease of use	***	2,85	3,32	3,57	3,33	3,25
	Customization	*	3,57	3,89	3,97	3,78	3,8
	Information and system
	quality	*	4,45	4,49	4,65	4,88	4,57
	Usefulness	Not significant
	Trust	Not significant


S Lecommandoux

O Sandre

F Chécot

J Rodriguez-Hernandez

R Perzynski
email: regine.perzynski@sorbonne-universite.fr

Self-assemblies of magnetic nanoparticles and di-block copolymers : magnetic micelles and vesicles

Keywords: Colloids, nano-composites, block copolymers, ferrofluids, self-assembly

Magnetic nano-composites are obtained by the self-assembly in water of polypeptide based diblock copolymers polybutadiene-b-poly(glutamic acid) combined with hydrophobic γ-Fe 2 O 3 nanoparticles. These hybrid supramolecular objects are either -(3-d) spherical micelles filled with a hydrophobic ferrofluid at a concentration as high as 45 vol % or -hollow vesicles with a (2-d) magnetic membrane. In this last case the organic amphiphilic copolymers are able to confine the hydrophobic nanoparticles within the thin layer of PB blocks. We probe these objects by AFM, by Small Angle Neutron Scattering (SANS) and by ligth scattering. Furthermore, anisotropic SANS data bring the experimental evidence of the capability to modify the shape of the mineralized membranes in response to a magnetic field intensity as low as 290 G .

Introduction

To introduce inorganic nano-objects in self-organized structures of amphiphile molecules is still a challenge for physico-chemists, even if such hybrids are oftenly encountered in Nature. For example, calcium carbonates [1] and iron oxides [2,3] are colloidal particles commonly observed in organisms where they are often confined in vesicles. In addition to the biomimetic aspect of this kind of structures, the formation of hybrids constituted of nanoscale inorganic compounds dispersed in a selfassembled organic structure may lead to smart materials with specific properties brought by the inorganic nanomaterial. The challenge is here to introduce magnetic nanoparticles in self-assemblies of di-block copolymers in order to generate new supramolecular structures sensitive to an applied magnetic field. If these supramolecular objects are also able to respond to stimuli such as pH and ionic strength due to the presence of some polypeptide block, they form what can be called multi-responsive nanocapsules. These superparamagnetic self-assembled hybrids may offer attractive potentialities in biomedicine and biotechnology due to their dimensions (0.1 -0.5 µm) small enough to stay for some time in the blood circulation. Because of the properties brought by the iron oxide nanoparticles, a manipulation by an external magnetic field gradient, a local heating by a radio-frequency field for cancer radio-therapy, a labeling of organs to enhance the contrast in Magnetic Resonant Imaging become possible.

A novel type of hybrid colloids, based on the association of several polymeric systems and ferrofluids is presented here [4]. We use inorganic nanoparticles made of a magnetic iron oxide that respond to a magnetic field of low intensity. The organic part is made of mesoscopic structures (micelles or vesicles) self-assembled from amphiphilic polybutadiene-block-poly(glutamic acid) (PBb-PGA) diblock coplymers. These PB-b-PGA copolymers bearing a rod-coil structure with a cross-linkable hydrophobic block and a hydrophilic peptidic block have been synthesized recently [5]. Due to a helix-coil transition of the PGA block, such peptosomes behave as stimuliresponsive capsules; they respond to a pH change by a variation of their hydrodynamic diameter as large as 50% [5,6,7]. The magnetic nanoparticles come from colloidal suspensions of nanometric magnetic grains made of maghemite (γ-Fe 2 O 3 ) and stabilized either by electrostatic charges in aqueous media [8] or by appropriate tensioactives in organic solvents [9]. Performing smallangle neutron scattering (SANS) experiments in LLB-CEA Saclay-France on PACE and PAXY spectrometers, we use these inorganic nanoparticles, embedded in supramolecular objects formed by diblock copolymers, as structural probes of the hybrid objects. Benefiting from the strong contrast of iron oxide with respect to the polymer and the solvent, we measure the structure factor S intra (q) of the nanoparticles inside the objects. The shape of S intra (q) reflects the interactions between the nanoparticles inside the object [10]. In addition at low scattering vectors q, S intra (q) can be associated to the global form factor P(q) of the object that they decorate [11,12]. The synthesized objects are also probed by static (SLS) and dynamic (DLS) light scattering and by AFM.

Magnetic micelles

We obtain the magnetic micelles mixing in water (or in a mixture of The dispersions of the synthesized objects are stable in time. Combined with one mass equivalent of ferrofluid, both di-block copolymers give rise to fully dispersed suspensions. Figure 1 shows the structure factor S intra (q) of the nanoparticles inside the synthesized objects as obtained by SANS (the solvent is contrast matched to polymer) and SLS. At intermediate scattering vectors q, S intra (q) ∝ q -4 it expresses that the nanoparticles are densely packed inside the hybrid objects. The SLS measurements lead to a radius of gyration R g of the objects of the order of 100 nm. It is smaller than (half of) the hydrodynamic diameter d H (determined by DLS) which ranges between 225 to 430 nm. There is a several-fold increase of hydrodynamic diameter with respect to unloaded micelles obtained without adding any ferrofluid (d H ≈ 60 to 70 nm). It means that the presence of the nanoparticles significantly modifies the self-assembly of di-blocks. The ratio 2R g /d H of the hydrid objects is found between 0.6 and 0.8. It is close to the hard sphere value (3/5) 0.5 ≈ 0.77. Moreover S intra (q) presents a correlation bump around 8 10 -2 Å -1 (see figure 1) which is associated to a most probable interparticle distance d max ≈ 8 nm and a volume fraction of the order of 45%. This high encapsulation yield, together with the global three dimensional shape of the objects is confirmed by AFM images (see figure 2). The nanoparticles appear densely packed and confined in thick bags of lateral extension comparable to the diameter d H determined by DLS.

We conclude that we obtain 3D-micelles bulky loaded with nanoparticles with a number of particles per micelle that can be evaluated to a few 10 4 . It is two orders of magnitude larger than in aggregates of magnetic nanoparticles obtained by the addition of coagulating homopolymers [13,[START_REF] Kharrat | AIP Conf. Proc[END_REF] or of other self-assembling diblock copolymers [START_REF] Kiselev | [END_REF].

Magnetic vesicles in zero field

We obtain the magnetic vesicles mixing in water (or in a mixture of H 2 O/D 2 O) PB 48 -b-PGA 56 di-block copolymers with the previous ferofluid in dichloromethane. The structure factor of the hybrid objects is presented in figure 3. In the low q regime, S intra (q) approximately follows a power law q -2 , which is completely different from the q -4 behavior of figure 1. This q -2 regime could be associated to 3D aggregation of the nanoparticles under DLA or RLA processes. However AFM pictures (inset of figure 3 and figure 4) do not correspond to such a fractal cluster formation [16] nor to clusters induced by other (co)polymers [START_REF] Kharrat | AIP Conf. Proc[END_REF]17,18]. We observe closed loops around a central hole looking like pieces of lace. These holey shapes are reproducible (see inset of figure 3). Presumably, because of the strong adhesion of the softs shells on the freshly cleaved surface of mica, the vesicles open pores. It leads to a ripping of the bilayers and then allows the spreading of the initially curved membranes onto the strongly adhesive substrate.

Moreover here the ratio 2R g /d H is close to 1 which is the theoretical value for a hollow sphere. From the SANS spectra, one can also deduce the thickness δ of the layer of nanoparticles inside the membrane of the vesicle. Using the Kratky-Porod approximation [START_REF] Glatter | Small X-Ray Scattering[END_REF] of the form factor of a flat infinite sheet of thickness δ in this q-region, it comes : ln (q 2 S intra ) ≈ ln (I o )-q 2 δ 2 /12, I o being proportional to the surface area. For one mass equivalent of ferrofluid and in a contrast matched experiment, we get δ = 8.6 nm; in H 2 0 due to an additional contribution of the copolymer, we obtain δ = 10 nm (see further on inset of figure 6). We can conclude that in these conditions the membrane contains at most one layer of magnetic particles. Indeed we can also adjust (see figure 3) S intra (q) at low q to the form factor of vesicles of radius d H /2 and membrane thickness δ. Let us note also that S intra (q) does not present any correlation bump at large q which confirms that the inorganic nanoparticles form, at most, one monolayer inside the polymeric membrane. We conclude that we observe hollow vesicles with a mineralized membrane.

SANS probing of magnetic vesicles under field

To study the response to an applied magnetic field, of vesicles of PB 48 -b-PGA 56 loaded with nanoparticles inside their membrane and to work in (almost) pure nuclear contrast [START_REF] Gazeau | [END_REF], the system is dispersed in light water. When a magnetic field is applied, the scattering pattern becomes clearly anisotropic (see figure 5). In the 3 10 -3 -2 10 -2 Å -1 q-range the lines of iso-intensity are ellipses elongated perpendicularly to the field direction, with aspect ratios increasing up to 1.3 as the field intensity reaches 1050 Oe, almost independently of the value of q. In the SANS window of q which is here explored, the measurements lie far above the Guinier range and give information at the length scale of the membrane thickness. In addition because of the magnetic and nuclear contrasts of the γ-Fe 2 O 3 nanoparticles dispersed in ligth water, the anisotropy of the pattern cannot be due to their magnetic scattering and is of nuclear origin [START_REF] Gazeau | [END_REF]. In order to study the anisotropy, the 2D-scattering patterns are averaged in angular sectors ± 15° around the two perpendicular directions // and ⊥ defined by the magnetic field. After dividing by the isotropic form factor of the nanoparticles, we obtain two different structure factors in the // and ⊥ directions. They are plotted in figure 6 at H = 1050 Oe and compared the value at H=0 Oe. The inset of figure 6 is a Kratky-Porod plot ln (q 2 S intra ) as a function of q 2 . Ln [ S intra (q) * q 2 ] q 2 (Å -2 )

Figure 6 -Comparison between Sintra(q) at H=0 and the under field determinations on sectors ± 15° around the direction parallel to the field and around the perpendicular direction. Inset : Kratky-Porod representation of the data.

Within the error bar there is no difference between the measurement in the direction perpendicular to the field and the isotropic situation at H=0 in both representations S intra (q) and ln (q 2 S intra )=f(q 2 ). Thus the thickness of the membrane in the direction perpendicular to the field δ ⊥ is of the same order as δ, the thickness in zero field. On the contrary in the direction parallel to the field the structure factor is substantially decreased with respect to the H=0 situation, up to q of the order of 2 10 -2 Å -1 . We conclude that the portions of membranes mostly affected by the magnetic field are those with their normal vector parallel to the field. In that direction the Kratky-Porod representation becomes almost flat : there is an important decrease of the apparent thickness δ // associated to a deficiency of nanoparticles inside the membrane patches that cross the field direction. Thus either the membrane becomes stretched in the portions of shell crossed by the magnetic field or almost equivalently the nanoparticles move away from the magnetic poles. To our knowledge, these mineralized vesicles are the first ones to have a fluid and magnetic membrane. Other magnetic shells have been mentioned in literature [21,22], but none as thin and as floppy as here.

The soft magnetic objects presented here are especially promising for drug delivery, their internal compartment being available for encapsulation of water-soluble species. A pH change or the application of a radio-frequency magnetic which would induce a local heating could trigger the transient opening of the envelope and the release of an encapsulated content.

  H 2 O/D 2 O) either PB 48 -b-PGA 114 or PB 48 -b-PGA 145 di-block copolymers with a ferrofluid based on γ-Fe 2 O 3 nanoparticles.

Figure 1 -

 1 Figure 1 -Sintra(q) of the hydrophobic nanoparticles confined in micelles of PB48-b-PGA114 and PB48-b-PGA145 obtained by SANS.The dashed line corresponds to a slope -4. The points at low q are obtained by SLS. Inset : SANS intensity as a function of q from the dilute ferrofluid, fitted with the form factor of the nanoparticles.The nanoparticles are dispersed in dichloromethane and stabilized by a commercial phosphoric di-ester tensioactive Beycostat NE ® . The inset of figure1shows the form factor

Figure 2 -

 2 Figure 2 -left : AFM picture of PB48-b-PGA114 copolymer micelles loaded with nanoparticles; scale bar : 400 nm. right : Height profile along the cross-section of the AFM picture.

Figure 3 -

 3 Figure 3-Sintra(q) of the hydrophobic nanoparticles confined in micelles of PB48-b-PGA56 obtained by SANS. The full line corresponds to the form factor of a vesicle of radius 312 nm and δ = 8.7 nm Inset : AFM picture of dispersion of these hollow hybrid objects, the bar length is 500 nm.

Figure 4 -

 4 Figure 4 -left : typical AFM lace shape of PB48-b-PGA56 copolymer vesicles, the membrane being loaded with nanoparticles; scale bar : 150 nm. right : Height profile along the cross-section of the AFM picture.

Figure 5 -

 5 Figure 5 -SANS pattern of hollow magnetic shells in the range 3 10 -3 -2 10 -2 Å -1 . left : in zero field; right : under a horizontal field H= 1050 Oe.

Acknowledgements We thank Fabrice Cousin and Julian Oberdisse as our local contacts at the LLB facilities.


Rumen Andonov

Nicola Yanev

Noël Malod-Dognin

Rr

Towards Structural Classification of Proteins based on Contact Map Overlap

Keywords: Protein structure alignment, Contact Map Overlap maximization, combinatorial optimization, integer programming, branch and bound, Lagrangian relaxation Alignement de structures de protéines, maximisation du recouvrement de cartes de contacts, optimisation combinatoire, programmation linéaire en nombre entier, séparation et évaluation, relaxation lagrangienne Acyl-CoA N-acyltransferases N-acetyl transferase, d1nsla, d1qsta, d1vhsa, d1s3za, d1n71a d1tiqa, d1q2ya, d1ghea, d1ufha, d1wh3a, d1mg8a, d1xd3b, d1wm3a, d1wiaa P450 d1jipa, d1izoa, d1x8va, d1io7a, d1jpza

A multitude of measures have been proposed to quantify the similarity between protein 3-D structure. Among these measures, contact map overlap (CMO) maximization deserved sustained attention during past decade because it offers a fine estimation of the natural homology relation between proteins. Despite this large involvement of the bioinformatics and computer science community, the performance of known algorithms remains modest. Due to the complexity of the problem, they got stuck on relatively small instances and are not applicable for large scale comparison.

This paper offers a clear improvement over past methods in this respect. We present a new integer programming model for CMO and propose an exact B&B algorithm with bounds computed by solving Lagrangian relaxation. The efficiency of the approach is demonstrated on a popular small benchmark (Skolnick set, 40 domains). On this set our algorithm significantly outperforms the best existing exact algorithms, and yet provides lower and upper bounds of better quality. Some hard CMO instances have been solved for the first time and within reasonable time limits. From the values of the running time and the relative gap (relative difference between upper and lower bounds), we obtained the right classification for this test. These encouraging result led us to design a harder benchmark to better assess the classification capability of our approach. We constructed a large scale set of 300 protein domains (a subset of ASTRAL database) that we have called Proteus 300. Using the relative gap of any of the 44850 couples as a similarity measure, we obtained a classification in very good agreement with SCOP. Our algorithm provides thus a powerful classification tool for large structure databases.

Introduction

A fruitful assumption of molecular biology is that proteins sharing close three-dimensional (3D) structures are likely to share a common function and in most case derive from a same ancestor. Computing the similarity between two protein structures is therefore a crucial task and has been extensively investigated [START_REF] Caprara | Optimal PDB Structure Alignments: Integer Programming Methods for Finding the Maximum Contact Map Overlap[END_REF][START_REF] Xu | A parametrized Algorithm for Protein Structer Alignment[END_REF][START_REF] Halperin | Principles of docking: An overview of search algorithms and a guide to scoring functions[END_REF][START_REF] Godzik | The Structural alignment between two proteins: is there a unique answer?[END_REF]. Interested reader can also refers [START_REF] Lancia | 101 Optimal PDB Structure Alignments: A branch and cut algorithm for the Maximum Contact Map Overlap problem[END_REF][START_REF] Caprara | Structural Alignment of Large-Size Protein via Lagrangian Relaxation[END_REF][START_REF] Lancia | Protein Structure Comparison: Algorithms and Applications[END_REF][START_REF] Strickland | Optimal Protein Struture Alignment Using Maximum Cliques[END_REF][START_REF] Agarwal | Fast Molecular Shape Matching Using Contact Maps[END_REF][START_REF] Krasnogor | Self Generating Metaheuristic in Bioinformatics: The Proteins Structure Comparison Case[END_REF][START_REF] Jaskowski | 3D-Judge -A Metaserver Approach to Protein Structure Prediction[END_REF][START_REF] Pelta | A fuzzy sets based generalization of contact maps for the overlap of protein structures[END_REF]. Since it is not clear what quantitative measure to use for comparing protein structures, a multitude of measures have been proposed. Each measure aims in capturing the intuitive notion of similarity. We studied the contact-map-overlap (CMO) maximization, a scoring scheme first proposed in [START_REF] Goldman | Algorithmic aspects of protein structure similarity[END_REF]. This measure has been found to be very useful for estimating protein similarity -it is robust, takes partial matching into account, translation invariant and captures the intuitive notion of similarity very well. The protein's primary sequence is usually thought as composed of residues. Under specific physiological conditions, the linear arrangement of residues will fold and adopt a complex 3D shape, called native state (or tertiary structure). In its native state, residues that are far away along the linear arrangement may come into proximity in 3D space. The proximity relation is captured by a contact map. Formally, a map is specified by a 0 -1 symmetric squared matrix C where c i j = 1 if the Euclidean distance of two heavy atoms (or the minimum distance between any two atoms belonging to those residues) from the i-th and the j-th amino acid of a protein is smaller than a given threshold in the protein native fold. In the CMO approach one tries to evaluate the similarity of two proteins by determining the maximum overlap (also called alignment) of contacts map. Formally: given two adjacency matrices, find two sub-matrices that correspond to principle minors 1 having the maximum inner product if thought as vectors (i.e. maximizing the number of 1 on the same position).

The counterpart of the CMO problem in the graph theory is the well known maximum common subgraph problem (MCS) [START_REF] Garey | Computers and Intractability: A Guide to the Thoery of NP-completness[END_REF]. The bad news for the later is its APXhardness 2 The only difference between the above defined CMO and MCS is that the isomorphism used for the MCS is not restricted to the non-crossing matching only.

Nevertheless the CMO is also known to be NP-hard [START_REF] Goldman | Algorithmic aspects of protein structure similarity[END_REF]. Thus the problem of designing efficient algorithms that guarantee the CMO quality is an important one that has eluded researchers so far. The most promising approach for solving CMO seems to be integer programming coupled with either Lagrangian relaxation [START_REF] Caprara | Optimal PDB Structure Alignments: Integer Programming Methods for Finding the Maximum Contact Map Overlap[END_REF] or B&B reduction technique [START_REF] Xie | A Reduction-Based Exact Algorithm for the Contact Map Overlap Problem[END_REF].

The results in this paper confirm once more the superiority of Lagrangian relaxation to CMO since the algorithm we present belongs to the same class. Our interest in CMO was provoked by its similarity with the protein threading problem. For the later we have presented an approach based on the so called non-crossing matching in bipartite graphs [START_REF] Andonov | Protein threading: From mathematical models to parallel implementations[END_REF]. It yielded a highly efficient algorithm solving the PTP by using the Lagrangian duality [START_REF] Balev | Solving the protein threading problem by lagrangian relaxation[END_REF][START_REF] Veber | Optimal protein threading by cost-splitting[END_REF][START_REF] Yanev | Lagrangian approaches for a class of matching problems[END_REF].

The contributions of this paper are as follows. We propose a new integer programming formulation of the CMO problem. For this model, we design a B&B algorithm coupled with a new Lagrangian relaxation for bounds computing. We compare our approach with the best existing exact algorithms [START_REF] Caprara | Optimal PDB Structure Alignments: Integer Programming Methods for Finding the Maximum Contact Map Overlap[END_REF][START_REF] Xie | A Reduction-Based Exact Algorithm for the Contact Map Overlap Problem[END_REF] on a widely used benchmark (the Skolnick set), and we noticed that it outperforms them significantly. New hard Skolnick set instances have been solved. In addition, we observed that our Lagrangian approach produces upper and lower bounds of better quality than in [START_REF] Caprara | Optimal PDB Structure Alignments: Integer Programming Methods for Finding the Maximum Contact Map Overlap[END_REF][START_REF] Xie | A Reduction-Based Exact Algorithm for the Contact Map Overlap Problem[END_REF]. This suggested us to use the relative gap (a function of these two bounds) as a similarity measure. To the best of our knowledge we are the first ones to propose such criterion for similarity. Our results demonstrated the very good classification potential of our method. Its capacity as classifier was further tested on the Proteus 300 set, a large benchmark of 300 domains that we extracted from ASTRAL-40 [START_REF] Chandonia | The ASTRAL Compendium in[END_REF]. We are not aware of any previous attempt to use a CMO tool on such large database. The obtained classification is in very good agreement with SCOP classification. This clearly demonstrates that our algorithm can be used as a tool for large scale classification.

The mathematical model

We are going to present the CMO problem as a matching problem in a bipartite graph, which in turn will be posed as a longest augmented path problem in a structured graph. Toward this end we need to introduce few notations as follows. The contacts maps of two proteins P1 and P2 are given by graphs

G m = (V m , E m ) with V m = {1, 2, . . . , n m } for m = 1, 2.
The vertices V m are better seen as ordered points on a line and correspond to the residues of the proteins. The arcs (i, j) correspond to the contacts. The right and left neighbouring of node i are elements of the sets

δ + m (i) = { j| j > i, (i, j) ∈ E m }, δ - m (i) = { j| j < i, ( j, i) ∈ E m }. Let i ∈ V 1 be matched with k ∈ V 2 and j ∈ V 1 be matched with l ∈ V 2 .
We will call a matching non-crossing, if i < j implies k < l. A feasible alignment of two proteins P 1 and P 2 is given by a non-crossing matching in the complete bipartite graph B with a vertex set V 1 ∪V 2 .

Let the weight w ik jl of the matching couple (i, k)( j, l) be set as follows

w ik jl = 1 if (i, j) ∈ E 1 and (k, l) ∈ E 2 0 otherwise (1)
For a given non-crossing matching M in B we define its weight w(M) as a sum over all couples of edges in M. The CMO problem consists then in maximizing w(M), where M belongs to the set of all non-crossing matching in B.

In [START_REF] Andonov | Protein threading: From mathematical models to parallel implementations[END_REF][START_REF] Balev | Solving the protein threading problem by lagrangian relaxation[END_REF][START_REF] Veber | Optimal protein threading by cost-splitting[END_REF][START_REF] Yanev | Lagrangian approaches for a class of matching problems[END_REF] we have already dealt with non-crossing matching and we have proposed a network flow presentation of similar one-to-one mappings (in fact the mapping INRIA there was many-to-one). The adaptation of this approach to CMO is as follows: The edges of the bipartite graph B are mapped to the points of n 1 × n 2 rectangular grid

B ′ = (V ′ , E ′ ) according to: point -(i, k) ∈ V ′ ←→ edge -(i, k) in B.
Definition. The feasible path is an arbitrary sequence (i 1 , k 1 ), (i 2 , k 2 ), . . . , (i t , k t ) of points in B ′ such that i j < i j+1 and k j < k j+1 for j = 1, 2, . . . ,t -1.

The correspondence feasible path ↔ non-crossing matching is obvious. This way non-crossing matching problems are converted to problems on feasible paths. We also add arcs (i, k) → ( j, l) ∈ E ′ iff w ik jl = 1. In B ′ , solving CMO corresponds to finding the densest (in terms of arcs) subgraph of B ′ whose node set is a feasible path (see Fig. 1). To each node (i, k) ∈ V ′ we associate now a 0/1 variable x ik , and to each arc (i, k) → ( j, l) ∈ E ′ , a 0/1 variable y ik jl . Denote by X the set of feasible paths. The problem can now be stated as follows (see Fig. 2 a) for illustration)

v(CMO) = max ∑ (ik)( jl)∈E ′ y ik jl (2)
subject to

x ik ≥ ∑ l∈δ + 2 (k) y ik jl , j ∈ δ + 1 (i) i = 1, 2, . . . , n1 -1, k = 1, 2, . . . , n2 -1 (3) x ik ≥ ∑ l∈δ - 2 (k) y jlik , j ∈ δ - 1 (i) i = 2, 3, . . . , n1, k = 2, 3, . . . , n2 (4)
x ik ≥ ∑ j∈δ + 1 (i) y ik jl , l ∈ δ + 2 (k) i = 1, 2, . . . , n1 -1, k = 1, 2, . . . , n2 -1 (5) x ik ≥ ∑ j∈δ - 1 (i) y jlik , l ∈ δ - 2 (k) i = 2, 3, . . . , n1, k = 2, 3, . . . , n2. ( 6
)
x ∈ X (7)

Actually, we know how to represent X with linear constraints. Recalling the definition of feasible path, ( 7) is equivalent to

k ∑ l=1 x il + i-1 ∑ j=1 x jk ≤ 1, i = 1, 2, . . . , n1, k = 1, 2, . . . , n2. ( 8
)
We recall that from the definition of the feasible paths in B ′ (non-crossing matching in B) the j-th residue from P1 could be matched with at most one residue from P2 and vice-versa. This explains the sums into right hand side of (3) and ( 5) -for arcs having their tails at vertex (i, k); and ( 4) and ( 6)-for arcs heading to (i, k). Any (i, k)( j, l) arc can be activated (y ik jl = 1) iff x ik = 1 and x jl = 1 and in this case the respective constraints are active because of the objective function.

A tighter description of the polytope defined by ( 3)-( 6) and 0 ≤ x ik ≤ 1, 0 ≤ y ik jl could be obtained by lifting the constraints ( 4) and ( 6) as it is shown in Fig. 2 b). The points shown are just the predecessors of (i, k) in graph B ′ and they form a grid of δ - 1 (i) rows and δ - 2 (k) columns. Let i 1 , i 2 , . . . , i s be all the vertices in δ - 1 (i) ordered according the numbering of the vertices in V 1 and likewise k 1 , k 2 , . . . , k t in δ - 2 (k). Then the vertices in the l-th column (i 1 , k l ), (i 2 , k l ), . . . (i s , k l ) correspond to pairwise crossing matching and at most one of them could be chosen in any feasible solution x ∈ X (see [START_REF] Lancia | 101 Optimal PDB Structure Alignments: A branch and cut algorithm for the Maximum Contact Map Overlap problem[END_REF]). This "all crossing" property will stay even if we add to this set the following two sets:

(i 1 , k 1 ), (i 1 , k 2 ), . . . , (i 1 , k l-1 ) and (i s , k l+1 ), (i s , k l+2 ), . . . , (i s , k t ).
Denote by col ik (l) the union of these three sets and analogously by row ik ( j) the corresponding union for the j-th row of the grid. When the grid is one column/row only the set row ik ( j)/col ik (l) is empty. Now a tighter LP relaxation of (3)-( 6) is obtained by changing (4) with

x ik ≥ ∑ (r,s)∈row ik ( j) y rsik , j ∈ δ - 1 (i) i = 2, 3, . . . , n1, k = 2, 3, . . . , n2 (9)
and ( 6) with

x ik ≥ ∑ (r,s)∈col ik (l) y rsik , l ∈ δ - 2 (k) i = 2, 3, . . . , n1, k = 2, 3, . . . , n2. (10)
Remark: Since we are going to apply the Lagrangian technique there is no need neither for an explicit description of the set X neither for lifting the constraints (3) (5).

Lagrangian relaxation approach

Here, we show how the Lagrangian relaxation of constraints ( 9) and ( 10) leads to an efficiently solvable problem, yielding upper and lower bounds that are generally better than those found by the best known exact algorithm [START_REF] Caprara | Optimal PDB Structure Alignments: Integer Programming Methods for Finding the Maximum Contact Map Overlap[END_REF].

Let λ h ik j ≥ 0 (respectively λ v ik j ≥ 0) be a Lagrangian multiplier assigned to each constraint (9) (respectively [START_REF] Agarwal | Fast Molecular Shape Matching Using Contact Maps[END_REF]). By adding the slacks of these constraints to the objective function with weights λ, we obtain the Lagrangian relaxation of the CMO problem

LR(λ) = max ∑ i,k, j∈δ - 1 (i) λ h ik j (x ik - ∑ (r,s)∈row ik ( j) y rsik ) + ∑ i,k,l∈δ - 2 (k) λ v ikl (x ik - ∑ (r,s)∈col ik (l) y rsik ) + ∑ (ik)( jl)∈E B ′
y ik jl [START_REF] Krasnogor | Self Generating Metaheuristic in Bioinformatics: The Proteins Structure Comparison Case[END_REF] subject to x ∈ X, (3), ( 5) and y ≥ 0.

INRIA l (i,k) (i,k) l n2 n2 n1 n1 a) b) j j
Figure 2: The shadowed area represents the set of vertices in V ′ which are tails for the arcs heading to (i, k). In a): corresponds to the indices of y jlik in ( 6) for l fixed. corresponds to the indices of y jlik in (4) for j fixed. In b): corresponds to the indices of y jlik in [START_REF] Agarwal | Fast Molecular Shape Matching Using Contact Maps[END_REF] for l fixed (the set col ik (l)).

corresponds to the indices of y jlik in (9) for j fixed (the set row ik ( j)).

Proposition 1 LR(λ) can be solved in O(|V

′ | + |E ′ |) time.
Proof: For each (i, k) ∈ V ′ , if x ik = 1 then the optimal choice y ik jl amounts to solving the following : The heads of all arcs in E ′ outgoing from (i, k) form a |δ

+ (i)| × |δ + (k)| table.
To each point ( j, l) in this table, we assign the profit max{0, c ik jl (λ)}, where c ik jl (λ) is the coefficient of y ik jl in [START_REF] Krasnogor | Self Generating Metaheuristic in Bioinformatics: The Proteins Structure Comparison Case[END_REF]. Each vertex in this table is a head of an arc outgoing from (i, k). Then the subproblem we need to solve consists in finding a subset of these arcs having a maximal sum c ik (λ) of profits(the arcs of negative weight are excluded as a candidates for the optimal solution) and such that their heads lay on a feasible path. This could be done by a dynamic programming approach in O(|δ + (i)||δ + (k)|) time. Once profits c ik (λ) have been computed for all (i, k) we can find the optimal solution to LR(λ) by using the same DP algorithm but this time on the table of n1 × n2 points with profits for (i, k)-th one given by

c ik (λ) + ∑ j∈δ - 1 (i) λ h ik j + ∑ l∈δ - 2 (k) λ v ikl . ( 12
)
where the last two terms are the coefficients of x ik in [START_REF] Krasnogor | Self Generating Metaheuristic in Bioinformatics: The Proteins Structure Comparison Case[END_REF]. Remark: The inclusion x ∈ X is explicitly incorporated in the DP algorithm.

The algorithm

In order to find the tightest upper bound on v(CMO) (or eventually to solve the problem), we need to solve in the dual space of the Lagrangian multipliers LD = min λ≥0 LR(λ), whereas LR(λ) is a problem in x, y. A number of methods have been proposed to solve Lagrangian duals: subgradient method, dual ascent methods,constraint generation method, column generation, bundel methods,augmented Lagrangian methods, etc.

Here, we choose the subgradient method. It is an iterative method in which at iteration t, given the current multiplier vector λ t , a step is taken along a subgradient of LR(λ), then if necessary, the resulting point is projected onto the nonnegative orthant. It is well known that practical convergence of the subgradient method is unpredictable. For some problems, convergence is quick and fairly reliable, while other problems tend to produce erratic behavior of the multiplier sequence, or the Lagrangian value, or both. In a "good" case, one usually observe a saw-tooth pattern in the Lagrangian value for the first iterations, followed by a roughly monotonic improvement and asymptotic convergence to a value that is hopefully the optimal Lagrangian bound. The computational runs on a reach set of real-life instances confirm a "good" case belonging of our approach at some expense in the speed of the convergence.

In our realization, the update scheme for λ ik j is λ t+1 ik j = max{0, λ t ik j -Θ t g t ik j }3 , where g t ik j = xik -∑ ȳ jlik (see ( 9) and ( 10) for the sum definition) is the sub-gradient component (0, 1,or -1), calculated on the optimal solution x, ȳ of LR(λ t ). The step size

Θ t is Θ t = α(LR(λ t )-Z lb ) ∑(g t ik j ) 2 +∑(g t ikl )
2 where Z lb is a known lower bound for the CMO problem and α is an input parameter. Into this approach the x-components of LR(λ t ) solution provides a feasible solution to CMO and thus a lower bound also. The best one (incumbent) so far obtained is used for fathoming the nodes whose upper bound falls below the incumbent and also in section 4 for reporting the final gap. If LD ≤ v(CMO) then the problem is solved. If LD > v(CMO) holds, in order to obtain the optimal solution, one could pass to a branch&bound algorithm suitably tailored for such an upper bounds generator.

From among various possible nodes splitting rules, the one shown in Fig. 3 gives quite satisfactory results (see section 4). Formally, let the current node be a subproblem of CMO defined over the vertices of V ′ falling in the interval [lc(k), uc(k)] for k = 1, n 2 (in Fig. 3 these are the points in-between two broken lines (the white area). Let (rowbest, colbest) be the argmax min(S u (i, k), S d (i, k)), where S d (i, k) = ∑ j≤k max(uc( j)i, 0) and S u (i, k) = ∑ j≥k max(ilc( j), 0). Now, the two descendants of the current node are obtained by discarding from its feasible set the vertices in S d (rowbest, colbest) and S u (rowbest, colbest) respectively. The goal of this strategy is twofold: to create descendants that are balanced in sense of feasible set size and to reduce maximally the parent node's feasible set.

In addition, the following heuristics happened to be very effective during the traverse of the B&B tree nodes. Once the lower and the upper bound are found at the root node, an attempt to improve the lower bound is realized as follows.

Let (i k 1 , k 1 ), (i k 2 , k 2 ), . . . , (i k s , k s ) be an arbitrary feasible path which activates certain number of arcs (recall that each iteration in the sub-gradient optimization phase generates such path and lower bound as well).

Then for a given strip size sz (an input parameter set by default to 4), the matchings in the original CMO are restricted to fall in a neighborhood of this path, allowing x ik to be non zero only for

max{1, i j -sz} ≤ i ≤ min{n1, i j + sz}, j = k 1 , k 2 , . . . , k s .
The Lagrangian dual of this subproblem is solved and a better lower bound is possibly sought. If the bound improves the incumbent, the same procedure is repeated by changing the strip alongside the new feasible solution.

Finally, the main steps of the B&B algorithm are as follows: Initialization: Set L={original CMO problem, i.e. no restrictions on the feasible paths}. Problem selection and relaxation: Select and delete the problem P i from L having the biggest upper bound. Solve the Lagrangian dual of P i . (Here a repetitive call to a heuristics is included after each improvement on the lower bound). Fathoming and Pruning: Follow classical rules. Partitioning : Create two descendants of P i using (rowbest, colbest) and add them to L. Termination : if L = / 0, the solution (x * , y * ) yielding the objective value is optimal.

Numerical results

To evaluate the above algorithm we performed two kinds of experiments. In the first one we compared our approach with the best existing algorithm from literature [START_REF] Caprara | Optimal PDB Structure Alignments: Integer Programming Methods for Finding the Maximum Contact Map Overlap[END_REF] in term of performance and quality of the bounds. This comparison was done on a set of proteins suggested by Jeffrey Skolnick which was used in various recent papers related to protein structure comparison [START_REF] Caprara | Optimal PDB Structure Alignments: Integer Programming Methods for Finding the Maximum Contact Map Overlap[END_REF][START_REF] Pelta | A fuzzy sets based generalization of contact maps for the overlap of protein structures[END_REF][START_REF] Xie | A Reduction-Based Exact Algorithm for the Contact Map Overlap Problem[END_REF]. This set contains 40 medium size domains from 33 proteins, which number of residues varies from 95 (2b3iA) to 252 (1aw2A). The maximum number of contacts is 593 (1btmA). We afterwards experimentally evaluated the capability of our algorithm to perform as classifier on the Proteus 300 set, a significantly larger protein set. It contains 300 domains, which number of residues varies from 64 (d15bba ) to 455 (d1po5a ). Its maximum number of contact is 1761 (d1i24a ). We will soon make available all data and results4 on the URL: http://www.irisa.fr/symbiose/softwares/resources/proteus300

Performance and quality of bounds

The results presented in this section were obtained on machines with AMD Opteron(TM) CPU at 2.4 GHz, 4 Gb Ram, RedHat 9 Linux. The algorithm was implemented in C. According to SCOP classification5 [START_REF] Murzin | SCOP: A structural classification of proteins database for the investigation of sequences and structures[END_REF], the Skolnick set contains five families (see Table 2 in Annexe) 6 . Note that both approaches that we compare use different La-grangian relaxations. Our algorithm is called a_purva 7 , while the other Lagrangian algorithm is denoted by LR.

The Skolnick set requires aligning 780 pairs of domains. We bounded the execution time to 1800 seconds for both algorithms. a_purva succeeded to solve 171 couples in the given time, while LR solved only 157 couples. Note that another exact algorithm called CMOS has been proposed in a very recent paper [START_REF] Xie | A Reduction-Based Exact Algorithm for the Contact Map Overlap Problem[END_REF]. CMOS succeeded to solve only 161 instances from the Skolnick set, yet the time limit was 4 hours on a similar workstation. Hence it seems that 171 is the best score ever obtained when exactly solving Skolnick set. To the best of our knowledge, we are the first ones to solve all the 164 instances with couples from the same SCOP folds, as well as the first to solve instances with couples from different folds (the 7 instances of the 6 th class presented in Table 1). The interested reader can find our detailed results on the webpage cited before.

Figure 4 illustrates LR/a_purva time ratio as a function of solved instances. It is easily seen that a_purva is significantly faster than LR (up to several hundred times in the majority of cases). Table 1 in the Annexe contains more details concerning a subset of 164 pairs of proteins. We observed that this set is a very interesting one. It is characterized by the following properties: a) in all but the 6 last instances the a_purva running time is less than 10 seconds; b) in all instances the relative gap 8 at the root of the B&B is smaller than 4, while in all other instances this gap is much larger (greater than 18 even for couples solved in less than 1800 sec); c) this set contains all instances such that both proteins belong to the same family according to SCOP classification. In other words, each pair such that both proteins belong to the same family is an easily solvable instance for a_purva and this feature can be successfully used as a discriminator. In fact, by virtue of this relation we were able to correctly classify the 40 items in the Skolnick set in 2000 seconds overall running time for all 780 instances. We will go back over this point in the next section. 1rn1 does not belong to the first family as indicated in [START_REF] Caprara | Optimal PDB Structure Alignments: Integer Programming Methods for Finding the Maximum Contact Map Overlap[END_REF]. Note that this corroborates the results obtained in [START_REF] Caprara | Optimal PDB Structure Alignments: Integer Programming Methods for Finding the Maximum Contact Map Overlap[END_REF] but the authors considered it as a mistake. 7 Apurva (Sanskrit) = not having existed before, unknown, wonderful, ... 8 We define the relative gap as 100 × U B-LB U B .

INRIA

Our next observation (see Fig. 5 and Fig. 6 in the Annexe) concerns the quality of gaps obtained by both algorithms on the set of unsolved instances. Remember that when a Lagrangian algorithm stops because of time limit (1800 sec. in our case) it provides two bounds: one upper (UB), and one lower (LB). Providing these bounds is a real advantage of a B&B type algorithm compared to any meta-heuristics. These values can be used as a measure for how far is the optimization process from finding the exact optimum. The value UB-LB is usually called absolute gap. Any one of the 609 points (x, y) in Fig. 5 presents the absolute gap for a_purva (x coordinate) and for LR (y coordinate) algorithm. All points are above the y = x line (i.e. the absolute gap for a_purva is always smaller than the absolute gap for LR). On the other hand the entire figure is very asymmetric in a profit of our algorithm since its maximal absolute gap is 33, while it is 183 for LR.

In Fig. 6 we similarly compare lower and upper bounds separately. Any point • has the lower bound computed by a_purva (res. LR) as x (res. y) coordinate, while any point × has the upper bound computed by a_purva (res. LR) as x (res. y) coordinate. We observe that in a large majority the points • are below the y = x line while the points × are above this line. This means that usually a_purva lowers bounds are higher, while its upper bounds are all smaller and therefore a_purva provides bounds with clearly better quality than LR. We don't have much information about the bounds find by CMOS, except that at the root of the B&B tree, it obtains upper bounds of worst quality than the ones of LR.

A purva as a classifier

When running a_purva on the Skolnick set, we observed that relative gaps are smaller for similar domains than for dissimilar ones. This became even more obvious when we fixed a small upper bound of iterations and limited the computations only to the root of the B&B tree. The question then was to check if the relative gap can be used as a similarity index (the smaller is the relative gap, the more similar are the domains) which can be given to an automatic classifier in order to quickly provide a classification.

We used the following protocol : the runs of a_purva were limited to the root, with a limit of 500 iterations for the subgradient descent. We used the publicly available hierarchical ascendant classifier Chavl [START_REF] Lerman | Likelihood linkage analysis (LLA) classification method (Around an example treated by hand)[END_REF], which proposes a best partition of classified elements based on the derivative of the similarity index and thus requires no similarity threshold. For the Skolnick set, the alignment of all couples was done in less than 1100 seconds (with a mean computation time of 1.39 seconds/couple). The classification returned by Chavl based on the relative gap is exactly the classification at the fold level in SCOP. Taking into account that according to Table 1, 609 couples ran 1800 seconds without finding the solution, this result pushes to use the relative gap as a classifier. Note also that we succeeded to classify the Skolnick set significantly faster than both previously published exact algorithms [START_REF] Xie | A Reduction-Based Exact Algorithm for the Contact Map Overlap Problem[END_REF][START_REF] Caprara | Optimal PDB Structure Alignments: Integer Programming Methods for Finding the Maximum Contact Map Overlap[END_REF] that use similarity indexes based on lower bound only. This illustrates the effectiveness of using a similarity based on both upper and lower bounds.

To get a stronger confirmation of a_purva classifier capabilities, we performed the same operation on the Proteus 300 set, presented in Table 3. The alignment 9 of the 44850 couples required roughly 82 hours (with a mean computation time of 6,58 seconds/couple).

Table 4 presents the classification that we obtain. It contains 25 classes denoted by letters A-Y. This classification is almost identical to the SCOP one (at folds level) which contains 24 classes denoted by numbers (presented in Table 3). 18 of the 24 SCOP classes correspond perfectly to our classes. Class 15 (resp. 24) contains two families 10that we classified in M and N (resp. V and W). Classes 9 and 11 were merged into class I and are indeed similar, with some domains (like d1jgca and d1b0b ) having more than 75% of common contacts 11 . Class 18 was split into its two families (X and Y), but Y was merged with class 10. Again, some of the corresponding domains (e.g. d1b00a and d1wb1a4) are very similar, with more than 75% of common contacts.

Conclusion

In this paper, we give an efficient exact B&B algorithm for contact map overlap problem. The bounds are found by using Lagrangian relaxation and the dual problem is solved by sub-gradient approach. The efficiency of the algorithm is demonstrated on a benchmark set of 40 domains and the dominance over the existing algorithms is total. In addition,its capacity as classifier (and this was the primary goal) was tested on a large data set of 300 protein domains. We were able to obtain in a short time a classification in very good agreement to the well known SCOP database.

We are curently working on the integration of biological information into the contact maps, such as the secondary structure type of the residues (alpha helix or beta strand). Aligning only residues from the same type will reduce the research space and thus speed up the algorithm.

Acknowledgement

Supported by ANR grant Calcul Intensif projet PROTEUS (ANR-06-CIS6-008) and by Hubert Curien French-Bulgarian partnership "RILA 2006" N 0 15071XF. N. Malod-Dognin is supported by Région Bretagne. We are thankful to Professor Giuseppe Lancia for numerous discussions and for kindly providing us with the source code and the contact map graphs for the Skolnick set.

All computations were done on the Ouest-genopole bioinformatics platform (http://genouest.org).

ANNEXE

Figure 1 :

 1 Figure 1: Left: Vertex 1 from V1 is matched with vertex 1 from V2 and 2 is matched with 3: matching couple (1, 1)(2, 3). Other matching couples are (3, 4)(5, 5). This defines a feasible matching M = {(1, 1)(2, 3), (3, 4)(5, 5)} with weight w(M) = 2. Right: The same matching is visualized in graph B ′ .

Figure 3 :

 3 Figure 3: Sketch of the B&B splitting strategy. a) the white area in-between broken lines represents the current node feasible set; b) This set is split by (rowbest, colbest), D corresponds to the set S d (rowbest, colbest) while U corresponds to the set S u (rowbest, colbest); c) and d) are the descendants of the node a).

Figure 4 :

 4 Figure 4: LR time a purva time ratio as a function of solved instances

Figure 5 :

 5 Figure 5: Comparing absolute gaps on the set of unsolved instances. The gaps computed by a purva are significantly smaller.

Table 1 :

 1 Column one contains the number of the families according to table 2. The sixth class contains the hardest solved Skolnick set intstances. Column two(six) contains the names of the couples, column three(seven) is the score, column four(height) gives the time in seconds taken by LR algoritm, and column five(nine) presents the corresponding time taken by a purva.

	F Proteins	CMO	Time	Time	Proteins	CMO	Time	Time
		Name		LR	a pr	Name		LR	a pr
	1	1b00A 1dbwA	149	192.00	1.2	1ntr 1qmpA	119	545.94	7.18
	1	1b00A 1nat	145	166.98	1.11	1ntr 1qmpB	115	454.01	4.23
	1	1b00A 1ntr	118	565.47	3.59	1ntr 1qmpC	116	610.93	6.56
	1	1b00A 1qmpA	143	198.72	1.33	1ntr 1qmpD	118	522.53	4.44
	1	1b00A 1qmpB	136	439.95	59.65	1ntr 3chy	130	339.86	5.53
	1	1b00A 1qmpC	139	263.81	1.68	1ntr 4tmyA	126	450.05	3.34
	1	1b00A 1qmpD	137	181.23	1.89	1ntr 4tmyB	127	399.26	3.75
	1	1b00A 3chy	154	141.50	0.85	1qmpA 1qmpB	221	3.77	0.03
	1	1b00A 4tmyA	155	143.92	0.9	1qmpA 1qmpC	232	0.35	0.02
	1	1b00A 4tmyB	155	75.41	0.73	1qmpA 1qmpD	230	0.02	0.03
	1	1dbwA 1nat	157	226.42	1.51	1qmpA 3chy	160	69.78	1.07
	1	1dbwA 1ntr	130	426.13	5.53	1qmpA 4tmyA	162	98.21	0.78
	1	1dbwA 1qmpA	152	159.74	2.93	1qmpA 4tmyB	164	50.48	0.62
	1	1dbwA 1qmpB	150	63.63	1.52	1qmpB 1qmpC	221	1.60	0.02
	1	1dbwA 1qmpC	150	180.52	2.38	1qmpB 1qmpD	220	1.61	0.03
	1	1dbwA 1qmpD	152	111.28	1.78	1qmpB 3chy	156	68.17	0.84
	1	1dbwA 3chy	164	84.22	1.19	1qmpB 4tmyA	157	51.32	0.58
	1	1dbwA 4tmyA	161	73.71	1.1	1qmpB 4tmyB	156	66.11	0.64
	1	1dbwA 4tmyB	163	47.87	1.11	1qmpC 1qmpD	226	3.65	0.02
	1	1nat 1ntr	127	302.39	3.59	1qmpC 3chy	157	75.14	1.23
	1	1nat 1qmpA	157	66.03	1.04	1qmpC 4tmyA	162	55.46	1.26
	1	1nat 1qmpB	149	69.00	0.99	1qmpC 4tmyB	162	78.52	0.58
	1	1nat 1qmpC	152	73.53	1.07	1qmpD 3chy	158	59.47	1.11
	1	1nat 1qmpD	151	99.14	1.33	1qmpD 4tmyA	157	59.23	0.71
	1	1nat 3chy	163	76.95	0.86	1qmpD 4tmyB	159	53.27	0.59
	1	1nat 4tmyA	175	15.58	0.28	3chy 4tmyA	171	54.33	0.55
	1	1nat 4tmyB	172	19.06	0.37	3chy 4tmyB	174	41.43	0.5
	1					4tmyA 4tmyB	230	0.02	0.02
	2	1bawA 1byoA	152	11.59	0.25	1byoB 2b3iA	135	7.21	0.27
	2	1bawA 1byoB	155	6.11	0.18	1byoB 2pcy	175	2.28	0.05
	2	1bawA 1kdi	140	33.84	0.55	1byoB 2plt	174	3.90	0.06
	2	1bawA 1nin	153	9.45	0.21	1kdi 1nin	129	52.53	1.13
	2	1bawA 1pla	124	28.04	0.62	1kdi 1pla	126	33.59	0.89
	2	1bawA 2b3iA	130	15.57	0.38	1kdi 2b3iA	122	40.83	0.84
	2	1bawA 2pcy	148	6.91	0.16	1kdi 2pcy	145	15.19	0.3
	2	1bawA 2plt	161	5.22	0.13	1kdi 2plt	150	24.56	0.32
	2	1byoA 1byoB	192	2.61	0.02	1nin 1pla	130	22.76	0.69
	2	1byoA 1kdi	148	17.89	0.35	1nin 2b3iA	129	25.55	0.5
	2	1byoA 1nin	140	30.14	0.85	1nin 2pcy	139	23.31	0.49
	2	1byoA 1pla	150	7.55	0.16	1nin 2plt	146	18.85	0.52
	2	1byoA 2b3iA	132	10.26	0.39	1pla 2b3iA	122	12.65	0.32
	2	1byoA 2pcy	176	2.18	0.04	1pla 2pcy	143	4.75	0.14
	2	1byoA 2plt	172	3.77	0.07	1pla 2plt	144	7.10	0.17
	2	1byoB 1kdi	152	11.89	0.21	2b3iA 2pcy	127	11.79	0.35
	2	1byoB 1nin	141	21.05	0.6	2b3iA 2plt	140	7.37	0.17
	2	1byoB 1pla	148	6.94	0.16	2pcy 2plt	172	3.67	0.06
	3	1amk 1aw2A	411	1272.28	1.48	1btmA 1tmhA	432	1801.97	2.81
	3	1amk 1b9bA	400	1044.23	2.04	1btmA 1treA	433	1512.26	2.59
	3	1amk 1btmA	427	1287.48	2.38	1btmA 1tri	419	1455.08	3.26
	3	1amk 1htiA	407	265.16	1.4	1btmA 1ydvA	385	692.72	1.52
	3	1amk 1tmhA	424	638.26	1.29	1btmA 3ypiA	406	1425.09	2.43
	3	1amk 1treA	411	716.51	1.52	1btmA 8timA	408	940.59	2
	3	1amk 1tri	445	447.54	0.97	1htiA 1tmhA	416	588.98	1.07
	3	1amk 1ydvA	384	462.44	1.05	1htiA 1treA	426	395.23	0.81
	3	1amk 3ypiA	412	427.66	0.97	1htiA 1tri	412	779.84	1.55
	3	1amk 8timA	410	386.73	0.94	1htiA 1ydvA	382	405.04	1.09
	3	1aw2A 1b9bA	411	961.04	3.28	1htiA 3ypiA	422	148.75	0.56

Table 2 :

 2 The Skolnick set

	Fold number	SCOP fold	SCOP family	Domains name
	1	7-bladed beta-propeller	WD40-repeat	d1nr0a1, d1nexb2, d1k8kc , d1p22a2, d1erja
				d1tbga , d1pgua2, d1gxra , d1pgua1, d1nr0a2
				INRIA

matrix that corresponds to a principle minor is a sub-matrix of a squared matrix obtained by deleting k rows and the same k columns

see "A compendium of NP optimization problems", http://www.nada.kth.se/∼viggo/problemlist/ RR n°6370

RR n°6370

analogously for λ ikl INRIA

solved instances, upper and lower bounds, computational time, classifications...

Using SCOP version 1.71

Caprara et al.[START_REF] Caprara | Optimal PDB Structure Alignments: Integer Programming Methods for Finding the Maximum Contact Map Overlap[END_REF] mention only four families. This wrong classification was also accepted in[START_REF] Pelta | A fuzzy sets based generalization of contact maps for the overlap of protein structures[END_REF] but not in[START_REF] Xie | A Reduction-Based Exact Algorithm for the Contact Map Overlap Problem[END_REF]. The families are in fact five as shown in Table2. According to SCOP classification the protein RR n°6370

Detailed results of the runs will be available in our web page.

In the SCOP classification, Families are sub-sub-classes of Folds.

The percentage of common contacts between domains i and j is CMO(i, j) MIN(C i ,C j ) where C i (resp C j ) denotes the number of contacts in domain i (resp j), and CMO(i, j) is the number of common contacts between i and j found by a purva.INRIA

R. Andonov

W TIM beta/alpha-barrel Class I aldolase d1n7ka , d1w3ia ,