Ivana Ticha

Zdenek Kleibl

Jana Stribrna

Jaroslav Kotlas

Martina Zimovjanova

Martin Mateju

Michal Zikan

M.D Petr Pohlreich

Screening for genomic rearrangements in and genes in

Keywords: BRCA1 gene, BRCA2 gene, large genomic rearrangements (LGR), hereditary breast and ovarian cancer syndrome, multiplex ligation-dependent probe amplification (MLPA), chromosome

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

BRCA1 (MIM# 113705) and BRCA2 (MIM# 600185) are major predisposition genes in hereditary breast and ovarian cancer. Frequency of germline BRCA1/2 mutations was estimated at 2-4.7% in unselected breast cancer (BC) patients from different populations [START_REF]Anglian Breast Cancer Study Group (2000) Prevalence and penetrance of BRCA1 and BRCA2 mutations in a population-based series of breast cancer cases[END_REF][START_REF] Malone | Prevalence and predictors of BRCA1 and BRCA2 mutations in a population-based study of breast cancer in white and black American women ages 35 to 64 years[END_REF][START_REF] Mateju | Population-based study of BRCA1/2 mutations: Family history based criteria identify minority of mutation carriers[END_REF]. Pathogenic alterations are predominantly represented by small deletions, insertions and point mutations leading to premature termination of translation and production of truncated proteins. Deletions and duplications of large genomic regions or alterations that combine both deletion and insertion events have been increasingly reported during period following the introduction of multiple ligation-dependent probe amplification (MLPA) testing [START_REF] Hogervorst | Large genomic deletions and duplications in the BRCA1 gene identified by a novel quantitative method[END_REF]. The majority of large genomic rearrangements (LGR) at the BRCA1 locus are unique and their frequency is not expected to vary markedly among various geographic regions [START_REF] Mazoyer | Genomic rearrangements in the BRCA1 and BRCA2 genes[END_REF]. They represented 8-10% of all BRCA1 mutations in several countries [START_REF] Mazoyer | Genomic rearrangements in the BRCA1 and BRCA2 genes[END_REF][START_REF] De La Hoya | Genomic rearrangements at the BRCA1 locus in Spanish families with breast/ovarian cancer[END_REF][START_REF] Engert | MLPA screening in the BRCA1 gene from 1,506 German hereditary breast cancer cases: novel deletions, frequent involvement of exon 17, and occurrence in single early-onset cases[END_REF][START_REF] Gad | Significant contribution of large BRCA1 gene rearrangements in 120 French breast and ovarian cancer families[END_REF][START_REF] Hansen | Large BRCA1 and BRCA2 genomic rearrangements in Danish high risk breast-ovarian cancer families[END_REF][START_REF] Puget | Screening for germ-line rearrangements and regulatory mutations in BRCA1 led to the identification of four new deletions[END_REF]. The elevated incidence of LGRs in certain ethnic groups is caused by founder effect. In Dutch population, deletions of exon 13 or 22 represented 36% (12/33) of all BRCA1 mutations found in 170 families [START_REF] Petrij-Bosch | BRCA1 genomic deletions are major founder mutations in Dutch breast cancer patients[END_REF].

In another group of 805 Dutch patients, these two deletions were detected in 23.1% (28/121) of BRCA1 positive cases and all LGRs accounted for 27.3% of BRCA1 mutations [START_REF] Hogervorst | Large genomic deletions and duplications in the BRCA1 gene identified by a novel quantitative method[END_REF]. High proportion of LGRs was also found in Italy where LGRs accounted for 19% of BRCA1 mutations [START_REF] Agata | Prevalence of BRCA1 genomic rearrangements in a large cohort of Italian breast and breast/ovarian cancer families without detectable BRCA1 and BRCA2 point mutations[END_REF].

Most of

LGRs are the result of unequal homologous recombination between Alu repeats accumulated at the BRCA1 locus [START_REF] Smith | Complete genomic sequence and analysis of 117 kb of human DNA containing the gene BRCA1[END_REF]. Numerous recombination sites in homologous regions located in the BRCA1 gene and the BRCA1 pseudogene (ψBRCA1) were described by Puget and colleagues [START_REF] Puget | Screening for germ-line rearrangements and regulatory mutations in BRCA1 led to the identification of four new deletions[END_REF][START_REF] Puget | Distinct BRCA1 rearrangements involving the BRCA1 pseudogene suggest the existence of a recombination hot spot[END_REF] and afterwards by other authors [START_REF] Mazoyer | Genomic rearrangements in the BRCA1 and BRCA2 genes[END_REF].

Contrary to BRCA1, the germline BRCA2 rearrangements have not been identified in several populations [START_REF] Buffone | Prevalence of BRCA1 and BRCA2 genomic rearrangements in a cohort of consecutive Italian breast and/or ovarian cancer families[END_REF][START_REF] Preisler-Adams | Gross rearrangements in BRCA1 but not BRCA2 play a notable role in predisposition to breast and ovarian cancer in high-risk families of German origin[END_REF][START_REF] Pylkas | Analysis of large deletions in BRCA1, BRCA2 and PALB2 genes in Finnish breast and ovarian cancer families[END_REF] and in other geographic areas occurred rarely [START_REF] Engert | MLPA screening in the BRCA1 gene from 1,506 German hereditary breast cancer cases: novel deletions, frequent involvement of exon 17, and occurrence in single early-onset cases[END_REF][START_REF] Hansen | Large BRCA1 and BRCA2 genomic rearrangements in Danish high risk breast-ovarian cancer families[END_REF][START_REF] Staaf | Detection and precise mapping of germline rearrangements in BRCA1, BRCA2, MSH2, and MLH1 using zoom-in array comparative genomic hybridization (aCGH)[END_REF][START_REF] Agata | Large genomic deletions inactivate the BRCA2 gene in breast cancer families[END_REF]. LGRs in the BRCA2 gene were most frequent in families with multiple BC cases including one or more male BC cases [START_REF] Gutierrez-Enriquez | Screening for large rearrangements of the BRCA2 gene in Spanish families with breast/ovarian cancer[END_REF][START_REF] Tournier | Significant contribution of germline BRCA2 rearrangements in male breast cancer families[END_REF].

Rearrangements at the BRCA1 locus represented 10.4% (10/96) of all BRCA1 mutations identified in high-risk families in Moravia -the eastern part of the Czech Republic [START_REF] Vasickova | High occurrence of BRCA1 intragenic rearrangements in hereditary breast and ovarian cancer syndrome in the Czech Republic[END_REF].

Further, one rearrangement in the gene was identified by RNA-based analysis performed in our previous study [START_REF] Zikan | Novel complex genomic rearrangement of the BRCA1 gene[END_REF]. These results indicated that screening for LGRs in the BRCA1 gene should be included in genetic testing in high-risk BC or ovarian cancer (OC) families.

Nevertheless, only high-risk families were screened for LGRs at the BRCA1 locus and LGRs within the BRCA2 gene have not been analyzed at all in the Czech population. In this study, MLPA analysis was applied to determine the frequency and spectrum of LGRs in the BRCA1/2 genes in a group of patients from BC and/or OC families and a group of high-risk patients not selected on the basis of their family history of cancer. Oligonucleotide arraybased comparative genomic hybridization (aCGH) was used for precise location of LGRs.

The purpose of this study was to define reliable inclusion criteria for LGR testing. [START_REF] Bartonkova | Doporučené zásady péče o nemocné s nádory prsu a vaječníků a zdravé osoby se zárodečnými mutacemi genů BRCA1 nebo BRCA2 [Recommendations for care of patients with breast and ovarian cancer and healthy individuals with germline mutations in BRCA1 or BRCA2 gene[END_REF][START_REF] Plevová | Syndrom hereditárního karcinomu prsu a ovarií [Hereditary breast and ovarian cancer syndrome[END_REF].

Materials and methods

Patients and samples

Selection

A series of 655 patients was first analyzed for the presence of point mutations and small deletions or insertions in BRCA1/2 genes as described previously [START_REF] Pohlreich | Mutations of the BRCA1 gene in hereditary breast and ovarian cancer in the Czech Republic[END_REF][START_REF] Pohlreich | High proportion of recurrent germline mutations in the BRCA1 gene in breast and ovarian cancer patients from the Prague area[END_REF] and those tested negative for mutations in coding gene regions were subsequently screened for LGRs at BRCA1/2 loci. This series represented 521 cases including (i) 239 patients from high-risk families (referred herein as familial/hereditary cancer cases) and (ii) 282 patients selected regardless of the absence of reported family history of cancer (referred herein as sporadic/non-familial cancer cases). The first group met the following criteria in first-or second-degree relatives: two cases of either BC diagnosed before the age of 50 or OC diagnosed at any age; and three or more cases of BC or OC diagnosed at any age. A total of 161 families had a history positive for BC only (HBC families), 69 families had both BC and OC (HBOC families) and 9 families had OC only (HOC families). The second group included patients diagnosed with BC before the age of 36 (138 cases) or OC before the age of 40 (64 cases), patients with bilateral BC before the age of 51 (27 cases), patients with both primary breast and ovarian cancer (18 cases) or medullary breast carcinoma (19 cases) and cases of male BC (16 cases). The study was approved by the Ethical Committee of the First Faculty of Medicine and the General University Hospital and all participants gave their written informed consent prior to genetic testing.

Genomic DNA was isolated from EDTA blood samples using the Wizard Genomic DNA Purification System (Promega, Madison, WI) according to the supplier's instructions.

Mutation probabilities calculation

To compare detected mutation frequencies in analyzed groups with expected mutation frequencies, we retrospectively calculated mutation probabilities in BRCA1/2 genes using BRCAPRO BayesMendel model [START_REF] Parmigiani | Determining carrier probabilities for breast cancer-susceptibility genes BRCA1 and BRCA2[END_REF]

MLPA analysis

The SALSA MLPA kits for BRCA1 (the primary screening kit P002B and the confirmatory kit P087) and BRCA2 (kit P045-B1; MRC-Holland, Amsterdam, The Netherlands) were used for relative quantification of each of the BRCA1/2 exons according to the manufacturer's instructions. Amplified products were separated on an ABI 3130 genetic analyzer (Applied Biosystems, Foster City, USA). The collected data were analyzed using Gene Mapper v4.0

Software (Applied Biosystems) and evaluated by both visual comparison of chromatograms and quantitative comparison of peak areas exported to Excel spreadsheet. Samples differing in a relative peak area by more than 30% were reanalyzed with the P087 kit. Samples with single exon deletion were sequenced to exclude the presence of sequence variants affecting probe hybridization.

Array-based comparative genomic hybridization

The chromosome 17 -specific aCGH (Roche NimbleGen, Madison, USA) was used to locate deletion breakpoints in regions flanking the BRCA1 gene. The arrays format was 385K; median oligonucleotide probe (50 to 75mer) spacing was 160 bp.

Sample and reference DNA (from blood samples of 100 random blood donors) were fragmented by sonication and further processed according to the supplier's protocol (Roche NimbleGen). Briefly, 1 µg of sample DNA was labeled with Cy3-and the same amount of reference DNA with Cy5-dye using a NimbleGen Dual-Color DNA Labeling Kit.

Differentially labeled DNA samples were purified, combined (6 µg of each labeled DNA) and hybridized to arrays for 18 hours at 42°C. The slides were washed, dried and fluorescence was recorded at 3µm resolution using microarray fluorescent scanner Innoscan 700 (INNOPSYS, France). Scanned images were analyzed using NimbleScan software.

Fluorescence signals were normalized with qspline algorithm [START_REF] Workman | A new non-linear normalization method for reducing variability in DNA microarray experiments[END_REF] to compensate for inherent differences in signal between the two dyes. Copy number analysis was performed using the segMNT algorithm [START_REF] Olshen | Circular binary segmentation for the analysis of array-based DNA copy number data[END_REF], and statistically significant regions of aberration were visualized using SignalMap software (Roche NimbleGen).

DNA breakpoint analysis

Large deletions detected by MLPA and located by aCGH were validated by identification and characterization of the genomic breakpoints. Long-range PCR (LR-PCR) implementing

Expand Long Template PCR System (Roche Applied Science) was performed according to the manufacturer's instructions with primers flanking the breakpoints (Table 1) to amplify the junction fragment carrying the deletion. The junction fragments of previously reported rearrangements were obtained with published primers [START_REF] Preisler-Adams | Gross rearrangements in BRCA1 but not BRCA2 play a notable role in predisposition to breast and ovarian cancer in high-risk families of German origin[END_REF][START_REF] Vasickova | High occurrence of BRCA1 intragenic rearrangements in hereditary breast and ovarian cancer syndrome in the Czech Republic[END_REF][START_REF] Zikan | Novel complex genomic rearrangement of the BRCA1 gene[END_REF]. Amplified PCR fragments were separated on agarose gels and visualized by ethidium bromide staining. PCR products, corresponding to the deleted allele, were purified with ExoSAP-IT (USB Corp., Cleveland, USA) according to the manufacturer's instructions and sequenced using the BigDye v3.1

terminator cycle sequencing kit (Applied Biosystems) on an ABI 3130 genetic analyzer.

Nomenclature of mutations

Mutations were described according to the recommended nomenclature system described by the Human Genome Variation Society (HGVS) [START_REF] Den Dunnen | Mutation nomenclature extensions and suggestions to describe complex mutations: a discussion[END_REF]. Designation of the genomic rearrangements in the BRCA1 gene is based on the reference sequence L78833.1; deletions of exons 1-17 and exons 1-2 on the reference sequence NC_000017.9 complement (38300000..38760000) [START_REF]Finishing the euchromatic sequence of the human genome[END_REF]. Whole genomic locale is from March 2006 assembly of the UCSC Genome Browser on Human, NCBI Build 36.1 (available at http://genome.ucsc.edu).

Haplotype analysis

DNA samples carrying deletion of exons 1-17 or 5-14 in the BRCA1 gene were genotyped for two BRCA1 intragenic microsatellite markers (D17S855, D17S1322), and two markers (D17S1320, D17S1325) flanking BRCA1 gene on the centromeric and telomeric side, respectively. Each marker was amplified by PCR using FAM-labeled forward primers as described previously [START_REF] Soukupova | Contribution of mutations in ATM to breast cancer development in the Czech population[END_REF] and analyzed on an ABI 3130 genetic analyzer.

Results

Prevalence of genomic rearrangements in BRCA1/2 genes

LGRs were examined in 521 unrelated patients negative for BRCA1 and BRCA2 point mutations. A series of 239 high-risk patients was selected from 161 HBC families and 78

HBOC or HOC families. A second series of 282 participants represented non-familial cancer cases. MLPA analysis revealed 8 different LGRs in BRCA1 gene in 14 (2.7%, 14/521) probands (Table 2). The frequency of LGRs in the whole group of BRCA1/2 tested patients (including 134 patients with small mutations) was 2.1% (14/655) (Table 3). Deletions were detected in the entire BRCA1 locus and varied in size from less than 4 kb to more than 80 kb.

The five rearrangements detected in eight families were novel (Fig. 1). One of the identified mutations (deletion of exons 1-2) occurred repeatedly in several countries [START_REF] Mazoyer | Genomic rearrangements in the BRCA1 and BRCA2 genes[END_REF][START_REF] Engert | MLPA screening in the BRCA1 gene from 1,506 German hereditary breast cancer cases: novel deletions, frequent involvement of exon 17, and occurrence in single early-onset cases[END_REF][START_REF] Puget | Distinct BRCA1 rearrangements involving the BRCA1 pseudogene suggest the existence of a recombination hot spot[END_REF][START_REF] Montagna | Genomic rearrangements account for more than one-third of the BRCA1 mutations in northern Italian breast/ovarian cancer families[END_REF][START_REF] Hartmann | Large BRCA1 gene deletions are found in 3% of German high-risk breast cancer families[END_REF]; two other mutations (deletion of exons 5-14 and 21-22) have already been detected in the Czech population [START_REF] Vasickova | High occurrence of BRCA1 intragenic rearrangements in hereditary breast and ovarian cancer syndrome in the Czech Republic[END_REF][START_REF] Zikan | Novel complex genomic rearrangement of the BRCA1 gene[END_REF]. No LGRs were identified in the BRCA2 gene in 521 analyzed samples of high-risk patients.

LGRs were significantly more frequent in the group of patients from high-risk families (12/239, 5.0%) compared to the group of non-familial cancer cases (2/282, 0.7%, P = 0.002).

In high-risk families, the frequency of LGRs was higher among patients from HBOC and HOC families (6/78, 7.7%) than that from HBC families (6/161, 3.7%, P = 0.2). Similar to

LGRs, the highest frequency of BRCA1 point mutations was also found in a group of HBOC and HOC families (Table 3). Among non-familial cancer cases two LGRs were found, a deletion of exons 5-14 in a woman diagnosed with medullary BC at the age of 39, and a deletion of exons 21-22 in a woman with OC at the age of 36.

In total, 14 large deletions or complex rearrangements were detected at the BRCA1 locus in 521 independent families, which accounted for 12.3% (14/114) out of all identified BRCA1 mutations (Table 3). To compare the number of actually detected mutations in BRCA1 gene with expected mutation frequencies in our study groups, we implemented BRCAPRO computational model to retrospectively estimate the likelihood of finding germline BRCA1 mutations. Compared to BRCAPRO, we obtained slightly higher frequencies of BRCA1 mutations in all analyzed patients and in high-risk families and non-familial cancer cases subgroups (Table 4). Small discrepancies in mutation rates may be influenced by the fact that the BRCAPRO can underpredict the numbers of mutations, especially in low carrier probability categories [START_REF] Lindor | Predicting BRCA1 and BRCA2 gene mutation carriers: comparison of LAMBDA, BRCAPRO, Myriad II, and modified Couch models[END_REF][START_REF] Antoniou | Predicting the likelihood of carrying a BRCA1 or BRCA2 mutation: validation of BOADICEA, BRCAPRO, IBIS, Myriad and the Manchester scoring system using data from UK genetics clinics[END_REF][START_REF] Van Harssel | Efficiency of BRCAPRO and Myriad II mutation probability thresholds versus cancer history criteria alone for BRCA1/2 mutation detection[END_REF] Characterization of LGRs and determination of breakpoints Specification of families with identified mutations and characterization of LGRs are described in Table 2. A deletion of exons 1-2 was found in a woman from HBOC family No 779.

Sequencing of the junction fragment amplified from a patient DNA sample revealed a deletion of 36,934 bp (g.197575_234508del36934) with identical breakpoints as described previously in families from the USA [START_REF] Puget | Distinct BRCA1 rearrangements involving the BRCA1 pseudogene suggest the existence of a recombination hot spot[END_REF], Italy [START_REF] Montagna | Genomic rearrangements account for more than one-third of the BRCA1 mutations in northern Italian breast/ovarian cancer families[END_REF] and Germany [START_REF] Engert | MLPA screening in the BRCA1 gene from 1,506 German hereditary breast cancer cases: novel deletions, frequent involvement of exon 17, and occurrence in single early-onset cases[END_REF]. A deletion of exons 5-14 was identified in two high-risk HBOC families, one HBC family encompassing four BC cases (including two bilateral BC cases) and one sporadic BC patient with medullary BC. LR-PCR and sequence analysis of the amplified junction fragment confirmed in all four cases a deletion of 31,583 nucleotides (g.21716_53298del31583) resulting in an in frame deletion of 1,450 amino acids, which was detected in four patients from Moravia, Czech Republic [START_REF] Vasickova | High occurrence of BRCA1 intragenic rearrangements in hereditary breast and ovarian cancer syndrome in the Czech Republic[END_REF] and in one from Germany [START_REF] Engert | MLPA screening in the BRCA1 gene from 1,506 German hereditary breast cancer cases: novel deletions, frequent involvement of exon 17, and occurrence in single early-onset cases[END_REF]. In frame deletion involving exons 21-22 and simultaneous insertion of a 236-bp intronic fragment into the site of a deleted sequence (g.77128_80906del3779ins236) was detected once in our laboratory [START_REF] Zikan | Novel complex genomic rearrangement of the BRCA1 gene[END_REF] and two times in Moravia [START_REF] Vasickova | High occurrence of BRCA1 intragenic rearrangements in hereditary breast and ovarian cancer syndrome in the Czech Republic[END_REF].

A large deletion affecting exons 1-17 was identified in two HBC families and in two high-risk HBOC families. Chromosome 17 -specific aCGH was used to map accurately borders of the deletion extending the 5′ boundary of the BRCA1 gene, which enabled precise design of PCR primers and sequencing of breakpoints (Fig. 2a). Junction fragments of 1,311 bp were obtained from patients' genomic DNA with primers spanning the region from the end of the NBR2 gene to intron 17 of BRCA1. Sequence analysis of amplified fragments revealed a deletion of 80,496 bp (g.208928_289423del80496) in all four families with breakpoints occurring in a 37-bp region of identical sequence within two AluY repeats located more than 20 kb upstream of the BRCA1 translation start site and in intron 17 of BRCA1.The deletion spanned more than 90% of the BRCA1 coding sequence together with coding sequence of the NBR2 gene. The deletion of exons 1-17 was also described in Sweden [START_REF] Staaf | Detection and precise mapping of germline rearrangements in BRCA1, BRCA2, MSH2, and MLH1 using zoom-in array comparative genomic hybridization (aCGH)[END_REF], but the alteration had different breakpoints and included 284,479 bp.

A complex recombination event characterized by the deletion of exons 5-10 and the insertion of a short nucleotide stretch derived from the sequence in intron 3 of the BRCA1 gene (Fig. 3) A deletion comprising exons 13-19 was found in a woman with bilateral BC from HBC family No 571. The specific junction fragment of 716 bp was obtained from patient's DNA using primers located in introns 12 and 19 (Fig. 4). Sequence analysis identified a deletion of 25,201 bp (g.41850_67050del25201). Despite the deletion of exons 13-19 maintains the BRCA1 reading frame, elimination of the gene region coding for 336 amino acids (p.Gln1396_Glu1731del) is probably of pathogenic nature. The deleted region comprises the substantial part of the functional BRCT (BRCA1 C-terminal) domain (amino acid residues 1,646-1,859) [START_REF] Narod | BRCA1 and BRCA2: 1994 and beyond[END_REF] affected by several reported missense and nonsense mutations associated with BC [START_REF]Breast Cancer information Core database (BIC)[END_REF].

was
In HBC family No 897 affected with six cases of BC, a deletion of exons 18-22 was revealed.

Chromosome 17 -specific aCGH was used to map the deletion breakpoints (Fig. 2b). LR-PCR with primers located in introns 17 and 22 amplified a family specific fragment of 3,738 bp.

Sequencing of the junction fragment showed that recombination took place at highly region of the gene, study of allelic expression was not possible, however, monoallelic expression of the BRCA1 gene was observed in a patient with the deletion involving exon 24 [START_REF] Engert | MLPA screening in the BRCA1 gene from 1,506 German hereditary breast cancer cases: novel deletions, frequent involvement of exon 17, and occurrence in single early-onset cases[END_REF]. In addition, the deleted gene region coding for terminal 104 amino acid residues includes an essential part of the C-terminal BRCT domain of the BRCA1 protein. The similar deletion of exons 21-24 was also described in the USA in a family with Irish ancestry [START_REF] Walsh | Spectrum of mutations in BRCA1, BRCA2, CHEK2, and TP53 in families at high risk of breast cancer[END_REF], but in this 19,245-bp long deletion, Alu repeats were involved in recombination.

Analysis of BRCA1 Haplotypes

To evaluate whether the repeatedly occurring deletions in the BRCA1 gene involving exons 1-17 and 5-14 (both found in four families) represent founder mutations, haplotype analysis was performed in families carrying these alterations. One specific ~756-kb haplotype defined by D17S855, D17S1322, D17S1320 and D17S1325 markers was common for each carrier with a given type of alteration, which indicates the same origin for each mutation (Table 5).

Discussion

The frequency of LGRs in our study (12.3% of all mutations found in BRCA1 gene) was lower than that observed in the Netherlands (27.3%) [START_REF] Hogervorst | Large genomic deletions and duplications in the BRCA1 gene identified by a novel quantitative method[END_REF] and Italy (19%) [START_REF] Agata | Prevalence of BRCA1 genomic rearrangements in a large cohort of Italian breast and breast/ovarian cancer families without detectable BRCA1 and BRCA2 point mutations[END_REF], but it was in agreement with data reported from Denmark (12.5%) [START_REF] Hansen | Large BRCA1 and BRCA2 genomic rearrangements in Danish high risk breast-ovarian cancer families[END_REF], France (12%) [START_REF] Gad | Significant contribution of large BRCA1 gene rearrangements in 120 French breast and ovarian cancer families[END_REF], Germany (9.6%) [START_REF] Engert | MLPA screening in the BRCA1 gene from 1,506 German hereditary breast cancer cases: novel deletions, frequent involvement of exon 17, and occurrence in single early-onset cases[END_REF] and Spain (8.2%) [START_REF] De La Hoya | Genomic rearrangements at the BRCA1 locus in Spanish families with breast/ovarian cancer[END_REF]. Frequency of LGRs described in Moravia (10.4% of all detected BRCA1 mutations) [START_REF] Vasickova | High occurrence of BRCA1 intragenic rearrangements in hereditary breast and ovarian cancer syndrome in the Czech Republic[END_REF] was similar to our results. However, only two mutations (deletions of Nevertheless, haplotype analysis was not carried out in affected families. The deletion of exons 1-2 was the only identified mutation spread throughout Europe [START_REF] Mazoyer | Genomic rearrangements in the BRCA1 and BRCA2 genes[END_REF]. In the presented study, five novel LGRs were found. Frequent occurrence of unique mutations is in agreement with the results obtained from other countries [START_REF] Mazoyer | Genomic rearrangements in the BRCA1 and BRCA2 genes[END_REF].

The whole group of 521 high-risk patients was tested for LGRs in the BRCA2 gene, however, no alterations were found. Very low frequency of LGRs was reported from Germany, where a gross rearrangement in the BRCA2 gene was found only in one family with male BC out of 450 analyzed families [START_REF] Engert | MLPA screening in the BRCA1 gene from 1,506 German hereditary breast cancer cases: novel deletions, frequent involvement of exon 17, and occurrence in single early-onset cases[END_REF]. In Denmark, a group of 642 patients was screened for LGRs and one deletion in BRCA2 was also described in a family with male BC [START_REF] Hansen | Large BRCA1 and BRCA2 genomic rearrangements in Danish high risk breast-ovarian cancer families[END_REF]. Higher frequency of rearrangements in the BRCA2 gene was found in Spain (2/20) [START_REF] Gutierrez-Enriquez | Screening for large rearrangements of the BRCA2 gene in Spanish families with breast/ovarian cancer[END_REF] and France (3/39) [START_REF] Tournier | Significant contribution of germline BRCA2 rearrangements in male breast cancer families[END_REF] in families with female and male BC. In our study, only a small group of 5 families with female and male BC was analyzed with negative results for rearrangements in BRCA2. On the other hand, our results are not in agreement with analyses performed in France [START_REF] Casilli | The contribution of germline rearrangements to the spectrum of BRCA2 mutations[END_REF], Spain [START_REF] Gutierrez-Enriquez | Screening for large rearrangements of the BRCA2 gene in Spanish families with breast/ovarian cancer[END_REF] and the USA [START_REF] Walsh | Spectrum of mutations in BRCA1, BRCA2, CHEK2, and TP53 in families at high risk of breast cancer[END_REF] where genomic rearrangements of the BRCA2 gene have been found in families with no male BC cases.

Homologous recombination between Alu sequences is associated with most reported rearrangements at the BRCA1 locus [START_REF] Mazoyer | Genomic rearrangements in the BRCA1 and BRCA2 genes[END_REF]. High percentage of LGRs identified in our study group of patients was also caused by recombination of Alu repeats (Table 2). Deletions of exons 5-14, 13-19 and 21-24 were not mediated by Alu/Alu recombination and the deletion of exons 1-2 resulted from recombination of a sequence in intron 2 of the BRCA1 gene with the homologous sequence from the ψBRCA1 gene [START_REF] Puget | Distinct BRCA1 rearrangements involving the BRCA1 pseudogene suggest the existence of a recombination hot spot[END_REF].

Sequencing of the junction fragment amplified by LR-PCR that confirms MLPA results and characterizes deletion breakpoints is a necessary step in the LGR analysis. However, location of the breakpoints and PCR amplification may fail when the deletion interferes with large introns or regions beyond the gene boundaries, where the location of the breakpoints may be difficult. In tested carriers, we initially failed to amplify specific junction fragments in two novel

LGRs with borders located in regions adjacent to the BRCA1 gene (deletions comprising exons 1-17 and 21-24). Chromosome-specific aCGH with a high density of oligonucleotide probes is a method that enables accurate mapping of the deleted region. In this study, we implemented commercially available chromosome 17 -specific oligonucleotide arrays (Roche NimbleGen) that have comparable density of probes as custom made arrays described recently [START_REF] Staaf | Detection and precise mapping of germline rearrangements in BRCA1, BRCA2, MSH2, and MLH1 using zoom-in array comparative genomic hybridization (aCGH)[END_REF]. The technique was validated by analysis of a sample with already identified breakpoints (deletion of exons [START_REF] Staaf | Detection and precise mapping of germline rearrangements in BRCA1, BRCA2, MSH2, and MLH1 using zoom-in array comparative genomic hybridization (aCGH)[END_REF][START_REF] Agata | Large genomic deletions inactivate the BRCA2 gene in breast cancer families[END_REF][START_REF] Gutierrez-Enriquez | Screening for large rearrangements of the BRCA2 gene in Spanish families with breast/ovarian cancer[END_REF][START_REF] Tournier | Significant contribution of germline BRCA2 rearrangements in male breast cancer families[END_REF][START_REF] Vasickova | High occurrence of BRCA1 intragenic rearrangements in hereditary breast and ovarian cancer syndrome in the Czech Republic[END_REF] and consequently two novel BRCA1 rearrangements with unknown boundaries were analyzed. In all cases, the range of the deletion was accurately mapped, which enabled convenient PCR design and amplification of a short junction fragment (less than 1,500 bp) suitable for sequence analysis (Fig. 2). The sample No 609 with deleted exons 21-24 (deletion of 25.639 kb) was tested by both chromosome-specific (median probe spacing ~160 bp) and whole-genome aCGH (median probe spacing ~7000 bp) (Roche NimbleGen). The deletion was identified by chromosomespecific aCGH, while the resolution power of the whole-genome aCGH with lower density of oligonucleotide probes was not satisfactory (data not shown).

In conclusion, analysis performed in 521 high-risk families and patients with non-familial cancer demonstrated that LGRs at the BRCA1 locus account for 12.3% of all disease-causing mutations found in the BRCA1 gene. The two Czech-specific founder mutations, the deletions of exons 1-17 and 5-14, were dominant gene alterations. Our results indicate that screening for LGRs in the BRCA1 gene performed in high-risk families can also be recommended to patients with non-familial cancer; in particular cases with early-onset BC or OC. Screening for LGRs in BRCA2 may be restricted to high-risk families with male breast cancer, in which large rearrangements were identified in several studies. Characterization of deletion breakpoints belongs to essential steps in analysis of LGRs that could be substantially improved by chromosome-specific aCGH suitable for accurate detection of deletion boundaries.

Tables

  for genetic testing was performed between 2002 and 2009 at the Institute of Biology and Medical Genetics, at the Department of Oncology and at the Department of Obstetrics and Gynecology of the First Faculty of Medicine, Charles University in Prague and General University Hospital in Prague. Selection criteria for BRCA1/2 testing followed the national guidelines approved by the Czech Society for Oncology and the Czech Society for Medical Genetics published in 2003 and updated in 2009

  identified in a HBOC family No 1190. With PCR primers located in introns 3 and 10, a fragment of 816 bp was amplified from patient's DNA but not from control DNA. Sequencing of the PCR product ascertained a deletion of 15,552 bp with concurrent insertion of a 35-bp fragment (g.17696_33247del15552ins35). Deletion breakpoints were found in the AluSx and AluJb sequences located in introns 3 and 10, respectively. Inserted fragment corresponded to the reverse complement of the sequence derived from AluY repeat located in intron 3 of BRCA1 (g.18725-18759). Breakpoints were located in a sequence comprising 10 identical nucleotides within AluSx (g.17686-17695) and AluY (g.18760-18769) repeats in intron 3 and a stretch of 29 identical nucleotides located in the AluY (g. 18696-18724) and AluJb (g.33248-33276) repeats in introns 3 and 10, respectively. The complex rearrangement led to the loss of exons 5-10 that caused a shift in the reading frame and truncation of the BRCA1 protein (p.Lys45AsnfsX3).

homologous

  AluY and AluSx sequences in introns 17 and 22 and demonstrated a deletion of 16,316 bp (g.63647_79962del16316). Out of frame deletion of exons 18-22 predicted truncation of the BRCA1 protein (p.Asp1692GlyfsX26). A deletion of exons 21-24 was revealed in a woman from HBC family No 609 with invasive BC diagnosed at the age of 38. Chromosome 17 -specific aCGH analysis localize the deletion breakpoints in intron 20 and in a region of about 18 kb downstream of the BRCA1 stop codon (Fig 2c). Primers were designed to amplify a specific junction fragment of 259 bp from patient's DNA sample. Sequence analysis demonstrated the recombination of nonhomologous sequences leading to the deletion of 25,639 nucleotides and the insertion of a trinucleotide TAG (g.75489-101127del25639insTAG). Due to homozygosity in the coding

exons 5 -

 5 14 and 21-22) were identical in both parts of the country. The Czech-specific mutations, deletions of exons 1-17 and 5-14 in the BRCA1 gene, comprised more than 50% (8/14) of identified LGRs in our study. While the occurrence of exon 1-17 deletion was restricted to the Prague area so far, the deletion of exons 5-14 was also detected four times in Moravia and likely represents the most frequent LGR in the Czech Republic. The complex rearrangement involving deletion of exons 21-22 was identified two times in Moravia and once in our laboratory and may represent further population specific BRCA1 mutation.

Fig. 2

 2 Fig. 2 Breakpoint analysis of three novel genomic rearrangements. Left -copy number analysis at the BRCA1 locus by aCGH. The y-axis indicates log2 ratios of Cy5/Cy3 fluorescent intensity. Red lines represent the results of segMNT analysis. Deleted regions are shown by lower red lines. The schemes show the position and orientation of BRCA1, NBR2 and RND2 genes and position of deleted regions (in red). Genomic locale is from the UCSC genome browser, Mar 2006 assembly. Right -analysis of PCR products on agarose gels and breakpoint verification by sequencing. Carriers of the deletion are indicated by numbers; lane C -negative control; lane M -size standards. Breakpoints are indicated by dashed lines. (a) Alu-mediated 80.5-kb deletion comprising exons 1-17 and the NBR2 gene; (b) Alu-mediated 16.3-kb deletion comprising exons 18-22; (c) a 25.6-kb deletion spanning exons 21-24 and the last three exons of RND2 gene.

Fig. 3

 3 Fig. 3 Breakpoint analysis of a complex genomic rearrangement comprising deletion of exons 5-10 and insertion of 35 nucleotides using LR-PCR (left) and sequencing (right). The carrier of the deletion is indicated by a number; lane C -negative control; lane M -size standards. Breakpoints verified by sequencing are indicated by dashed lines. The upper part of the scheme shows the deleted sequence in red; exons are denoted as red bars; position (out of scale) and orientation of Alu-elements are indicated by arrowheads. Alu-elements involved in rearrangement are labeled. Sequence coordinates are according to the GenBank reference sequence L78833.1. The lower part of the scheme shows sequences upstream and downstream to the breakpoints. Identical sequences, where the recombination events occur, are indicated by vertical lines. The green box highlights an insert of 35-bp. The underlined sequence corresponds to the junction fragment.

Fig. 4

 4 Fig. 4 Breakpoint analysis of a 25.2-kb deletion of exons 13-19 by LR-PCR (left) and sequencing (right). The carrier of the deletion is indicated by a number; lane C -negative control; lane M -size standards. Breakpoints verified by sequencing are indicated by dashed line.

Table 1

 1 Primers used for amplification of junction fragments

	Exon (length of deletion)	Primers (forward and reverse)	Position of primers a/b	Amplified junction fragment	Detection method
	1A-2 (36.934 kb)	1 F: ACCTAAAATTCCTTCTGCTGGAC R: CAAAGAACGACTAACCTGGCA	a 197249-235352	1.2 kb	MLPA, LR-PCR
	1-17 (80.496 kb)	F: TATCCCAGTGACTTTCCAGC R: TGAGAGGGATGGGAGAATAC	a 208205-290011	1.3 kb	MLPA, aCGH, LR-PCR
	5-10 (15.552 kb)	F: AGGCAGTCATGCATTAGTTTG R: CCGTCTCAGAAAATTCACAAG	b 17563-33895	0.8 kb	MLPA, LR-PCR
	5-14 (31.583 kb)	2 F: CCTTACCTACCTACATTCAC R: CTTTATGTAGGATTCAGAGTA	b 19244-54463	3.6 kb	MLPA, LR-PCR
	13-19 (25.201 kb)	F: ACCAGTTTATGCTCTTCCAG R: GCCTATAAGATGCATTCCCT	b 41617-67533	0.7 kb	MLPA, LR-PCR
	18-22 (16.316 kb)	F: GCTCGTGTACAAGTTTGCCAGA R: ATGGAAGCCATTGTCCTCTGTC	b 61040-81093	3.7 kb	MLPA, aCGH, LR-PCR
	21-22 (3.779 kb)	F: AGCATGATTTTGAAGTCAGAGGAG R: GTCCAGGCATCTGGCTGCACAACCACAA	b 71596-81074	5.9 kb	cDNA analysis, LR-PCR
	21-24 (25.639 kb)	F: TTATCTCATAACTAGGCATCC R: TTCCTGAAAGTCCTCAGAGC	b 75369-101263	0.3 kb	MLPA, aCGH, LR-PCR
	1-2 Primers according to 1 Preisler-Adams et al. [16]; 2 Vasickova et al. [22]; a GenBank reference sequence
	NC_000017.9 complement (38300000..38760000); b GenBank reference sequence L78833.1

Table 2

 2 Germline rearrangements in the BRCA1 gene Genomic locale for chromosome 17 is from the UCSC genome browser, Mar 2006 assembly; b GenBank reference sequence L78833.1; c GenBank reference sequence covering the analyzed region: NC_000017.9 complement (38300000..38760000); d Mutation numbering: +1 corresponds to the A of the ATG translation initiation codon in the reference sequence U14680; e BC and/or OC cases in proband and its relatives. Age of onset in proband is indicated in bold underlined numerals; asterisks (*) mark the patient with both BC and OC; ages at diagnosis of bilateral BC cases are separated by a slash (/)

	Exon	Chromosomal breakpoints a , mut. Designation -gDNA b , mut. Designation -cDNA c/d	Predicted mutation effect	Recombination	Patient No.	e (age at diagnosis) BC & OC cases	Other tumors	Reference
	1A-2 a chr17: 38,525,493-38,562,426 b g.197575_234508del 36934	No transcript?	ΨBRCA1/BRCA1	779	BC (58*); OC (51*, 47)	-	7, 14, 34
		c c.1-32787_80+4067del 36934
	1-17	a chr17:38,470,578-38,551,073 b g.208928_289423del 80496 c c.1-21434_5075-1084del 80496	Loss of ~90% of coding sequence	AluY/AluY	206 225 269	BC (28, 50, 50) BC (27); OC (40) BC (35, 36)	Uterus (3x) Colon, lung -	novel
					416	BC (39, 62*); OC (42, 64*)	Lymphoma
	5-10	a chr17:38,501,028-38,516,581 b g.17696_33247del 15552ins35 d c.135-4505_670+361del 15552ins35	p.Lys45Asn fsX3	AluSx/AluY/AluJb 1190	BC (50, 50); OC (46)	-	novel
	5-14	a chr17:38,480,980-38,512,561	p.Lys45_Lys1495del	LINE/-	278	BC (40/41, 63, 69, 35/35)	Pancreas, uterus
		b g.21716_53298del 31583 d c.135-485_4485-913del 31583			453 862	BC (39) BC (44, 48*); OC (60, 64*)	-Prostate	7, 22
					938	BC (32, ?*, ?); OC (?*)	-
	13-19	a chr17:38,467,226-38,492,424 b g.41850-67050del 25201	p.Gln1396_Glu1731del	-/AluSx	571	BC (56/56, 48, 44)	-	novel
		d c.4185+4062_5193+1650del 25201
	18-22	a chr17:38,454,318-38,470,629 b g.63647_79962del 16316 d c.5075-1135_5046+347del 16316	p.Asp1692Gly fsX26	AluY/AluSx	897	BC (35, 64, ?, ?, ?, ?)	-	novel
	21-22	a chr17:38,453,374-38,457,152	p.Ile1760_Thr1802del	AluSx/AluJb	102	OC (36)	-
		b g.77128-80906del 3779ins236 d c.5278-492_5407-128del 3779ins236						22, 23
	21-24 a chr17:38,433,150-38,458,787 b g.75489_101127del 25639 insTAG	No transcript? p.Ile1760 fs	-/-	609	BC (38, ?, ?)	-	novel
		d c.5278-2135_5592+18067del 25639insTAG

a

Table 3

 3 Frequencies of genetic changes in relation to classification of patients and families

	Classification	Number of families/patients	Small mutations in BRCA1 (%)	Small mutations in BRCA2 (%)	LGRs in families in the study (%)	LGRs in families negatively tested for BRCA1/2 mutation (%)
	Mmmmmmmmmmm HBC families	206	26 (12.6)	19 (9.2)	6 (2.9)	6/161 (3.7)
	mmmmmmmmmmm HBOC+HOC families	138	48 (34.8)	12 (8.7)	6 (4.3)	6/78 (7.7)
	mmmzzzzz´,řřřře\ High-risk families	344	74 (21.5)	31 (9.0)	12 (3.5)	12/239 (5.0)
	Sporadic cases	311	26 (8.4)	3 (1.0)	2 (0.6)	2/282 (0.7)
	Overall	655	100 (15.3)	34 (5.2)	14 (2.1)	14/521 (2.7)

HBC, hereditary breast cancer; HBOC, hereditary breast and ovarian cancer; HOC, hereditary ovarian cancer

Table 4

 4 The mean predicted probabilities calculated using BRCAPRO and actual occurrence Five novel deletions in BRCA1 gene identified by MLPA analysis. Control sample is indicated by wt, numbers denote exons of BRCA1, Ccontrol DNA sequences. Arrows indicate exons interpreted as deleted.

	of BRCA1 mutations
	Classification	Number of families/patients	Mutations in BRCA1 (%)	BRCAPRO Mean (± SD) Range
	Mmmmmmmmmmm mmmmmmmmmmm High-risk families	344	86 (25.0)	0.229 (±0.269) 0.001-0.975
	mmmzzzzz´,řřřře\ Sporadic cases	311	28 (9.0)	0.086 (±0.122) 0.001-0.838
	Overall	655	114 (17.4)	0.162 (±0.225) 0.001-0.975

Acknowledgement

We thank Marie Epsteinova for her excellent technical assistance. Special thanks go to Zbynek Halbhuber PhD from KRD Molecular Technologies, who performed experiments with the oligonucleotide-based array CGH technique. This project was supported by the Internal Grant Agency of the Ministry of Health of the Czech Republic, Grant No. NS 10304-3/2009; and the Ministry of Education Youth and Sports Research Project: MSM 0021620808.


Gabriela Arévalo

Stéphane Ducasse

Oscar Nierstrasz

Lessons Learned in Applying Formal Concept Analysis to Reverse Engineering *

A key difficulty in the maintenance and evolution of complex software systems is to recognize and understand the implicit dependencies that define contracts that must be respected by changes to the software. Formal Concept Analysis is a well-established technique for identifying groups of elements with common sets of properties. We have successfully applied FCA to complex software systems in order to automatically discover a variety of different kinds of implicit, recurring sets of dependencies amongst design artifacts. In this paper we describe our approach, outline three case studies, and draw various lessons from our experiences. In particular, we discuss how our approach is applied iteratively in order to draw the maximum benefit offered by FCA.

Introduction

One of the key difficulties faced by developers who must maintain and extend complex software systems, is to identify the implicit dependencies in the system. This problem is particularly onerous in object-oriented systems, where mechanisms such as dynamic binding, inheritance and polymorphism may obscure the presence of dependencies [START_REF] Dunsmore | Object-oriented inspection in the face of delocalisation[END_REF][START_REF] Dekel | Revealing java class structures using concept lattices[END_REF]. In many cases, these dependencies arise due to the application of well-known programming idioms, coding conventions, architectural constraints and design patterns [START_REF] Stata | Modular reasoning in the presence of subclassing[END_REF], though sometimes they may be a sign of weak programming practices.

On the one hand, it is difficult to identify these dependencies in non-trivial applications because system documentation tends to be inadequate or out-of-date and because the information we seek is not explicit in the code [START_REF] Demeyer | Object-Oriented Reengineering Patterns[END_REF][START_REF] Steyaert | Reuse contracts: Managing the evolution of reusable assets[END_REF][START_REF] Lamping | A focus + context technique based on hyperbolic geometry for visualising larges hierarchies[END_REF]. On the other hand, these dependencies play a part in implicit contracts between the various software artifacts of the system. A developer making changes or extensions to an object-oriented system must therefore understand the dependencies among the classes or risk that seemingly innocuous changes break the implicit contracts they play a part in [START_REF] Steyaert | Reuse contracts: Managing the evolution of reusable assets[END_REF]. In short, implicit, undocumented dependencies lead to fragile systems that are difficult to extend or modify correctly.

Due to the complexity and size of present-day software systems, it is clear that a software engineer would benefit from a (semi-)automatic tool to help cope with these problems.

Formal Concept Analysis provides a formal framework for recognizing groups of elements that exhibit common properties. It is natural to ask whether FCA can be applied to the problem of recognizing implicit, recurring dependencies and other design artifacts in complex software systems.

From our viewpoint, FCA is a metatool that we use as tool builders to build new software engineering tools to analyze the software. The software engineer is considered to be the end user for our approaches, but his knowledge is needed to evaluate whether the results provided by the approaches are meaningful or not.

Over the past four years, we have developed an approach based on FCA to detect undocumented dependencies by modeling them as recurring sets of properties over various kinds of software entities. We have successfully applied this approach to a variety of different reverse engineering problems at different levels of abstraction. At the level of classes, FCA helps us to characterize how the methods are accessing state and how the methods commonly collaborate inside the class [START_REF] Arévalo | X-Ray views: Understanding the internals of classes[END_REF]. At the level of the class hierarchy, FCA helps us to identify typical calling relationships between classes and subclasses in the presence of late binding and overriding and superclass reuse [START_REF] Arévalo | Understanding behavioral dependencies in class hierarchies using concept analysis[END_REF]. Finally, at the application level, we have used FCA to detect recurring collaboration patterns and programming idioms [START_REF] Arévalo | Detecting implicit collaboration patterns[END_REF]. We obtain, as a consequence, views of the software at a higher level of abstraction than the code. These high level views support opportunistic understanding [START_REF] Littman | Mental models and software maintenance[END_REF] in which a software engineer gains insight into a piece of software by iteratively exploring the views and reading code.

In this paper we summarize our approach and the issues that must be taken into consideration to apply FCA to software artifacts, we briefly outline our three case studies, and we conclude by evaluating the advantages and drawbacks of using FCA as a metatool for our reverse engineering approaches.

Overview of the Approach

In this section we describe a general approach to use FCA to build tools that identify recurring sets of dependencies in the context of object-oriented software reengineering. Our approach conforms to a pipeline architecture in which the analysis is carried out by a sequence of processing steps. The output of each step provides the input to the next step. We have implemented the approach as an extension of the Moose reengineering environment [START_REF] Ducasse | Moose: an extensible language-independent environment for reengineering object-oriented systems[END_REF].

The processing steps are illustrated in Figure 1. We can briefly summarize the goal of each step as follows:

-Model Import: A model of the software is constructed from the source code.

Source code

Source code model

Elements and Properties

Magnitude Set

Inheritance

Magnitude isAbstract < self send = ... -Post-Filtering: Concepts that are not useful for the analysis are filtered out.

High Level Views

Magnitude

-Analysis: The concepts are used to build the high level views.

A key aspect of our approach is that one must iterate over the modeling and the interpretation phases (see Figure 1). The modeling phase entails a process of experimentation with smaller case studies to find a suitable mapping from the source code model to FCA elements and properties. A particular challenge is to find a mapping that is efficient in terms of identifying meaningful concepts while minimizing the quantity of data that must be processed.

The interpretation phase is the other iterative process in which the output of the modeling phase is analyzed in order to interpret the resulting concepts in the context of the application domain. The useful concepts can then be flagged so that future occurrences can be automatically detected. As more case studies are analyzed, the set of identifiably useful concepts typically increases up to a certain point, and then stabilizes.

We must remark that, from our experiences, there are two main participants in the approach: the tool builder and the software engineer. The tool builder builds the FCA-based tool to generate the high level views, and the software engineer uses the results provided by the tool to analyze a piece of software. Both of them work together in the modeling and interpretation phase of the approach, because software engineer has the knowledge of analyzing a system and the tool builder can represent this knowledge in the tool.

We will now describe each processing step in detail and outline the key issues that must be addressed in order to apply the approach.

Model Import

Description: Our first step is to build a model of the application from the source code. For this purpose we use the Moose reengineering platform, a research vehicle for reverse and reengineering object-oriented software [START_REF] Demeyer | Object-Oriented Reengineering Patterns[END_REF]. Software models in Moose conform to the Famix metamodel [TDDN00], a language-independent metamodel for reengineering. Moose functions both as a software repository for these models, and as a platform for implementing language-independent tools that query and manipulate the models.

Issues: In this step the most important issue is how to map the source code to metamodel entities. The main goal of this step is to have a language-independent representation of the software. In our specific case, we use the Famix metamodel, which includes critical information such as method invocations and attribute accesses. The tool builder can, however, choose any suitable metamodel.

FCA Mapping

Description: In the second step, we need to map the model entities to elements and properties, and we need to produce an incidence table that records which elements fullfil which property. The choice of elements and properties depends on the view we want to obtain.

Issues: This is a critical step because several issues must be considered. Each of these issues is part of the iterative modeling process.

-Choice of Elements: First we must decide which metamodel entities are mapped to FCA elements. This is normally straightforward. In most cases there are some particular metamodel entities that are directly adopted as FCA elements (e.g., classes, methods). Alternatively, a FCA element may correspond to a set of entities (e.g., a set of collaborating classes). -Compact Representation of Data: In some cases, a naïve mapping from metamodel entities to FCA elements may result in the generation of massive amounts of data. In such cases, it may well be that many elements are in fact redundant. For example, if method invocations are chosen as FCA elements, it may be that multiple invocations of the same method do not add any new information for the purpose of applying FCA.

By taking care in how FCA elements are generated from the metamodel, we can not only reduce noise, but we can also reduce the cost of computing the concepts. -Choice of Properties: Once the issue of modeling FCA elements is decided, the next step is to choose suitable properties. Well-chosen properties achieve the goal of distinguishing groups of similar elements. This means that they should neither be too general (so that most elements fulfill them) nor be too specific (so only few elements fulfill them). -Use of negative properties: Nevertheless, in some cases the developer needs still more properties to distinguish the elements. But simply adding more properties may only increase the complexity of the approach. The use of "negative" information (built by negating existing properties) may help. -Single or Multiple FCA Contexts: In some cases, multiple FCA contexts may be required. For example, in the XRay views case study, one context was used to analyze state and another to analyze behavior. -Computation of properties or elements: When building the FCA context of a system to analyze, there are two alternatives for the FCA mapping. In an one-to-one mapping, the developer directly adopts metamodel entities and metamodel relationships as FCA elements and properties respectively. In a many-to-one the developer builds more complex FCA elements and properties by computing them from the metamodel entities and relationships, meaning for example that an FCA element can be composed of several metamodel entities, or an FCA property must be calculated based on metamodel relationships between different entities. This issue is one of the bottlenecks in the total computation time of the approach, because the incidence table must be computed in this step and if the FCA property must be calculated, this time can also compromise the total computation time.

ConAn Engine

Description: Once the elements and properties are defined, we run the ConAn engine. The ConAn engine is a tool implemented in VisualWorks 7 which runs the FCA algorithms to build the concepts and the lattice. ConAn applies the Ganter algorithm [START_REF] Ganter | Formal Concept Analysis: Mathematical Foundations[END_REF] to build the concepts and our own algorithm to build the lattice [START_REF] Arévalo | High Level Views in Object Oriented Systems using Formal Concept Analysis[END_REF].

Issues: In this step, there are two main issues to consider -Performance of Ganter algorithm: Given an FCA Context C = (E, P, I), the Ganter algorithm has a time complexity of O(|E| 2 |P |). This is the second bottleneck of the approach because in our case studies the number of FCA elements is large due to the size of the applications. We consider that |P| is not a critical factor because in our cases studies the maximum number of properties is 15. -Performance of Lattice Building Algorithm: Our algorithm is the simplest algorithm to build the lattice but the time complexity is O(n 2 ) where n is the number of concepts calculated by Ganter algorithm. This is the last bottleneck of the approach. -Unnecessary properties: It may happen that certain properties are not held by any element. Such properties just increase noise, since they will percolate to the bottom concept of the lattice, where we have no elements and all properties of the context.

Post-Filtering

Description: Once the concepts and the lattice are built, each concept constitutes a potential candidate for analysis. But not all the concepts are relevant. Thus we have a post-filtering process, which is the last step performed by the tool. In this way we filter out meaningless concepts.

Issues: In this step, there are two main issues to consider:

-Removal of Top and Bottom Concepts: The first step in post-filtering is to remove the top and bottom concepts. Neither provides useful information for our analysis because each one usually contains an empty set. (The intent is empty in the top concept and the extent is empty in the bottom concept). -Removal of meaningless concepts: This step depends on the interpretation we give to the concepts. Usually concepts with only a single element or property are candidates for removal because the interesting characteristic of the approach is to find groups of elements sharing common characteristics. Concepts with only a single element occur typically in nodes next to the bottom of the lattice, whereas concepts with only one property are usually next to the top of the lattice.

Analysis

Description: In this step, the software engineer examines the candidate concepts resulting from the previous steps and uses them to explore the different implicit dependencies between the software entities and how they determine or affect the behavior of the system Issues: In this step, there are several issues to consider. All of them are related to how the software engineer interprets the concepts to get meaningful or useful results.

-Concept Interpretation based on Elements or Properties: Once the lattice is calculated, we can interpret each concept C = ({E 1 . . . E n }, {P 1 . . . P m }) using either its elements or its properties. If we use the properties, we try to associate a meaning to the conjunction of the properties. On the other hand, if we focus on the elements, we essentially discard the properties and instead search for a domain specific association between the elements (for example, classes being related by inheritance). -Equivalent Concepts: When we interpret the concepts based on their properties, we can find that the meaning of several concepts can be the same. This means that for our analysis, the same meaning can be associated to different sets of properties. -Automated Concept Interpretation: The interpretation of concepts can be transformed into an automatic process. Once the software engineer establishes a meaning for a given concept, this correspondence can be stored in a database. The next time the analysis is performed on another case study, the established interpretations can be retrieved and automatically applied to the concepts identified. Once this process is finished, the software engineer must still check those concepts whose meaning has not been identified automatically. -Using Partial Order in the Lattice: The concepts in the lattice are related by a partial order. During analysis, the software engineer should evaluate if it is possible to interpret the partial order of the lattice in terms of software relationships. This means that the software engineer should only not interpret the concepts but also the relationships between them. -Limit of using FCA as a grouping technique: When additional case studies fail to reveal new meaningful concepts, then the application of FCA has reached its limit. At this point, the set of recognized concepts and their interpretations can be encoded in a fixed way, for example, as logical predicates over the model entities, thus fully automating the recognition process and bypassing the use of FCA.

High Level Views in Reverse Engineering

Using the approach we have introduced in the previous section, we have generated different views at different abstraction levels for object oriented applications. We present each analysis according to a simple pattern: Reengineering Goal, FCA Mapping, High Level Views, Validation, Concrete Examples and Issues. Reengineering Goal introduces the analysis goal of the corresponding high level view. FCA Mapping explains which are the chosen elements and properties of the context for the analysis. High level view presents how the concepts are read to interpret which of them are meaningful or not for our analysis and how we use them to build the corresponding high level views. Validation summarizes some results of the case studies. Concrete Examples presents some examples found in the specific case study. Issues summarizes briefly which were the main issues taken into account to build the high level view.

Understanding a Class: XRay Views

Reengineering Goal: The goal is to understand the internal workings of a class by capturing how methods call each other and how they collaborate in accessing the state. We focus on analyzing a class as an isolated development unit [START_REF] Arévalo | X-Ray views: Understanding the internals of classes[END_REF].

FCA Mapping: The elements are the methods (labelled m or n) and the attributes (labelled a) of the class, and the properties, are:

-m reads or writes the value of a -m calls via-self n in its body -m is abstract in its class -m is concrete in its class -m is an "interface" (not called in any method defined in the same class) -m is "stateless" (doesn't read or write any attribute defined in the class)

High Level Views: A XRay view is a combination of concepts that exposes specific aspects of a class. We have defined three XRay views: State Usage, External/Internal Calls and Behavioural Skeleton. These three views address different but logically related aspects of the behavior of a class.

State Usage focuses on how the behavior accesses the state of the class, and what dependencies exist between groups of methods and attributes. This view helps us to measure the class cohesion [START_REF] Briand | A unified framework for cohesion measurement in object-oriented systems[END_REF] revealing whether there are methods using the state partially or totally and whether there are attributes working together to provide different functionalities of the class.

Behavioural Skeleton focuses on methods according to whether or not they work together with other methods defined in the class or whether or not they access the state of the class. The way methods form groups of methods that work together also indicates how cohesive the class is [START_REF] Briand | A unified framework for cohesion measurement in object-oriented systems[END_REF].

External/Internal Calls focuses on methods according to their participation in internal or external invocations. Thus, this view reveals the overall shape of the class in terms of its internal reuse of functionality. This is important for understanding framework classes that subclasses will extend. Interface methods, for example, are often generic template methods, and internal methods are often hook methods that should be overridden or extended by subclasses.

Validation: We have applied the XRay views to three Smalltalk classes: OrderedCollection (2 attributes, 54 methods), Scanner (10 attributes, 24 methods) and UIBuilder (18 attributes, 122 methods). We chose these particular three classes because they are different enough in terms of size and functionality and they address well-known domains. In general terms, we discovered that in OrderedCollection most of the methods access all the state of the class, that there is little local behavior to be reused or extended by subclasses because the class works with inherited methods, and there are few collaborations among the methods.

UIBuilder is a class where most of the methods are not invoked in the class itself, meaning the internal behavior is minimal, and we have a large interface. This class offers a lot of functionality to build complex user interface and also several ways to query its internal state.

In Scanner, the collaboration between methods occurs in pairs and there are no groups of methods collaborating with other groups.

Concrete Examples:

We illustrate this case study with the XRay State Usage found in the Smalltalk class OrderedCollection. This view is composed of several concepts, and it clusters attributes and methods according to the way methods access the attributes. The motivation for this view is that, in order to understand the design of a class, it is important to gain insight into how the behaviour accesses the state, and what dependencies exist between groups of methods and attributes. This view helps us to measure the cohesion of the class [START_REF] Briand | A unified framework for cohesion measurement in object-oriented systems[END_REF], thereby revealing any methods that use the state partially or totally and any attributes that work together to provide different functionalities of the class.

Some of the concepts occurring in State Usage are the following:

-{before, removeAtIndex:, add:beforeIndex:, first, removeFirst, removeFirst:, addFirst } reads or writes {firstIndex } represents the Exclusive Direct Accessors of firstIndex.

-{after, last, removeIndex:, addLastNoCheck:, removeLast, addLast:, removeLast: } reads or writes {lastIndex } represents the Exclusive Direct Accessors of lastIndex -{makeRoomAtFirst, changeSizeTo:, removeAllSuchThat:, makeRoomAtLast, do:, notEmpty:, keysAndValuesDo:, detect:ifNone:, changeCapacityTo:, isEmpty, size, remove:ifAbsent:, includes:, reverseDo:, find:, setIndices, insert: before:, at:, at:put:, includes: } reads or writes {firstIndex, lastIndex } represents the Collaborating Attributes -Stateful Core Methods = the same set as Collaborating Attributes

Before analysing the concepts identified by this view, we posed the hypothesis that the two attributes maintain an invariant representing a memory zone in the third anonymous attribute. From the analysis we obtain the following points:

-By browsing Exclusive Direct Accessors methods, we confirm that the naming conventions used help the maintainer to understand how the methods work with the instance variables, because we see that the method removeFirst accesses firstIndex and removeLast: accesses lastIndex. -The numbers of methods that exclusively access each attribute are very similar, however, we discover (by inspecting the code) that firstIndex is mostly accessed by readers, whereas lastIndex is mostly accessed by writers. -It is worth noting that Collaborating Attributes are accessed by the same methods that are identified as Stateful Core Methods. This situation is not common even for classes with a small number of attributes, and reveals a cohesive collaboration between the attributes when the class is well-designed and gives a specific functionality, in this specific case, dealing with collections. -We identified 20 out of 56 methods in total that systematically access all the state of the class. By further inspection, we learned that most of the accessors are readers.

There are only five methods, makeRoomAtFirst, makeRoomAtLast, setIndices, insert:before:, and setIndicesFrom:, that read and write the state at the same time. More than half of the methods (33 over 56) directly and indirectly access both attributes. This confirms the hypothesis that the class maintains a strong correlation between the two attributes and the anonymous attribute of the class.

All these facts confirm the hypothesis that the class maintains a strong correlation between the two attributes and the anonymous attribute of the class.

Issues: We mention some important issues about this approach.

-Choice of elements and properties. Elements and properties are mapped directly from the metamodel: the elements are attributes and methods, and the properties are accesses to attributes and calls to methods. -Compact representation of data. Supposing you have two methods m and n and one attribute a, if we have several calls to the method n or accesses to the attribute a in the method body of m, we just keep one representative of n and a related to the method m.

-Multiple FCA contexts. In this case, we have used two lattices. The first one is used to analyze the state of the class and the second one is used to analyze the invocations of the class. We did not combine this information in a single lattice because we consider them to be completely different aspects of the class. -Unnecessary properties. In some classes, the following properties isAbstract, isStateless, isInterface are discarded. This is normal because in any given class, it commonly occurs that all methods are concrete, or that all the methods access the state, or that most methods are called inside the class. -Meaningless concepts. We discarded concepts with a single method in the set of elements, because we were more focused on groups of methods (represented in the elements) collaborating with another group of methods (represented in the properties).

Analyzing Class Hierarchies: Dependency Schemas

Reengineering Goal: Using the state and behavior of a class we analyze the different recurring dependencies between the classes of a hierarchy. They help us to understand which are the common and irregular design decisions taken when the hierarchy was built, and possible refactorings that were carried out [START_REF] Arévalo | Understanding behavioral dependencies in class hierarchies using concept analysis[END_REF].

FCA Mapping:

The elements are the accesses to any attribute defined in any classes of the hierarchy, and the called methods in any class of the hierarchy. If i is an invoked method or accessed attribute, and C, C 1 , C 2 are classes, the properties are grouped as follows:

-Kind of calls: C invokes i via self and C invokes i via super -Location of accessed state: i accesses { local state, state in Ancestor C 1 , state in Descendant C 1 } -Kind and Location of invoked method: { is abstract, is concrete, is cancelled } × { locally, in ancestor

C 1 of C , in descendant C 1 of C }
High Level Views: A dependency schema is a recurring set of dependencies (expressed with the properties of the concepts) over methods and attributes in a class hierarchy. We have identified 16 dependency schemas that are classified as:

Classical schemas representing common idioms/styles that are used to build and extend a class hierarchy.

Bad Smell schemas representing doubtful designs decisions used to build the hierarchy. They are frequently a sign that some parts should be completely changed or even rewritten from scratch.

Irregularity schemas representing irregular situations used to build the hierarchy. Often the implementation can be improved using minimal changes. They are less serious than bad smell schemas.

Thus we see that the dependency schemas can be a good basis for identifying which parts of a system are in need of repair. These schemas can be used in two different ways: Either we obtain the global view of the system and which kinds of dependencies and practices occur when analyzing a complete hierarchy, or we get detailed information about how specific classes are related to others in their hierarchy by restricting the analysis to just those classes.

Validation: We have validated dependency schemas in three Smalltalk class hierarchies: Collection (104 classes distributed in 8 inheritance levels, 2162 methods, 3117 invocations, 1146 accesses to the state of the classes), Magnitude and Model. Collection is an essential part of the Smalltalk system and it makes use of subclassing for different purposes. In this class hierarchy, the most used classical schemas are (1) the reuse of superclass behavior, meaning concrete methods that invokes superclass methods by self or super, (2) local behavior, meaning methods defined and used in the class that are not overridden in the subclasses and (3) local direct access, meaning methods that directly access the class state. In general terms, this means that the classes define their own state and behavior but they exhibit heavy superclass reuse. Within bad smell schemas, the most common is the ancestor direct state access meaning methods that directly access the state of an ancestor, bypassing any accessors. This is not a good coding practice since it violates class encapsulation. Within irregularity schemas the most common case is that of inherited and local invocations where methods are invoked by both self and super sends within the same class. This may be a problem if the super sends are invoked from a method with a different name. This is an irregular case because the class is overriding the superclass behavior but is indirectly using the superclass behavior.

Concrete Examples:

We illustrate this case study with the schema named Broken super send Chain, which is categorized as a Bad Smell schema. It was found in the analysis of the Smalltalk class OrderedCollection.

Within the "Bad Smell" category, we have the schema Broken super send Chain (shown in Figure 2). It is composed of the following elements and properties:

- This schema identifies methods that are extended (i.e., performing a super send) in a class but redefined in their subclasses without calling the overridden behavior, thus giving the impression of breaking the original extension logic. In SortedCollection the methods = and representBinaryOn: invoke hidden superclass methods. But the definitions of these methods in the subclass SortedCollectionWithPolicy do not invoke the super methods defined in Sorted-Collection. Such a behavior can lead to unexpected results when the classes are extended.

C
Issues: We mention some important issues about this approach.

-Choice of Elements and Properties. We map the attribute accesses and method calls directly from the metamodel. The choice of properties requires some analysis, because we need to cover the different possible inheritance relationships of the elements. The properties in the category Kinds of calls are mapped directly from the metamodel the rest of the properties are calculated based on the relationships expressed in the metamodel. -Single context. In this case, we just use only one lattice, because we analyze only one aspect of classes: inheritance relationships.

Collaborations Patterns on Applications

Reengineering Goal: We analyze the different patterns used in a system using structural relationships between classes in a system. We call them Collaboration Patterns and they show us not only classical design patterns [START_REF] Gamma | Design Patterns: Elements of Reusable Object-Oriented Software[END_REF] but any kind of repeated patterns of hidden contracts between the classes, which may represent design patterns, architectural constraints, or simply idioms and conventions adopted for the project. With these patterns, we analyze how the system was built and which are the main constraints it respects [START_REF] Arévalo | Detecting implicit collaboration patterns[END_REF]. This approach refines and extends that which was proposed by Tonella and Antoniol [START_REF] Tonella | Object oriented design pattern inference[END_REF] for detecting classical design patterns.

FCA Mapping: The elements are tuples composed of classes from the analyzed application. The order refers to length of the tuples. In our cases, we have experimented with order 2, 3 and 4. The properties are relations inside one class tuple, and are classified as binary and unary properties. The binary property characterizes a relationship between two classes inside the tuple, and the unary property gives a characteristic of a single class in the tuple. Given a tuple composed of classes (C 1 , C 2 , .....C n ), the properties are:

-Binary property: For any i, j,

1 ≤ i, j ≤ n, C i is subclass of C j , C i accesses C j , C i has as attribute C j , C i invokes C j , C i uses locally C j -Unary property: For any i, 1 ≤ n, C i is abstract, C i is root, C i is singleton, C i has local defined method.
High Level Views: The concepts are composed of groups of tuples of classes that share common properties. The conjunction of these properties characterizes the pattern that all the tuples in the concept represent. Each meaningful concept represents a candidate for a pattern. Based on our case studies using tuples of classes of length 3 and 4, we have identified 8 collaboration patterns. 4 of 8 patterns exhibit the structural relationships of known design patterns (Facade, Composite, Adapter and Bridge). The rest of the identified patterns called Subclass Star, Subclass Chain, Attribute Chain and Attribute Star show the relationships among classes based on inheritance or on invocations, but not combined at the same time. The frequency of the patterns helps the developer to identify coding style applied in the application. The most interesting contribution of this high level view is the possibility of establishing a called pattern neighbourhoods over detected patterns. With the neighbours of the patterns, we can detect either missing relationships between classes needed to complete a pattern, or excess relationships between classes that extend a pattern. We can also analyze the connections of the identified patterns with the classes implemented in the analyzed application.

Validation:

We have investigated the collaboration patterns in three Smalltalk applications: (1) ADvance2 (167 classes, 2719 methods, 14466 lines of code) is a multidimensional OOAD-tool for supporting object-oriented analysis and design, reverse engineering and documentation, (2) SmallWiki3 (100 classes, 1072 methods, 4347 lines of code) is a new and fully object-oriented wiki implementation in Smalltalk and (3) CodeCrawler4 (81 classes, 1077 methods, 4868 lines of code) is a language independent software visualization tool. These three applications have different sizes and complexity. We briefly summarize some results related to coding styles. We have seen that frequency and the presence of a pattern in a system is besides domain specific issues of coding style. 4).

Pattern Subclass Chain in order = 3 is described with the following properties: C 3 is subclass of C 2 , {C 2 is subclass of C 1 , C 1 is abstract}, and in order = 4 the property C 4 is subclass of C 3 is added. Pattern Attribute Chain in order = 3 is described with the following properties: {C 1 invokes C 2 , C 2 invokes C 3 and C 1 is abstract}, and in order = 4 the property C 3 invokes C 4 is added. Pattern Composite (shown in the Figure 3) is described with the following properties: The first two patterns help us to analyze some coding styles used in CodeCrawler. We have found 25 instances of 3 classes (order = 3) of Attribute Chain but no instances of 4 classes (order = 4). This means that in this application the developer has used at most 3 levels of delegation between the classes. Thus, if we detect a case of delegation in a method in a class in CodeCrawler, we are sure that this delegation will relate 2 or 3 classes. In the case of Subclass Chain, we have found 11 instances of 3 classes (order = 3) but only 3 instances of 4 classes (order = 4). This means that in this application most of hierarchies have 3 levels of inheritance and only some of them have 4 levels of inheritance. This is a symptom that the application uses flat hierarchies in its implementation. Related to the idea of pattern neighbourhood, as we have said exploring the neighbours of a pattern is important to detect all candidates for a classical pattern. For example, we have found the Abstract Composite pattern of order o = 3 of the ADvance application. We have detected two Abstract Composite patterns, but in the neighborhood we find four more Composite patterns without an abstract composite root.

{C 2 is subclass of C 1 , C 3 is subclass of C 1 , C 3 invokes C 1 , C 1 is abstract}.
Issues: We mention some important issues about this approach.

-Choice of elements and properties. Elements are tuples of classes built from the metamodel. As our case study refines the work of Tonella and Antoniol [START_REF] Tonella | Object oriented design pattern inference[END_REF] we use the same idea to build the elements. The choice of properties is the set of the structural relationships to characterize Structural Design Patterns [START_REF] Gamma | Design Patterns: Elements of Reusable Object-Oriented Software[END_REF]. Except the properties is subclass of and is abstract that are mapped directly from the metamodel, the rest of properties are computed from the metamodel. -Compact representation of data. This issues is related to how the tuples of classes are generated. We avoid generating all permutations of class sequences in the tuples. For example, if the tuple (C A P) is generated, and we subsequently generate (A P C) or (C P A), we only keep one of these as being representative of all three alternatives. -Multiple Contexts. In this case, we have used 3 lattices. Each lattice is for one order of the elements: 2, 3 and 4. All use the same set of properties. -Performance of the algorithm. With the tuples of classes of order more than 4, we are not able to have a reasonable computation time of the algorithm. With one of the applications using tuples of classes of order 4, the computation time took around 2 days and this is not acceptable time from our viewpoint to software engineering. -Meaningless concepts. As we said previously, each concept is a candidate for a pattern.

In this case, each concept represents a graph in which the set of the elements is the set of nodes, and the set of properties define the edges that should connect the nodes, e.g., if (A P C) has the properties A is subclass of P and P uses C, then we have a graph of 3 nodes with edges from A to P and from P to C. Thus we discarded all the concepts that represent graphs in which one or several nodes are not connected at all with any node in the graph. -Mapping Partial Order of the Lattice. In this case, we map the partial order of the lattice to the definition of neighbours of a pattern. We can detect either missing relationships between classes needed to complete a pattern, or excess relationships between classes that extend a pattern. -Limits of Collaboration Patterns. In this high level view, we consider that there are still possible new collaboration patterns to detect when applying the approach in other applications.

Lessons Learned

In general terms, we have seen that Formal Concept Analysis is a useful technique in reverse engineering. From our experiencies [Aré03, ABN04, ADN03] in developing this approach, several lessons learned are worthwhile mentioning.

Lack of a general methodology. The main problem we have found in the state of the art is the lack of a general methodology for applying FCA to the analysis of software. In most publications related to software analysis, the authors only mention the FCA mapping as a trivial task, and how they interpret the concepts. With our approach, we achieved not only to identify clear steps for applying FCA to a piece of software but where we have identified different bottlenecks in using the technique.

Modelling software entities as FCA components. The process of modelling software entities as FCA components is one of most difficult tasks and we consider it as one of the critical steps in the approach. Modelling is an iterative process in which we map software entities to FCA components, and we test whether they are useful enough to provide meaningful results. This task is not trivial at all, because it entails testing at least 5 small case studies (which should be representative of larger case studies). Each case study should help to refine the building of FCA components.

Performance of FCA algorithms. Part 1 The performance of the algorithms (to build the concepts and lattice) was one of main bottlenecks. In small case studies, this factor can be ignored because the computation time is insignificant. But in large case studies this factor can cause the complete approach to fail because computing the concepts and the lattice may take several hours (eventually days).

Performance of FCA algorithms. Part 2 The computation of the FCA algorithms is also affected by how they are implemented in a chosen language. A direct mapping of the algorithms (in pseudo-code, as they are presented in books) to a concrete programming language is not advisable. In our specific case, we took advantage of efficient data structures in Smalltalk language to represent the data and improve the performance.

Supporting Software Engineers. The result of our experiences must be read by software engineers. One positive issue in this point is that with the high level views the software engineer is not obliged to read the concept lattices , meaning that he need not be a FCA expert.

Interpretation of the concepts. Although we can have an adequate choice of FCA elements and properties, the interpretation of the concepts is a difficult and time-consuming task. In most of the cases, we have tried to associate a meaning (a name) to each concept based on the conjunction of its properties. This task must be done by a software engineer applying opportunistic code reading to get meaningful interpretations. This process is completely subjective because it depends on the knowledge and experience of the software engineer.

Use of the Complete Lattice. Not all the concepts have a meaning in our approach, so we do not use the complete lattice in our analysis. In most of the cases, we remove meaningless concepts because from software engineering viewpoint they did not provide enough information for the analysis. We hypothesize that in certain cases it may be possible to use the complete lattice, but we did not find any.

Use of the Partial Order. Another critical factor is the interpretation of the partial order of the lattice in terms of software relationships. Only in Collaboration Patterns we were able to obtain a satisfactory interpretation of the partial order. So far, the interpretation is not a trivial task.

Related Work

Several researchers have also applied FCA to the problem of understanding object oriented software. Dekel uses CA to visualize the structure of the class in Java and to select an effective order for reading the methods and reveal the state usage [START_REF] Dekel | Revealing java class structures using concept lattices[END_REF]. Godin and Mili [GMM + 98] use concept analysis to maintain, understand and detect inconsistencies in the Smalltalk Collection hierarchy. They show how Cook's [START_REF] William | Interfaces and specifications for the Smalltalk-80 collection classes[END_REF] earlier manual attempt to build a better interface hierarchy for this class hierarchy (based on interface conformance) could be automated. In C++, Snelting and Tip [START_REF] Snelting | Reengineering class hierarchies using concept analysis[END_REF] analysed a class hierarchy making the relationship between class members and variables explicit. They were able to detect design anomalies such as class members that are redundant or that can be moved into a derived class. As a result, they propose a new class hierarchy that is behaviorally equivalent to the original one. Similarly, Huchard [START_REF] Huchard | Galois lattice as a framework to specify algorithms building class hierarchies[END_REF] applied concept analysis to improve the generalization/specialization of classes in a hierarchy. Tonella and Antoniol [START_REF] Tonella | Object oriented design pattern inference[END_REF] use CA to detect the structure of Gamma-style design patterns using relationships between classes, such as inheritance and composition.

Conclusions and Future Work

In this paper we present a general approach for applying FCA in reverse engineering of object oriented software. We also evaluate the advantages and drawbacks of using FCA as a metatool for our reverse engineering approaches. We also identify the different bottlenecks of the approach. Thus, we are able to focus clearly on solving which and where the limitations appear (if there are some possible solutions) to draw the maximum benefit offered by FCA.

From our tool builder viewpoint, we have proven that FCA is an useful technique to identify groups of software entities with hidden dependencies in a system. With FCA, we have built different software engineering tools that help us to generate high level views at different levels of abstraction of a system. We generate the high level views because without them, the software engineer should be obliged to read the lattice. This can represent a problem because in most of the cases, besides the useful information, the lattice can also have useless information that can introduce noise in analyzing a system.

Our future work is focused on several research directions that consist of: (1) the development of new case studies to analyze how useful the approach is or if there are still some refinements and improvements to do, (2) Testing with other concept and lattice building algorithms to see if we can improve the computation time of the ConAn engine and(3) Analysis of the partial order to get possible mappings in terms of software engineering relationships.

Figure 1 :

 1 Figure 1: The overall approach

Figure 2 :

 2 Figure 2: Broken super send Chain

Figure 4 :

 4 Figure 3: Composite Pattern

  =} has concrete behavior in ancestor SequenceableCollection of SortedCollection.-i is concrete in descendant C 1 of C : {representBinaryOn:, =} has concrete behavior in descendant SortedCollectionWithPolicy of SortedCollection.

invokes i via super : {representBinaryOn:, =} are super-called in SortedCollection -i is concrete locally: {representBinaryOn:, =} has concrete behavior in SortedCollection.

-i is concrete in ancestor C 1 of C : {representBinaryOn:,

  In our case studies we have seen that CodeCrawler has a lot of Subclass Star and Facade patterns, whereas SmallWiki has a lot of Attribute Chain and Attribute Star patterns. Advance is the only application with the Composite pattern. We illustrate this case study showing two collaboration patterns named Attribute Chain and Subclass Chain that were found in the tool CodeCrawler (shown in the Figure

	Concrete Examples:

We prefer to use the terms element and property instead of the terms object and attribute in this paper because the terms object and attribute have a very specific meaning in the object oriented programming paradigm.

http://www.io.com/ icc/

http://c2.com/cgi/wiki?SmallWiki

http://www.iam.unibe.ch/ scg/Research/CodeCrawler/index.html

Acknowledgments. We gratefully acknowledge the financial support of the Swiss National Science Foundation for the projects "Tools and Techniques for Decomposing and Composing Software" (SNF Project No. 2000-067855.02), and Recast: Evolution of Object-Oriented Applications (SNF 2000-061655.00/1).