BACKGROUND
eukaryotes can enhance their repertoire of different protein products by alternative splicing of the corresponding genes  <cit> .
since the first description of alternative splicing of precursor mrna almost  <dig> years ago  <cit>  the suggested and verified percentage of human genes that are spliced into alternative transcripts has steadily risen .
very recently, two studies using high-throughput sequencing indicate that every single human gene containing more than one exon is transcribed and processed to yield multiple mrnas  <cit> .
mainly, five different types of alternative splicing affect the resulting translated protein product  <cit> : the first type is exon skipping, in which an exon, also called cassette exon, is spliced out of the transcript together with its flanking introns.
the second and third types are the alternative splicing of the 3' splice site and 5' splice site, respectively.
here, two or more splice sites are recognized at one end of the exon.
the fourth type is intron retention in which part of an exon is either spliced  or retained in the mature mrna transcript.
while exon skipping and alternative 3' splice site selection account for most alternative splicing events in higher eukaryotes  <cit> , the most prevalent type of alternative splicing in plants, fungi, and protozoa is intron retention  <cit> .
the fifths type is called mutually exclusive splicing and is used for clusters of internal exons that are spliced in a mutually exclusive manner.
it is important to note that the term mutually exclusive splicing is only used for these specific clusters of exons.
mutually exclusive splicing demands a specific mechanism for the regulated splicing of exactly one of the exons of such a cluster.
recent analyses have shown that this mechanism might be based on intra-intronic rna pairings that are conserved at the secondary structure level  <cit> .
these alternatively spliced exons must not be mixed up with exons that seem to be spliced in a mutually exclusive manner based on their annotation.
this especially accounts for terminal exons that are alternatively spliced in conjunction with the use of alternative promoters or 3'-end processing sites .
the regulation of the splicing of these types need not be at the level of splicing.
to our knowledge, the only study to identify and predict regions in silico that might contain mutually exclusive spliced exons used a method of local similarity of genomic regions at the nucleotide level  <cit> .
assuming that clusters of mutually exclusive exons evolved by one or several rounds of single-exon duplications, given gene locations were self-aligned using a pairwise local alignment algorithm to derive similar regions.
those regions were regarded as candidate regions, and mutually exclusive exons were only predicted by verification through est and cdna data.
the method itself cannot determine exons including intron splice sites, and is not able to identify mutually exclusive exons whose dna sequences have diverged considerably.
false positive candidates are detected in regions that contain clusters of duplicated genes, and in regions containing pseudo-exons .
here, we propose a different approach that is based on the knowledge of creating meaningful transcripts.
we presume that most mutually exclusive exons encode the same region of the resulting protein structure.
these regions are embedded in the surrounding three-dimensional structure and thus alternative exons must preserve all structurally important contacts between the corresponding local structure elements.
a demonstrative example is the alternatively spliced motor domain of the muscle myosin heavy chain in arthropods  <cit> .
in drosophila, four clusters of mutually exclusive spliced exons encode regions of the motor domain, and the variability of creating different transcripts and further fine-tune the motor domain function is even enhanced in the waterflea daphnia magna by four additional clusters.
one of the clusters contains exons encoding the so-called relay helix and subsequent relay loop, a structural element that starts at switch- <dig> embedded in the middle of the motor domain and ends at the connection to the converter domain.
this whole relay element converts small conformational changes at the atp-binding site to large movements of the lever arm  <cit> .
retaining structural integrity is therefore indispensible for mutually exclusive exons.
of course, parts of the exons might also encode loop regions, but also those parts must at least partly be conserved to retain their general function.
based on these preconditions we apply the following constrains to our search for mutually exclusive exons: a) mutually exclusive exons must have about the same length .
b) they must have conserved splice site patterns  and the reading frame of the exon must be conserved.
c) they must show sequence similarity.
these features have been implemented in an extension to the webscipio software.
the application of the algorithm to various genes from several eukaryotes, and to all genes of the x chromosome of drosophila melanogaster is demonstrated.
methods
the search algorithm has been implemented as an extension to the webscipio web application  <cit> .
it is based on the exon-intron gene structure reconstructed by scipio  <cit> .
the extension is written in the ruby programming language  <cit>  and fully integrated into webscipio to facilitate user interaction, and visualization and analysis of the results.
webscipio uses the web framework ruby on rails  <cit> .
to make the session storage fast, flexible, and scalable a database backend consisting of tokyo cabinet and tokyo tyrant  <cit>  is used.
to run jobs in background the rails plug-in workling in combination with spawn  <cit>  is applied.
search algorithm
the new algorithm divides into several steps, which are executed for each original exon .
it assumes that mutually exclusive spliced exons share the following features: firstly, mutually exclusive spliced exons have a similar length; secondly, their splice sites and reading frames are conserved; thirdly, they are homologous.
for each internal exon  the two surrounding introns  are scanned for exon candidates that have a similar length.
these exon candidates must introduce introns with the following splice site pattern: gt---ag, gc---ag, gg---ag, and at---ac.
firstly, the algorithm looks for the nucleotide pairs ag or ac in the intron sequence, which define start sites of exon candidates and 3' splice sites of the proposed intron.
if the intron in front of the original exon starts with gt, gc or gg the algorithm searches for ag, if it starts with an at the algorithm searches for ac.
secondly, the algorithm looks for the nucleotide pairs gt, gc, gg and at in the intron sequence, which define ends of exon candidates and 5' splice sites of the proposed intron.
if the intron following the original exon ends with ag the algorithm searches for gt, gc and gg, if it ends with ac the algorithm searches for at.
the nucleotide sequences between two possible 3' and 5' splice sites of the scanned intron that have a length similar to the length of the original exon are considered as exon candidates.
the maximum length difference between an exon and its candidate can be adjusted by the allowed length difference parameter in number of amino acids.
the default value of this parameter is  <dig> aa.
for terminal exons, the algorithm is able to scan the up- and downstream regions of the gene for exon candidates.
the first exon of a protein-coding gene has to start with the start codon atg.
thus, for the first exon, alternative candidates must start with atg instead of sharing a theoretical splice site pattern with the first exon.
the last exon is followed by a stop codon  and all exon candidates must be followed by a stop codon instead of sharing a splice site pattern with the last exon.
the use of the start codon and stop codon instead of the splice sites can be adjusted by the search with start codon for first exon and search with stop codon for last exon parameters.
for example it would be useful to release this restriction in the case where the algorithm searches for alternative exons in a protein fragment.
the default of these parameters is to search with a start codon if the first amino acid of the user-provided protein query sequence starts with methionine, and to search with stop codons if the last exon is followed by a stop codon.
to reduce the number of candidates it is possible to set the minimal exon length parameter.
original exons, which are shorter than this length, are not considered in the candidate search.
the default value for this parameter is  <dig> aa.
the nucleotide sequences of the exon candidates are translated into amino acid sequences using the bioruby library  <cit> .
the candidates are translated in the same reading frame as the original exon, because their nucleotide sequences appear mutually exclusive in the resulting mrna and thus share the same reading frame.
if the translation results in an in-frame stop codon, the candidate is rejected.
each candidate sequence is aligned to the original exon sequence.
if the alignment score is high, the probability that the two exons are homologous is high as well.
the optimal global alignment of the two amino acid sequences is calculated with the gotoh algorithm, which extends the needleman-wunsch algorithm by affine gap costs  <cit> .
for this task, the pair_align program of the seqan package  <cit>  is used.
the gap penalties are set to - <dig> for initial gaps and - <dig> for extending gaps.
the blosum <dig> matrix is used as substitution matrix  <cit> .
because of differences in length and amino acid composition of the clusters of mutually exclusive exons the resulting global alignment scores are not directly comparable.
to normalise the alignment scores each score is divided by the score of the alignment of the original exon sequence to itself.
this relative score shows the similarity of the two sequences on a scale from zero to one.
candidates, which have a low alignment score, are rejected.
the threshold for rejection can be adjusted in percent by the minimal score for exons parameter .
if candidate regions overlap the highest scoring candidates are retained or, if scores are identical, the longest candidates.
an optional recursive search was implemented to find less similar alternative exons.
if this option is selected, the search is repeated with the found alternatively spliced exons as query exons.
the number of recursive runs can be adjusted with the maximal recursion depth parameter up to three rounds of recursion .
webscipio integration
the webscipio tool allows reconstructing an exon-intron gene structure based on a protein sequence query.
this reconstruction step is the basis for the mutually exclusive spliced exon search.
the user can enable the search and adjust several parameters in the advanced options section of webscipio.
the search will run subsequently to the gene structure reconstruction step.
in addition, the user can enable the search after uploading a previously calculated and downloaded scipio result.
the result of the search is displayed in the result section of the webscipio interface .
the standard gene structure picture is extended by the predicted mutually exclusive spliced exons.
the alternative exons corresponding to the same original exon constitute a cluster.
exons of a cluster get the same colour.
the original exon is dark coloured and the corresponding predicted ones are lighter coloured depending on their similarity with respect to the original exon.
in the statistics section the number of exons in each cluster is shown in colour.
the alignment view  offers a detailed analysis at the sequence level.
for each alternative exon the genomic sequence, its translation, and the alignment to the original translated exon are shown.
the alignment score is given in percent.
the alternative exons are also marked in the genomic dna result view.
in the coding dna and translation result view the user can choose the alternative exons that should build the alternative coding dnas or protein sequences.
the results can be downloaded in several data formats.
the yaml file contains all corresponding information and can later be uploaded and used for future analysis  <cit> .
additionally, the results can be downloaded as general feature format  file  <cit> .
the figures can be downloaded in the scalable vector graphics  format for further high quality processing  <cit> .
example searches as well as further descriptions of the search parameters are provided on the help pages of webscipio.
RESULTS
identification of mutually exclusive spliced exons
the search for mutually exclusive spliced exons is based on three criteria:  the lengths of the mutually exclusive exons must be very similar, because these exons are supposed to code for the same part in the resulting protein structure, including identical secondary structural elements.
to be spliced in a mutually exclusive way, the exons must have similar splice sites and reading frames to be compatible with the previous and following exons.
the exons must encode homologous protein sequences, because their inclusion into the protein structure must be compatible with the corresponding local structural environment.
the search implemented in webscipio is based on the availability of the gene structure.
firstly, mutually exclusive exon candidates are searched for using corresponding splice sites to the query exons and restricting the candidate length to similar reading frames .
total length difference is less restricted allowing length differences between query and candidate exons at the dna level in multiples of three for each additional or missing codon.
these candidate exons are then filtered and scored based on the blosum <dig> matrix.
the best scoring, non-overlapping candidates are proposed to be alternative exons to the respective query exon, resulting in a cluster of mutually exclusive exons.
with this approach, the absolute necessary constraints at the dna-level that can be obtained by bioinformatics means are combined with biological information.
based on these criteria several cases can be distinguished:  alternative exons found in the surrounding introns of single internal exons should form true clusters of mutually exclusive exons,  alternative exons found for terminal exons most probably constitute multiple promoters or multiple poly sites,  clusters of several exons in combination, which can be found by searching for candidates for all exons in all introns and up- and downstream regions, most probably represent cases of tandemly arrayed gene duplications or trans-spliced genes.
example genes with clusters of mutually exclusive exons
to test the quality of the new algorithm, several well-known genes with clusters of mutually exclusive exons with different characteristics were analysed .
the first test case is the cytoplasmic dynein heavy chain from schistosoma mansoni .
dynein heavy chains belong to the longest genes in eukaryotes encoding  <dig> -  <dig> residues and are spread over several dozens of exons.
the mutually exclusive exon is clearly identified in the middle of the gene, encoding split codons at the 3'- and 5'-end of the exon.
the query exon and the candidate exon have identical lengths and show strong homology.
based on the multiple sequence alignment of more than  <dig> dhcs these exons are mutually exclusive and not constitutive or differentially included.
the second case represents the muscle myosin heavy chain gene from the waterflea daphnia magna  <cit> .
the arthropod muscle myosin heavy chain genes contain several clusters of mutually exclusive exons to fine tune the mechanochemical characteristics of the motor domain that are needed to accomplish the different tasks in the various muscle types  <cit> .
the dapmhc <dig> is an example with nine clusters of mutually exclusive exons of which several are adjacent and not interrupted by constitutive exons.
the new algorithm found all mutually exclusive exons that have manually been identified previously  <cit> .
the two example alignments show that the new algorithm is able to correctly identify even short exons with limited complexity, and subsequent clusters of mutually exclusive exons encoded in different reading frames.
the third example shows the prediction of the mutually exclusive exons in dscam  from drosophila melanogaster, which is known to encode the largest set of mutually exclusive exons of any gene analysed so far  <cit> .
the potentially  <dig> mutually exclusive exons of the dscam gene are organized into four clusters that are separated by constitutive exons.
the exon  <dig>   <dig>   <dig>  and  <dig> clusters are supposed to contain  <dig>   <dig>   <dig>  and  <dig> exons, respectively  <cit> .
in the publicly available drosophila melanogaster reference genome sequence  mutually exclusive exons were searched using a gene translation containing the first exons of each of the clusters as query sequence.
if clusters contain that many exons as are found in the dscam genes it might be possible that the exon, that has been included in the query sequence, is the most divergent of the exons of the cluster.
therefore, a parameter to the search algorithm that enforces recursive searches in all introns with the newly identified exon candidates was introduced.
exons that might not be identified in the first round might then be found in the second, third, or later round.
of course, the recursive depth should not be too large to avoid the inclusion of false positive exons because of the decreasing stringency of the query exons.
including every first exon of the dscam mutually exclusive exon clusters in the query sequence, all twelve exons of the exon  <dig> cluster were identified, both exons of the exon  <dig> cluster, and  <dig> and  <dig> exons for the exon  <dig> and exon  <dig> cluster, respectively .
increasing the recursive depth to one also revealed exon  <dig> , which is the most divergent exon of the cluster, and which has not been detected in transcriptome studies yet  <cit> .
exon  <dig>  was not identified because the intron before exon  <dig>  does not have an "ag" at the 3'-end and is therefore not compatible with the "gt" at the 5'-end of the intron succeeding exon  <dig>  the supposed 5'-end sequence of exon  <dig>  is different to the published sequence  <cit>  but is supported by many genomic dna reads available from genbank .
exon  <dig>  was also not identified because it contains a frame shift in the drosophila reference genome assembly, supported by many genomic dna reads.
therefore, the translations of the predicted transcripts containing exon  <dig>  all stop shortly behind this frame shift .
however, both exon  <dig>  and exon  <dig>  were identified in many transcripts  <cit> .
thus, either the genome assembly based on the many genomic dna reads is wrong, which is unlikely, or the many est/cdna-reads are wrong, which is also unlikely, or the genomic dna has been obtained from a different strain than the one that has been used in the transcriptome studies.
webscipio is, however, not able to identify mutually exclusive exons if those do not correspond to the exon length  and corresponding splice site restrictions.
the strength of the new algorithm is illustrated at the exon  <dig> cluster that encodes two highly divergent but mutually exclusive spliced exons .
when applying the search for mutually exclusive exons in the dscam gene against the published genomic sequence  all proposed  <dig> mutually exclusive exons were identified .
less mutually exclusive exons in the search against the drosophila melanogaster reference genome sequence compared to the search against the published sequence are therefore not due to problems with the search algorithm.
a
a
dm = drosophila melanogaster; dse = drosophila sechellia rob3c; dy = drosophila yakuba tai18e2; der = drosophila erecta tsc#14021- <dig> ; da = drosophila ananassae tsc#14024- <dig> ; dp = drosophila pseudoobscura mv2-25; drp = drosophila persimilis msh-3; dw = drosophila willistoni tsc#14030- <dig> ;
dmo = drosophila mojavensis tsc#15081- <dig> ; dv = drosophila virilis tsc#15010- <dig> ; dg = drosophila grimshawi tsc#15287- <dig> .
a genomes are fragmented and contain gaps in the dscam genes.
b the first number corresponds to a search with standard parameters, the second to searches with one round of recursion.
c one of the exons is a pseudo-exon because it misses the last forth of the exon because of an in-frame stop codon.
in addition, mutually exclusive exons in the dscam genes of the other sequenced drosophila species were searched .
here, all mutually exclusive exons were found immediately, and only three further exons were identified by a second recursive round of exon search.
as found for the drosophila melanogaster gene, webscipio identified sometimes more sometimes less exons compared to the published analyses  <cit> .
however, the webscipio searches were performed against the official reference genome assemblies, while the published analyses were based on manually performed genomic clone assemblies of the dscam gene regions.
therefore, the differences in exon numbers do not result from shortcomings of the search algorithm, but from differences in the assembly of the reference genome data and the manually assembled genomic regions.
example genes encoding 5'- and 3'-terminal exons with features of mutually exclusive spliced exons
terminal exons are often not selected at the level of splicing.
instead, initial  exons are most probably selected at the level of transcription that starts at different promoters.
terminal exons  might either be spliced as differentially included exons, like in the case of the drosophila muscle myosin heavy chain gene  <cit> , or as multiple poly sites.
nevertheless, these terminal exons might contain an important structural part of the encoded protein and thus often have similar length and show sequence similarity.
figure  <dig> shows two examples of genes that contain 5'- and 3'-terminal exons sharing the described features of mutually exclusive exons, but are spliced as multiple promoters or multiple poly sites.
the silver protein of drosophila melanogaster illustrates a case where two initial exons, which are transcribed/spliced as multiple promoters, share the features of mutually exclusive exons.
the capping protein beta  from homo sapiens represents a case where homologous 3'-terminal exons containing multiple poly sites are found.
the detection of these cases can be suppressed by disabling the search for mutually exclusive exons for 5'- and 3'-terminal exons.
by default, webscipio enables the search for homologous exons for all exons, because it is not known whether the user is searching with a complete, partial or fragmented query sequence.
in the case of partial and fragmented sequences the search would provide significant results.
also, genes sometimes contain untranslated 5'- and/or 3'-terminal exons whereby the first translated exon could well be part of a cluster of mutually exclusive spliced exons.
in addition, alternative terminal exons by themselves might provide interesting perspectives to the corresponding genes independently of whether they are mutually exclusively spliced or not.
webscipio cannot distinguish between the described cases and thus the user has to be careful when alternative terminal exons are proposed.
detection of trans-spliced genes and arrays of tandem gene duplications
the trans-splicing of separate pre-mrnas involving coding exons to reveal a joined transcript is a relatively uncommon event  <cit> .
in general, trans-spliced genes in drosophila melanogaster can be distinguished into those with multiple first exons or multiple 3'-terminal exons, or those with very large introns.
many of the trans-spliced genes contain variable single terminal exons   <cit>  or lola  <cit> ) or alternative terminal exon groups .
when searching for mutually exclusive spliced exons based on one of the annotated isoforms of a trans-spliced gene potentially alternative exons of internal exons might be identified.
an example of the trans-spliced drosophila melanogaster gene cg <dig> is shown in figure 4a.
three isoforms of the cg <dig> gene exist  that result in transcripts of a common 5' exon spliced to isoform-specific sets of three 3' exons.
the sequences of the isoform-specific sets are homologous although the intron positions are different between the isoform a/b exons and the isoform c exons.
when searching with the isoform a exons for mutually exclusive exons in surrounding introns the homologous exon of isoform b is found for the first of the three isoform a-specific exons .
when only searching in surrounding introns  further exons are not found for isoform b  and for isoform c .
thus, if only isoform a were known a mutually exclusive exon would have been proposed.
to avoid the mis-annotation of exons of trans-spliced clusters a parameter was introduced that allows searching for candidate exons not only in the neighbouring introns but also in all introns.
in figure 4a-iv the exons of isoform b were identified by searching with the exons of isoform a in all introns revealing the trans-spliced nature of the cluster.
if searching in up- and downstream regions for alternatively spliced exons, it is possible that candidate exons belong to gene duplicates .
in this case, the webscipio option to search for candidates in all introns including up- and downstream regions and not only in surrounding introns helps identifying exons of gene duplications.
in many cases, gene duplications result in genes arranged in tandem.
those gene duplicates often share the complete gene structure meaning that for every exon there is a corresponding exon in the duplicated gene.
figure 4b illustrates this behaviour and provides means by which users can judge between a true cluster of mutually exclusive exons belonging to one gene and a set of duplicated genes.
if the search for candidate exons is only allowed in surrounding introns, a set of six homologous exons is found for the drosophila melanogaster gene cg <dig> .
performing the search in all introns results in five homologous exons also for the second exon of the cg <dig> gene, and shows one homologous exon for exon  <dig> .
the first exons of the genes seem to be very divergent.
allowing one additional recursive round of candidate search reveals the first exons for two additional gene homologs .
in addition lowering the score reveals the exon  <dig> candidates of the remaining two gene homologs, although two further regions with very low homology to exon  <dig> appear in the upstream region of the cg <dig> gene .
this example illustrates the use of the search parameters so that gene duplications can be identified.
gene duplicates that are not arranged in tandem but are distributed in the genome do not provide problems in evaluating exon candidates, because the search is restricted to a certain size of the up- and downstream regions.
if needed, these gene duplicates can be identified with webscipio using the general multiple results option.
application of the search algorithm for mutually exclusive exons to genome scale data
the described search algorithm identifies three types of exons as described above:  mutually exclusive exons,  terminal exons that are spliced as multiple promoters or multiple poly sites but share similar length, reading frame, and sequence homology, and  exons with the characteristics of mutually exclusive exons that are actually part of tandemly arrayed gene duplicates or groups of alternative exons in trans-spliced genes.
type b and type c exons are false positives, when looking for mutually exclusive exons.
in addition, false positive exons are those exons that show all characteristics of type a exons but are constitutively or differentially included spliced.
false negatives exons, which are not identified by webscipio, are those mutually exclusive exons that do not have similar length and sequence homology.
to quantify the amount of each of these exon types we searched the complete x chromosome of the fruit fly drosophila melanogaster for mutually exclusive spliced exons with webscipio and compared the results to the flybase annotation.
protein sequences for the search were obtained from the flybase annotation  and mapped to the genomic sequence of the x chromosome using scipio.
<dig>  transcripts containing more than one exon were derived from  <dig>  genes.
for each exon mutually exclusive alternative splice variants have been searched for in the surrounding introns.
the search parameters were set to  <dig> amino acids for the allowed length difference, to 15% for the minimal score for exons, and to  <dig> amino acids for the minimal exon length.
we did not search for alternative exons in up- and downstream regions of genes, and we did not apply the recursive search, which means the repeated search for further alternative exons with the newly identified exons that we demonstrated for dscam .
three genes  g <dig>  cg <dig>  and cg42249), in which mutually exclusive exons were found, were excluded from the analysis, because the respective exons are spliced in a mutually exclusive manner in groups of two, three, and four exons, instead of single exons within a cluster.
those genes are probably trans-spliced .
search for non-mutually exclusive exons sharing similar length, same reading frame, and sequence homology
it could well be possible that internal exons with similar length, same reading frame, and showing sequence homology are not mutually exclusive spliced exons, but constitutive exons or exons spliced by one of the other types of alternative splicing.
to get a statistically relevant number of these types of exons we collected all genes of the drosophila melanogaster x chromosome containing at least two exons based on the flybase annotation version  <dig> .
the transcripts of each gene were analysed independently because alternative splicing produces different exon neighbours.
thus exons are counted for each transcript  even if the transcripts have the same start and end points in the genomic sequence.
in total, the  <dig>  transcripts of the drosophila melanogaster x chromosome include  <dig>  exons.
all neighbouring exons were compared with respect to having similar length , sharing high similarity , coding for at least fifteen amino acids , and encoding the same reading frame.
the results are summarized in table  <dig> .
only  <dig> % of the non-mutually exclusive exons  share the features of mutually exclusive exons.
these exons are located in only six genes out of  <dig> .
in one of the six genes  the two homologous exons are terminal exons and would represent a case of multiple poly sites if alternatively spliced.
this analysis shows that the chance that the exons predicted by webscipio as mutually exclusive exons will later  be reannotated as constitutive or differentially included exons, is very low.
a
a exons  which share similar length, same reading frame and sequence homology
search for mutually exclusive spliced exons in the drosophila melanogaster x chromosome
some categories have to be defined to separate true  mutually exclusive spliced exons from predicted ones and false positives and false negatives.
as real mutually exclusive exons we regard those with the following criteria: an exon is part of a cluster of mutually exclusive spliced exons if each transcript of the gene contains exactly one exon of the cluster , the cluster contains at least two exons, the exons of the cluster are neighbouring exons, and the cluster is surrounded by further exons.
the latter criterion distinguishes the mutually exclusive spliced exons from clusters of initial exons  and 3'-terminal exons that are spliced in a mutually exclusive manner and share sequence similarity, similar length, and splice site conservation.
in contrast to real mutually exclusive spliced exons the exons of these clusters appear mutually exclusive in the transcripts but their transcription and splicing is regulated in a different way.
these clusters are therefore regarded as types of multiple promoters and types of multiple poly sites, and are false positives.
other types of false positives are those exons that are predicted by webscipio but overlap with already annotated exons and do not match exactly the positions of these exons.
false negatives are those exons that do not meet the preconditions of similar length and sequence homology.
however, if those exons are mutually exclusive spliced they must have conserved splice sites and reading frames.
in total,  <dig> exons of similar length, same splice sites and reading frames, and sequence homology have been identified by webscipio, of which  <dig> are potentially in clusters of mutually exclusive exons,  <dig> in clusters of multiple promoters, and  <dig> in clusters of multiple poly sites .
of the  <dig> exons predicted to belong to internal clusters of mutually exclusive spliced exons,  <dig> exons are already annotated in flybase.
<dig> exons are predictions by webscipio that have not been described before.
these  <dig> exons are distributed into  <dig> clusters that belong to  <dig> genes.
thus, there are several clusters with more than two alternative exons, and one gene with two clusters.
if the flybase based annotation is assumed to represent true mutually exclusive exons, the chart represents the specificity of our method.
the  <dig> already known mutually exons divided by  <dig> predicted exons result in 40% specificity.
however, the value for the specificity is misleading because it depends on the "known" mutually exclusive exons.
we expect that many of the additional exons predicted by webscipio will be experimentally confirmed in the future and thus will become "known" mutually exclusive exons.
the true specificity will therefore be much higher than the value of 40% suggests.
to analyse whether the additional exons predicted by webscipio contain general features of exons , the found exons were compared to those of an ab initio prediction performed by augustus  <cit>  .
in many cases the webscipio predictions are supported by the ab initio prediction, which is based on the genomic sequence alone.
the augustus prediction matches  <dig> of the  <dig> exons with exact exon borders  and overlaps with  <dig> of them .
the results show that about 70% of all predicted exons  comprise clusters of internal mutually exclusive exons.
the false positive prediction of 5'- and 3'-terminal exons as mutually exclusive exons, which comprise the remaining 30% of predicted exons, could even be suppressed by a webscipio option.
we can also conclude that webscipio correctly identifies all but one  of the annotated mutually exclusive exons.
this suggests that most of the webscipio predictions of new mutually exclusive exon candidates will also be real mutually exclusive exons.
this is supported by the ab initio exon prediction by augustus that showed exon probability for about 50% of the newly predicted exons, which is comparable to the ab initio prediction of the already annotated exons.
however, we cannot completely exclude the possibility that some of the newly predicted exons might in truth be constitutive or differentially included exons .
false negatives would be those mutually exclusive spliced exons that do not share a similar length and sequence similarity.
to figure out how often clusters of mutually exclusive exons with such characteristics exist in comparison to mutually exclusive exons with similar length and sequence similarity, all internal clusters of exons on the x chromosome that were annotated as mutually exclusive based on flybase transcripts were manually analysed .
of the annotated genes only the phosphorylase kinase γ gene contains two mutually exclusive spliced exons that do not have similar length and sequence .
if the flybase annotation is assumed as true, the chart in figure  <dig> represents the sensitivity of the algorithm.
<dig> predicted mutually exclusive spliced exons divided by  <dig> annotated exons results in 93% sensitivity for internal exons.
these data likely indicate that not many mutually exclusive spliced exons will be missed given the constraints of similar length and sequence similarity as implemented in webscipio.
mutually exclusive exons predicted for 5'- and 3'-terminal exons were regarded as false positives because these rather present cases of multiple promoters, multiple poly sites, and differentially included exons.
however, additional untranslated terminal exons might exist that were not analysed here, and in those cases the exons, based on the translation predicted as terminal, become internal and thus true mutually exclusive exons.
for comparison all terminal exons annotated as transcribed or spliced in a mutually exclusive manner have been analysed .
of the  <dig> terminal exons only  <dig> terminal exons share the features of mutually exclusive spliced exons.
a reason for the sequence and length variability of terminal exons is that the n- and c-termini of proteins are not as restricted in their structure as internal parts.
thus, the number of false positives predicted by webscipio is rather low.
future developments and applications
due to the precondition that mutually exclusive exons encode the same part of the protein product, we also want to include the comparison of the prediction of secondary structural elements for the query and the candidate exons as an additional scoring, analysis, and validation parameter.
also, other substitution matrices might be offered for the scoring of the aligned query and candidate exons.
scipio and webscipio have been shown to be suitable for the prediction of genes in cross-species searches  <cit> .
of course, both approaches can be combined and users can search, for example, with a human protein query sequence in other mammals to identify homologous genes and simultaneously predict mutually exclusive exons in the target sequence.
because the search for mutually exclusive exons relies on the translation of the exons as found in the genomic dna, it does not depend on the initial query sequence but on the quality of the exons identified in the cross-species search.
another application would be to search for mutually exclusive spliced genes in the complete genomes of sequenced eukaryotes.
CONCLUSIONS
the extension of webscipio to search for mutually exclusive exons is based on the precondition that these exons encode regions of the same structural part of the protein product.
this precondition provides restrictions to the search for candidate exons concerning their length, splice site conservation and reading frame preservation, and overall homology.
the implemented algorithm has been shown to identify all known mutually exclusive spliced exons in many example genes from various species, like the muscle myosin heavy chain gene of daphnia pulex or the dscam gene of drosophila melanogaster.
the search for homologs of terminal exons might, however, result in the prediction of multiple promoters, multiple poly sites, groups of trans-spliced exons, or tandemly arrayed gene duplicates, and can therefore optionally be disabled.
to quantify the quality of webscipio to correctly predict already annotated mutually exclusive exons and to predict so far unrecognized exon candidates, an analysis of the whole x chromosome of drosophila melanogaster has been performed.
all but two of the  <dig> annotated mutually exclusive exons were found by webscipio.
in addition, webscipio predicts  <dig> new mutually exclusive exon candidates of which about 50% are supported by an ab initio exon prediction by augustus.
in conclusion, webscipio should be able to identify mutually exclusive spliced exons in any query sequence from any species with a very high probability.
abbreviations
dhc: dynein heavy chain; dscam: down syndrome cell adhesion molecule; gff: general feature format; mhc: myosin heavy chain; svg: scalable vector graphics; yaml: yaml ain't markup language
authors' contributions
hp, fo, and mk set the requirements for the system.
hp and kh wrote the software.
fo assisted in and supervised the implementation of the software.
bh implemented improvements to the software, and kh committed the final version.
kh performed the whole chromosome search and evaluation.
hp, kh, bh, and mk performed extensive testing.
kh and mk wrote the manuscript.
all authors read and approved the final version of the manuscript.
supplementary material
additional file 1
detailed activity diagram.
the detailed activity diagram shows each step of the search algorithm including points of decision and loops.
click here for file
additional file 2
search for non-mutually exclusive exons sharing similar length, same reading frame and sequence homology.
the file provides detailed information of the found genes and their gene structures.
click here for file
acknowledgements
mk has been funded by grants ko 2251/3- <dig>  ko 2251/3- <dig>  and ko 2251/6- <dig> of the deutsche forschungsgemeinschaft.

 eukaryotes can enhance their repertoire of different protein products by alternative splicing of the corresponding genes. since the first description of alternative splicing of precursor mrna almost years ago the suggested and verified percentage of human genes that are spliced into alternative transcripts has steadily risen. very recently, two studies using high-throughput sequencing indicate that every single human gene containing more than one exon is transcribed and processed to yield multiple mrnas. mainly, five different types of alternative splicing affect the resulting translated protein product: the first type is exon skipping, in which an exon, also called cassette exon, is spliced out of the transcript together with its flanking introns. the second and third types are the alternative splicing of the 3' splice site and 5' splice site, respectively. here, two or more splice sites are recognized at one end of the exon. the fourth type is intron retention in which part of an exon is either spliced or retained in the mature mrna transcript. while exon skipping and alternative 3' splice site selection account for most alternative splicing events in higher eukaryotes, the most prevalent type of alternative splicing in plants, fungi, and protozoa is intron retention. the fifths type is called mutually exclusive splicing and is used for clusters of internal exons that are spliced in a mutually exclusive manner. it is important to note that the term mutually exclusive splicing is only used for these specific clusters of exons. mutually exclusive splicing demands a specific mechanism for the regulated splicing of exactly one of the exons of such a cluster. recent analyses have shown that this mechanism might be based on intra-intronic rna pairings that are conserved at the secondary structure level. these alternatively spliced exons must not be mixed up with exons that seem to be spliced in a mutually exclusive manner based on their annotation. this especially accounts for terminal exons that are alternatively spliced in conjunction with the use of alternative promoters or 3'-end processing sites. the regulation of the splicing of these types need not be at the level of splicing. to our knowledge, the only study to identify and predict regions in silico that might contain mutually exclusive spliced exons used a method of local similarity of genomic regions at the nucleotide level. assuming that clusters of mutually exclusive exons evolved by one or several rounds of single-exon duplications, given gene locations were self-aligned using a pairwise local alignment algorithm to derive similar regions. those regions were regarded as candidate regions, and mutually exclusive exons were only predicted by verification through est and cdna data. the method itself cannot determine exons including intron splice sites, and is not able to identify mutually exclusive exons whose dna sequences have diverged considerably. false positive candidates are detected in regions that contain clusters of duplicated genes, and in regions containing pseudo-exons. here, we propose a different approach that is based on the knowledge of creating meaningful transcripts. we presume that most mutually exclusive exons encode the same region of the resulting protein structure. these regions are embedded in the surrounding three-dimensional structure and thus alternative exons must preserve all structurally important contacts between the corresponding local structure elements. a demonstrative example is the alternatively spliced motor domain of the muscle myosin heavy chain in arthropods. in drosophila, four clusters of mutually exclusive spliced exons encode regions of the motor domain, and the variability of creating different transcripts and further fine-tune the motor domain function is even enhanced in the waterflea daphnia magna by four additional clusters. one of the clusters contains exons encoding the so-called relay helix and subsequent relay loop, a structural element that starts at switch- embedded in the middle of the motor domain and ends at the connection to the converter domain. this whole relay element converts small conformational changes at the atp-binding site to large movements of the lever arm. retaining structural integrity is therefore indispensible for mutually exclusive exons. of course, parts of the exons might also encode loop regions, but also those parts must at least partly be conserved to retain their general function. based on these preconditions we apply the following constrains to our search for mutually exclusive exons: a) mutually exclusive exons must have about the same length. b) they must have conserved splice site patterns and the reading frame of the exon must be conserved. c) they must show sequence similarity. these features have been implemented in an extension to the webscipio software. the application of the algorithm to various genes from several eukaryotes, and to all genes of the x chromosome of drosophila melanogaster is demonstrated. methods the search algorithm has been implemented as an extension to the webscipio web application. it is based on the exon-intron gene structure reconstructed by scipio. the extension is written in the ruby programming language and fully integrated into webscipio to facilitate user interaction, and visualization and analysis of the results. webscipio uses the web framework ruby on rails. to make the session storage fast, flexible, and scalable a database backend consisting of tokyo cabinet and tokyo tyrant is used. to run jobs in background the rails plug-in workling in combination with spawn is applied. search algorithm the new algorithm divides into several steps, which are executed for each original exon. it assumes that mutually exclusive spliced exons share the following features: firstly, mutually exclusive spliced exons have a similar length; secondly, their splice sites and reading frames are conserved; thirdly, they are homologous. for each internal exon the two surrounding introns are scanned for exon candidates that have a similar length. these exon candidates must introduce introns with the following splice site pattern: gt---ag, gc---ag, gg---ag, and at---ac. firstly, the algorithm looks for the nucleotide pairs ag or ac in the intron sequence, which define start sites of exon candidates and 3' splice sites of the proposed intron. if the intron in front of the original exon starts with gt, gc or gg the algorithm searches for ag, if it starts with an at the algorithm searches for ac. secondly, the algorithm looks for the nucleotide pairs gt, gc, gg and at in the intron sequence, which define ends of exon candidates and 5' splice sites of the proposed intron. if the intron following the original exon ends with ag the algorithm searches for gt, gc and gg, if it ends with ac the algorithm searches for at. the nucleotide sequences between two possible 3' and 5' splice sites of the scanned intron that have a length similar to the length of the original exon are considered as exon candidates. the maximum length difference between an exon and its candidate can be adjusted by the allowed length difference parameter in number of amino acids. the default value of this parameter is aa. for terminal exons, the algorithm is able to scan the up- and downstream regions of the gene for exon candidates. the first exon of a protein-coding gene has to start with the start codon atg. thus, for the first exon, alternative candidates must start with atg instead of sharing a theoretical splice site pattern with the first exon. the last exon is followed by a stop codon and all exon candidates must be followed by a stop codon instead of sharing a splice site pattern with the last exon. the use of the start codon and stop codon instead of the splice sites can be adjusted by the search with start codon for first exon and search with stop codon for last exon parameters. for example it would be useful to release this restriction in the case where the algorithm searches for alternative exons in a protein fragment. the default of these parameters is to search with a start codon if the first amino acid of the user-provided protein query sequence starts with methionine, and to search with stop codons if the last exon is followed by a stop codon. to reduce the number of candidates it is possible to set the minimal exon length parameter. original exons, which are shorter than this length, are not considered in the candidate search. the default value for this parameter is aa. the nucleotide sequences of the exon candidates are translated into amino acid sequences using the bioruby library. the candidates are translated in the same reading frame as the original exon, because their nucleotide sequences appear mutually exclusive in the resulting mrna and thus share the same reading frame. if the translation results in an in-frame stop codon, the candidate is rejected. each candidate sequence is aligned to the original exon sequence. if the alignment score is high, the probability that the two exons are homologous is high as well. the optimal global alignment of the two amino acid sequences is calculated with the gotoh algorithm, which extends the needleman-wunsch algorithm by affine gap costs. for this task, the pair_align program of the seqan package is used. the gap penalties are set to - for initial gaps and - for extending gaps. the blosum matrix is used as substitution matrix. because of differences in length and amino acid composition of the clusters of mutually exclusive exons the resulting global alignment scores are not directly comparable. to normalise the alignment scores each score is divided by the score of the alignment of the original exon sequence to itself. this relative score shows the similarity of the two sequences on a scale from zero to one. candidates, which have a low alignment score, are rejected. the threshold for rejection can be adjusted in percent by the minimal score for exons parameter. if candidate regions overlap the highest scoring candidates are retained or, if scores are identical, the longest candidates. an optional recursive search was implemented to find less similar alternative exons. if this option is selected, the search is repeated with the found alternatively spliced exons as query exons. the number of recursive runs can be adjusted with the maximal recursion depth parameter up to three rounds of recursion. webscipio integration the webscipio tool allows reconstructing an exon-intron gene structure based on a protein sequence query. this reconstruction step is the basis for the mutually exclusive spliced exon search. the user can enable the search and adjust several parameters in the advanced options section of webscipio. the search will run subsequently to the gene structure reconstruction step. in addition, the user can enable the search after uploading a previously calculated and downloaded scipio result. the result of the search is displayed in the result section of the webscipio interface. the standard gene structure picture is extended by the predicted mutually exclusive spliced exons. the alternative exons corresponding to the same original exon constitute a cluster. exons of a cluster get the same colour. the original exon is dark coloured and the corresponding predicted ones are lighter coloured depending on their similarity with respect to the original exon. in the statistics section the number of exons in each cluster is shown in colour. the alignment view offers a detailed analysis at the sequence level. for each alternative exon the genomic sequence, its translation, and the alignment to the original translated exon are shown. the alignment score is given in percent. the alternative exons are also marked in the genomic dna result view. in the coding dna and translation result view the user can choose the alternative exons that should build the alternative coding dnas or protein sequences. the results can be downloaded in several data formats. the yaml file contains all corresponding information and can later be uploaded and used for future analysis. additionally, the results can be downloaded as general feature format file. the figures can be downloaded in the scalable vector graphics format for further high quality processing. example searches as well as further descriptions of the search parameters are provided on the help pages of webscipio.  identification of mutually exclusive spliced exons the search for mutually exclusive spliced exons is based on three criteria: the lengths of the mutually exclusive exons must be very similar, because these exons are supposed to code for the same part in the resulting protein structure, including identical secondary structural elements. to be spliced in a mutually exclusive way, the exons must have similar splice sites and reading frames to be compatible with the previous and following exons. the exons must encode homologous protein sequences, because their inclusion into the protein structure must be compatible with the corresponding local structural environment. the search implemented in webscipio is based on the availability of the gene structure. firstly, mutually exclusive exon candidates are searched for using corresponding splice sites to the query exons and restricting the candidate length to similar reading frames. total length difference is less restricted allowing length differences between query and candidate exons at the dna level in multiples of three for each additional or missing codon. these candidate exons are then filtered and scored based on the blosum matrix. the best scoring, non-overlapping candidates are proposed to be alternative exons to the respective query exon, resulting in a cluster of mutually exclusive exons. with this approach, the absolute necessary constraints at the dna-level that can be obtained by bioinformatics means are combined with biological information. based on these criteria several cases can be distinguished: alternative exons found in the surrounding introns of single internal exons should form true clusters of mutually exclusive exons, alternative exons found for terminal exons most probably constitute multiple promoters or multiple poly sites, clusters of several exons in combination, which can be found by searching for candidates for all exons in all introns and up- and downstream regions, most probably represent cases of tandemly arrayed gene duplications or trans-spliced genes. example genes with clusters of mutually exclusive exons to test the quality of the new algorithm, several well-known genes with clusters of mutually exclusive exons with different characteristics were analysed. the first test case is the cytoplasmic dynein heavy chain from schistosoma mansoni. dynein heavy chains belong to the longest genes in eukaryotes encoding - residues and are spread over several dozens of exons. the mutually exclusive exon is clearly identified in the middle of the gene, encoding split codons at the 3'- and 5'-end of the exon. the query exon and the candidate exon have identical lengths and show strong homology. based on the multiple sequence alignment of more than dhcs these exons are mutually exclusive and not constitutive or differentially included. the second case represents the muscle myosin heavy chain gene from the waterflea daphnia magna. the arthropod muscle myosin heavy chain genes contain several clusters of mutually exclusive exons to fine tune the mechanochemical characteristics of the motor domain that are needed to accomplish the different tasks in the various muscle types. the dapmhc is an example with nine clusters of mutually exclusive exons of which several are adjacent and not interrupted by constitutive exons. the new algorithm found all mutually exclusive exons that have manually been identified previously. the two example alignments show that the new algorithm is able to correctly identify even short exons with limited complexity, and subsequent clusters of mutually exclusive exons encoded in different reading frames. the third example shows the prediction of the mutually exclusive exons in dscam from drosophila melanogaster, which is known to encode the largest set of mutually exclusive exons of any gene analysed so far. the potentially mutually exclusive exons of the dscam gene are organized into four clusters that are separated by constitutive exons. the exon and clusters are supposed to contain and exons, respectively. in the publicly available drosophila melanogaster reference genome sequence mutually exclusive exons were searched using a gene translation containing the first exons of each of the clusters as query sequence. if clusters contain that many exons as are found in the dscam genes it might be possible that the exon, that has been included in the query sequence, is the most divergent of the exons of the cluster. therefore, a parameter to the search algorithm that enforces recursive searches in all introns with the newly identified exon candidates was introduced. exons that might not be identified in the first round might then be found in the second, third, or later round. of course, the recursive depth should not be too large to avoid the inclusion of false positive exons because of the decreasing stringency of the query exons. including every first exon of the dscam mutually exclusive exon clusters in the query sequence, all twelve exons of the exon cluster were identified, both exons of the exon cluster, and and exons for the exon and exon cluster, respectively. increasing the recursive depth to one also revealed exon, which is the most divergent exon of the cluster, and which has not been detected in transcriptome studies yet. exon was not identified because the intron before exon does not have an "ag" at the 3'-end and is therefore not compatible with the "gt" at the 5'-end of the intron succeeding exon the supposed 5'-end sequence of exon is different to the published sequence but is supported by many genomic dna reads available from genbank. exon was also not identified because it contains a frame shift in the drosophila reference genome assembly, supported by many genomic dna reads. therefore, the translations of the predicted transcripts containing exon all stop shortly behind this frame shift. however, both exon and exon were identified in many transcripts. thus, either the genome assembly based on the many genomic dna reads is wrong, which is unlikely, or the many est/cdna-reads are wrong, which is also unlikely, or the genomic dna has been obtained from a different strain than the one that has been used in the transcriptome studies. webscipio is, however, not able to identify mutually exclusive exons if those do not correspond to the exon length and corresponding splice site restrictions. the strength of the new algorithm is illustrated at the exon cluster that encodes two highly divergent but mutually exclusive spliced exons. when applying the search for mutually exclusive exons in the dscam gene against the published genomic sequence all proposed mutually exclusive exons were identified. less mutually exclusive exons in the search against the drosophila melanogaster reference genome sequence compared to the search against the published sequence are therefore not due to problems with the search algorithm. a a dm = drosophila melanogaster; dse = drosophila sechellia rob3c; dy = drosophila yakuba tai18e2; der = drosophila erecta tsc#14021-; da = drosophila ananassae tsc#14024-; dp = drosophila pseudoobscura mv2-25; drp = drosophila persimilis msh-3; dw = drosophila willistoni tsc#14030-; dmo = drosophila mojavensis tsc#15081-; dv = drosophila virilis tsc#15010-; dg = drosophila grimshawi tsc#15287-. a genomes are fragmented and contain gaps in the dscam genes. b the first number corresponds to a search with standard parameters, the second to searches with one round of recursion. c one of the exons is a pseudo-exon because it misses the last forth of the exon because of an in-frame stop codon. in addition, mutually exclusive exons in the dscam genes of the other sequenced drosophila species were searched. here, all mutually exclusive exons were found immediately, and only three further exons were identified by a second recursive round of exon search. as found for the drosophila melanogaster gene, webscipio identified sometimes more sometimes less exons compared to the published analyses. however, the webscipio searches were performed against the official reference genome assemblies, while the published analyses were based on manually performed genomic clone assemblies of the dscam gene regions. therefore, the differences in exon numbers do not result from shortcomings of the search algorithm, but from differences in the assembly of the reference genome data and the manually assembled genomic regions. example genes encoding 5'- and 3'-terminal exons with features of mutually exclusive spliced exons terminal exons are often not selected at the level of splicing. instead, initial exons are most probably selected at the level of transcription that starts at different promoters. terminal exons might either be spliced as differentially included exons, like in the case of the drosophila muscle myosin heavy chain gene, or as multiple poly sites. nevertheless, these terminal exons might contain an important structural part of the encoded protein and thus often have similar length and show sequence similarity. figure shows two examples of genes that contain 5'- and 3'-terminal exons sharing the described features of mutually exclusive exons, but are spliced as multiple promoters or multiple poly sites. the silver protein of drosophila melanogaster illustrates a case where two initial exons, which are transcribed/spliced as multiple promoters, share the features of mutually exclusive exons. the capping protein beta from homo sapiens represents a case where homologous 3'-terminal exons containing multiple poly sites are found. the detection of these cases can be suppressed by disabling the search for mutually exclusive exons for 5'- and 3'-terminal exons. by default, webscipio enables the search for homologous exons for all exons, because it is not known whether the user is searching with a complete, partial or fragmented query sequence. in the case of partial and fragmented sequences the search would provide significant results. also, genes sometimes contain untranslated 5'- and/or 3'-terminal exons whereby the first translated exon could well be part of a cluster of mutually exclusive spliced exons. in addition, alternative terminal exons by themselves might provide interesting perspectives to the corresponding genes independently of whether they are mutually exclusively spliced or not. webscipio cannot distinguish between the described cases and thus the user has to be careful when alternative terminal exons are proposed. detection of trans-spliced genes and arrays of tandem gene duplications the trans-splicing of separate pre-mrnas involving coding exons to reveal a joined transcript is a relatively uncommon event. in general, trans-spliced genes in drosophila melanogaster can be distinguished into those with multiple first exons or multiple 3'-terminal exons, or those with very large introns. many of the trans-spliced genes contain variable single terminal exons or lola ) or alternative terminal exon groups. when searching for mutually exclusive spliced exons based on one of the annotated isoforms of a trans-spliced gene potentially alternative exons of internal exons might be identified. an example of the trans-spliced drosophila melanogaster gene cg is shown in figure 4a. three isoforms of the cg gene exist that result in transcripts of a common 5' exon spliced to isoform-specific sets of three 3' exons. the sequences of the isoform-specific sets are homologous although the intron positions are different between the isoform a/b exons and the isoform c exons. when searching with the isoform a exons for mutually exclusive exons in surrounding introns the homologous exon of isoform b is found for the first of the three isoform a-specific exons. when only searching in surrounding introns further exons are not found for isoform b and for isoform c. thus, if only isoform a were known a mutually exclusive exon would have been proposed. to avoid the mis-annotation of exons of trans-spliced clusters a parameter was introduced that allows searching for candidate exons not only in the neighbouring introns but also in all introns. in figure 4a-iv the exons of isoform b were identified by searching with the exons of isoform a in all introns revealing the trans-spliced nature of the cluster. if searching in up- and downstream regions for alternatively spliced exons, it is possible that candidate exons belong to gene duplicates. in this case, the webscipio option to search for candidates in all introns including up- and downstream regions and not only in surrounding introns helps identifying exons of gene duplications. in many cases, gene duplications result in genes arranged in tandem. those gene duplicates often share the complete gene structure meaning that for every exon there is a corresponding exon in the duplicated gene. figure 4b illustrates this behaviour and provides means by which users can judge between a true cluster of mutually exclusive exons belonging to one gene and a set of duplicated genes. if the search for candidate exons is only allowed in surrounding introns, a set of six homologous exons is found for the drosophila melanogaster gene cg. performing the search in all introns results in five homologous exons also for the second exon of the cg gene, and shows one homologous exon for exon. the first exons of the genes seem to be very divergent. allowing one additional recursive round of candidate search reveals the first exons for two additional gene homologs. in addition lowering the score reveals the exon candidates of the remaining two gene homologs, although two further regions with very low homology to exon appear in the upstream region of the cg gene. this example illustrates the use of the search parameters so that gene duplications can be identified. gene duplicates that are not arranged in tandem but are distributed in the genome do not provide problems in evaluating exon candidates, because the search is restricted to a certain size of the up- and downstream regions. if needed, these gene duplicates can be identified with webscipio using the general multiple results option. application of the search algorithm for mutually exclusive exons to genome scale data the described search algorithm identifies three types of exons as described above: mutually exclusive exons, terminal exons that are spliced as multiple promoters or multiple poly sites but share similar length, reading frame, and sequence homology, and exons with the characteristics of mutually exclusive exons that are actually part of tandemly arrayed gene duplicates or groups of alternative exons in trans-spliced genes. type b and type c exons are false positives, when looking for mutually exclusive exons. in addition, false positive exons are those exons that show all characteristics of type a exons but are constitutively or differentially included spliced. false negatives exons, which are not identified by webscipio, are those mutually exclusive exons that do not have similar length and sequence homology. to quantify the amount of each of these exon types we searched the complete x chromosome of the fruit fly drosophila melanogaster for mutually exclusive spliced exons with webscipio and compared the results to the flybase annotation. protein sequences for the search were obtained from the flybase annotation and mapped to the genomic sequence of the x chromosome using scipio. transcripts containing more than one exon were derived from genes. for each exon mutually exclusive alternative splice variants have been searched for in the surrounding introns. the search parameters were set to amino acids for the allowed length difference, to 15% for the minimal score for exons, and to amino acids for the minimal exon length. we did not search for alternative exons in up- and downstream regions of genes, and we did not apply the recursive search, which means the repeated search for further alternative exons with the newly identified exons that we demonstrated for dscam. three genes g cg and cg42249), in which mutually exclusive exons were found, were excluded from the analysis, because the respective exons are spliced in a mutually exclusive manner in groups of two, three, and four exons, instead of single exons within a cluster. those genes are probably trans-spliced. search for non-mutually exclusive exons sharing similar length, same reading frame, and sequence homology it could well be possible that internal exons with similar length, same reading frame, and showing sequence homology are not mutually exclusive spliced exons, but constitutive exons or exons spliced by one of the other types of alternative splicing. to get a statistically relevant number of these types of exons we collected all genes of the drosophila melanogaster x chromosome containing at least two exons based on the flybase annotation version. the transcripts of each gene were analysed independently because alternative splicing produces different exon neighbours. thus exons are counted for each transcript even if the transcripts have the same start and end points in the genomic sequence. in total, the transcripts of the drosophila melanogaster x chromosome include exons. all neighbouring exons were compared with respect to having similar length, sharing high similarity, coding for at least fifteen amino acids, and encoding the same reading frame. the results are summarized in table. only % of the non-mutually exclusive exons share the features of mutually exclusive exons. these exons are located in only six genes out of. in one of the six genes the two homologous exons are terminal exons and would represent a case of multiple poly sites if alternatively spliced. this analysis shows that the chance that the exons predicted by webscipio as mutually exclusive exons will later be reannotated as constitutive or differentially included exons, is very low. a a exons which share similar length, same reading frame and sequence homology search for mutually exclusive spliced exons in the drosophila melanogaster x chromosome some categories have to be defined to separate true mutually exclusive spliced exons from predicted ones and false positives and false negatives. as real mutually exclusive exons we regard those with the following criteria: an exon is part of a cluster of mutually exclusive spliced exons if each transcript of the gene contains exactly one exon of the cluster, the cluster contains at least two exons, the exons of the cluster are neighbouring exons, and the cluster is surrounded by further exons. the latter criterion distinguishes the mutually exclusive spliced exons from clusters of initial exons and 3'-terminal exons that are spliced in a mutually exclusive manner and share sequence similarity, similar length, and splice site conservation. in contrast to real mutually exclusive spliced exons the exons of these clusters appear mutually exclusive in the transcripts but their transcription and splicing is regulated in a different way. these clusters are therefore regarded as types of multiple promoters and types of multiple poly sites, and are false positives. other types of false positives are those exons that are predicted by webscipio but overlap with already annotated exons and do not match exactly the positions of these exons. false negatives are those exons that do not meet the preconditions of similar length and sequence homology. however, if those exons are mutually exclusive spliced they must have conserved splice sites and reading frames. in total, exons of similar length, same splice sites and reading frames, and sequence homology have been identified by webscipio, of which are potentially in clusters of mutually exclusive exons, in clusters of multiple promoters, and in clusters of multiple poly sites. of the exons predicted to belong to internal clusters of mutually exclusive spliced exons, exons are already annotated in flybase. exons are predictions by webscipio that have not been described before. these exons are distributed into clusters that belong to genes. thus, there are several clusters with more than two alternative exons, and one gene with two clusters. if the flybase based annotation is assumed to represent true mutually exclusive exons, the chart represents the specificity of our method. the already known mutually exons divided by predicted exons result in 40% specificity. however, the value for the specificity is misleading because it depends on the "known" mutually exclusive exons. we expect that many of the additional exons predicted by webscipio will be experimentally confirmed in the future and thus will become "known" mutually exclusive exons. the true specificity will therefore be much higher than the value of 40% suggests. to analyse whether the additional exons predicted by webscipio contain general features of exons, the found exons were compared to those of an ab initio prediction performed by augustus. in many cases the webscipio predictions are supported by the ab initio prediction, which is based on the genomic sequence alone. the augustus prediction matches of the exons with exact exon borders and overlaps with of them. the results show that about 70% of all predicted exons comprise clusters of internal mutually exclusive exons. the false positive prediction of 5'- and 3'-terminal exons as mutually exclusive exons, which comprise the remaining 30% of predicted exons, could even be suppressed by a webscipio option. we can also conclude that webscipio correctly identifies all but one of the annotated mutually exclusive exons. this suggests that most of the webscipio predictions of new mutually exclusive exon candidates will also be real mutually exclusive exons. this is supported by the ab initio exon prediction by augustus that showed exon probability for about 50% of the newly predicted exons, which is comparable to the ab initio prediction of the already annotated exons. however, we cannot completely exclude the possibility that some of the newly predicted exons might in truth be constitutive or differentially included exons. false negatives would be those mutually exclusive spliced exons that do not share a similar length and sequence similarity. to figure out how often clusters of mutually exclusive exons with such characteristics exist in comparison to mutually exclusive exons with similar length and sequence similarity, all internal clusters of exons on the x chromosome that were annotated as mutually exclusive based on flybase transcripts were manually analysed. of the annotated genes only the phosphorylase kinase γ gene contains two mutually exclusive spliced exons that do not have similar length and sequence. if the flybase annotation is assumed as true, the chart in figure represents the sensitivity of the algorithm. predicted mutually exclusive spliced exons divided by annotated exons results in 93% sensitivity for internal exons. these data likely indicate that not many mutually exclusive spliced exons will be missed given the constraints of similar length and sequence similarity as implemented in webscipio. mutually exclusive exons predicted for 5'- and 3'-terminal exons were regarded as false positives because these rather present cases of multiple promoters, multiple poly sites, and differentially included exons. however, additional untranslated terminal exons might exist that were not analysed here, and in those cases the exons, based on the translation predicted as terminal, become internal and thus true mutually exclusive exons. for comparison all terminal exons annotated as transcribed or spliced in a mutually exclusive manner have been analysed. of the terminal exons only terminal exons share the features of mutually exclusive spliced exons. a reason for the sequence and length variability of terminal exons is that the n- and c-termini of proteins are not as restricted in their structure as internal parts. thus, the number of false positives predicted by webscipio is rather low. future developments and applications due to the precondition that mutually exclusive exons encode the same part of the protein product, we also want to include the comparison of the prediction of secondary structural elements for the query and the candidate exons as an additional scoring, analysis, and validation parameter. also, other substitution matrices might be offered for the scoring of the aligned query and candidate exons. scipio and webscipio have been shown to be suitable for the prediction of genes in cross-species searches. of course, both approaches can be combined and users can search, for example, with a human protein query sequence in other mammals to identify homologous genes and simultaneously predict mutually exclusive exons in the target sequence. because the search for mutually exclusive exons relies on the translation of the exons as found in the genomic dna, it does not depend on the initial query sequence but on the quality of the exons identified in the cross-species search. another application would be to search for mutually exclusive spliced genes in the complete genomes of sequenced eukaryotes.  the extension of webscipio to search for mutually exclusive exons is based on the precondition that these exons encode regions of the same structural part of the protein product. this precondition provides restrictions to the search for candidate exons concerning their length, splice site conservation and reading frame preservation, and overall homology. the implemented algorithm has been shown to identify all known mutually exclusive spliced exons in many example genes from various species, like the muscle myosin heavy chain gene of daphnia pulex or the dscam gene of drosophila melanogaster. the search for homologs of terminal exons might, however, result in the prediction of multiple promoters, multiple poly sites, groups of trans-spliced exons, or tandemly arrayed gene duplicates, and can therefore optionally be disabled. to quantify the quality of webscipio to correctly predict already annotated mutually exclusive exons and to predict so far unrecognized exon candidates, an analysis of the whole x chromosome of drosophila melanogaster has been performed. all but two of the annotated mutually exclusive exons were found by webscipio. in addition, webscipio predicts new mutually exclusive exon candidates of which about 50% are supported by an ab initio exon prediction by augustus. in conclusion, webscipio should be able to identify mutually exclusive spliced exons in any query sequence from any species with a very high probability. abbreviations dhc: dynein heavy chain; dscam: down syndrome cell adhesion molecule; gff: general feature format; mhc: myosin heavy chain; svg: scalable vector graphics; yaml: yaml ain't markup language authors' contributions hp, fo, and mk set the requirements for the system. hp and kh wrote the software. fo assisted in and supervised the implementation of the software. bh implemented improvements to the software, and kh committed the final version. kh performed the whole chromosome search and evaluation. hp, kh, bh, and mk performed extensive testing. kh and mk wrote the manuscript. all authors read and approved the final version of the manuscript. supplementary material additional file 1 detailed activity diagram. the detailed activity diagram shows each step of the search algorithm including points of decision and loops. click here for file additional file 2 search for non-mutually exclusive exons sharing similar length, same reading frame and sequence homology. the file provides detailed information of the found genes and their gene structures. click here for file acknowledgements mk has been funded by grants ko 2251/3- ko 2251/3- and ko 2251/6- of the deutsche forschungsgemeinschaft.
in addition, the algorithm was applied to the whole drosophila melanogaster x chromosome and the results were compared to the flybase annotation and an ab initio prediction. several types of different alternative splice forms exist including exon skipping, differential splicing of exons at their 3'- or 5'-end, intron retention, and mutually exclusive splicing. the latter term is used for clusters of internal exons that are spliced in a mutually exclusive manner. we have implemented an extension to the webscipio software to search for mutually exclusive exons. here, the search is based on the precondition that mutually exclusive exons encode regions of the same structural part of the protein product. mutually exclusive exons that are not homologous and not of about the same length will not be found. using the new algorithm, mutually exclusive exons in several example genes, a dynein heavy chain, a muscle myosin heavy chain, and dscam were correctly identified. clusters of mutually exclusive exons might be subsequent to each other and might encode dozens of exons. this is the first implementation of an automatic search for mutually exclusive exons in eukaryotes. webscipio offers high quality gene structure figures with the clusters of mutually exclusive exons colour-coded, and several analysis tools for further manual inspection. the genome scale analysis of all genes of the drosophila melanogaster x chromosome showed that webscipio is able to find all but two of the annotated mutually exclusive spliced exons and predicts new candidate exons. thus, webscipio should be able to identify mutually exclusive spliced exons in any query sequence from any species with a very high probability. alternative splicing of pre-mature rna is an important process eukaryotes utilize to increase their repertoire of different protein products. this precondition provides restrictions to the search for candidate exons concerning their length, splice site conservation and reading frame preservation, and overall homology.
 alternative splicing of pre-mature rna is an important process eukaryotes utilize to increase their repertoire of different protein products. several types of different alternative splice forms exist including exon skipping, differential splicing of exons at their 3'- or 5'-end, intron retention, and mutually exclusive splicing. the latter term is used for clusters of internal exons that are spliced in a mutually exclusive manner.  we have implemented an extension to the webscipio software to search for mutually exclusive exons. here, the search is based on the precondition that mutually exclusive exons encode regions of the same structural part of the protein product. this precondition provides restrictions to the search for candidate exons concerning their length, splice site conservation and reading frame preservation, and overall homology. mutually exclusive exons that are not homologous and not of about the same length will not be found. using the new algorithm, mutually exclusive exons in several example genes, a dynein heavy chain, a muscle myosin heavy chain, and dscam were correctly identified. in addition, the algorithm was applied to the whole drosophila melanogaster x chromosome and the results were compared to the flybase annotation and an ab initio prediction. clusters of mutually exclusive exons might be subsequent to each other and might encode dozens of exons.  this is the first implementation of an automatic search for mutually exclusive exons in eukaryotes. exons are predicted and reconstructed in the same run providing the complete gene structure for the protein query of interest. webscipio offers high quality gene structure figures with the clusters of mutually exclusive exons colour-coded, and several analysis tools for further manual inspection. the genome scale analysis of all genes of the drosophila melanogaster x chromosome showed that webscipio is able to find all but two of the annotated mutually exclusive spliced exons and predicts new candidate exons. thus, webscipio should be able to identify mutually exclusive spliced exons in any query sequence from any species with a very high probability. webscipio is freely available to academics at http://www.webscipio.org. 