
<section>
  <title>Sequence implementation</title>

  <section>
    <title>Overall design issues</title>

    <para>One of the requirements for the &seqapi; is that it should
      not require the use of a specific implementation of underlying
      data structure. For that reason that API makes extensive use of
      interfaces. All of the core classes are defined in the first
      instance as a interface. These are extended with an abstact
      class which implements many of the methods which can be defined
      in terms of the other methods in the interface (so are not
      implementation dependant) or alternatively where the default
      implementation is held to be likely to be a good implementation
      under most circumstances. Where ever possible we have used
      object composition, to delegate functionality to external
      classes. The support classes which provide this functionality
      are also available within the API and can be re-used. We 
      have provided default implementations which fully implement the
      interface. As far as possible these reuse standard classes
      provided by the Java Collections API. </para>
    
  </section>

  <section>
    <title>The implementation of sequence. </title>

    <para>The sequence interface is relatively straight forward,
      provided methods for accessing the elements, subsequences, and the
      SequenceType.
      
      <programlisting>
    
    public interface Sequence extends Identifiable
    {
    	public Sequence getSubSequence(int from, int length);
    	public char[] getSequenceAsChars();
    	public Element[] getSequenceAsElements();
    	public char getElementAtAsChar(int index);
    	public Element getElementAt(int index);
    	public SequenceType getSequenceType();
    	public int getLength();
    }// Sequence

      </programlisting>

      We have provided the ability to access the sequence as char
      arrays, because this allows easy printing. This has no impact on
      the underlying implementation because the
      <classname>Element</classname> interface provides a method for
      obtaining a char representation of each
      <classname>Element</classname>.</para>

    <para>The default implementation of
      <classname>Sequence</classname> called unsurprisingly
      <classname>DefaultSequence</classname> implements this class using
      a instance of <classname>java.util.ArrayList</classname>, which
      is part of the Java Collections API. </para>
    
  </section>

  <section id="mutable">
    <title id="mutable.title">Mutable Sequences</title>
    
    <para>One of the requirements for the &seqapi; was that it should
      be able to cope with sequences that change after they have been
      created. Probably the most common method for doing this is for
      the Sequence to signal events when ever it is changed, and to
      allow other objects to listen for these events. </para>

    <para>The biggest problem that an event system has for the
      &seqapi; is that it could place a fairly large computational
      load on using the sequences. The normal way to implement an
      event system in Java, requires the creation of an Object for
      each change that occurs, which could result in a large number of
      events being called, and therefore a large number of Objects
      created. It is for this reason combined with the desire not to
      place additional load on the implementor of Sequence.</para>

    <![%draft;[
    <para>
      <emphasis>One of the things that I do not like about this
	arrangement is that if you have an object of type sequence you
	can not know whether or not it is mutable, at least not
	without doing an instanceof MutableSequence call. I suppose
	that this is better than nothing but its a little bit
	messy. As an alternative it would be possible to have defined
	a "isMutable" method, and put the SequenceEventProducer
	methods into the top level Sequence class. This is also a
	little messy. The other problem is that it is perfectly
	possible to implement a Sequence which can change, but which
	does not have the listener methods. If the listener methods
	were in the top level class then this would not be the case,
	although it would always be possible to implement them
	foolishly.</emphasis>
    </para>
    ]]>
    
    <para>We have therefore defined the
      <classname>MutableSequence</classname> class. This is the top
      level class for Sequences which can change following
      construction. As well as the <classname>Sequence</classname>
      interface it extends the
      <classname>SequenceEventProducer</classname> interface which
      defines the following methods</para>

    <programlisting>
    public interface SequenceEventProvider 
    {
        public void addSequenceListener(SequenceListener listener);
      
        public void removeSequenceListener(SequenceListener listener);
        
        public void addVetoableSequenceListener(VetoableSequenceListener listener);
        
        public void removeVetoableSequenceListener(VetoableSequenceListener listener);
    
    }// SequenceEventProvider
      </programlisting>
      
    <para>These methods provide the ability to add
      <classname>SequenceListener's</classname> to give
      <classname>Sequence</classname> instance. These listeners will
      be informed when this <classname>Sequence</classname>
      changes. Additionally there are methods for adding vetoable
      Listeners, which throw an exception to prevent that
      <classname>Sequence</classname> from changing. </para>

    <para>Listeners are informed of the details of the
      event via their only method</para>

    <programlisting>
    public interface SequenceListener extends EventListener
    {
        public void changeOccurred( SequenceEvent event );
    }// SequenceListener
    </programlisting>

    <para>The <classname>SequenceEvent</classname> object carries with
      it information about the region of the sequence affected by the
      change and information about the type of change, if it is
      known. We have provided this information because it can be used
      to increase efficiency in some cases. Of course in many cases it
      is just safer to assume that the entire Sequence has
      changed.</para>

    <para>It should be noted that MutableSequence itself does not
      carry any methods for actually changing the underlying
      sequence. This methods are provided for by the sub classes and
      are described <link linkend="gappable.and.editable">next</link></para>
  </section>

  <section id="gappable.and.editable">
    <title>Gapped and Editable Sequences</title>
    
    <![%draft;[
    <para><emphasis>Should this not really be
    <classname>GappableSequence</classname>?</emphasis></para>
    ]]>
	
    <para>Aligning two sequences requires inserting gaps into one or
      both of them. Gaps in sequences are supported by the
      <classname>GappedSequence</classname>. This class provides a
      series of methods which mirror those provided by
      <classname>Sequence</classname> but instead return the
      equivalent Gapped value. </para>

    <programlisting>
    public interface GappedSequence extends MutableSequence
    {
        public GappedSequence getGappedSubSequence( int from, int to );
        
        public Element getGappedElementAt( int position );
        
        public char getGappedElementAtAsChar( int position );
        
        public Element[] getGappedSequenceAsElements();
        
        public char[] getGappedSequenceAsChars();
        
        public int getGappedLength();
        [SNIP]
    }
    </programlisting>

    <para>A call to the <function>getLength()</function> method of a
      GappedSequence will therefore return the length of the sequence,
      <emphasis>ignoring the gaps</emphasis>. The alternative method
      <function>getGappedLength()</function> should be used to include
      the gaps.</para>

    <para>The reason that this approach was choosen was because the
      <classname>Gap.GAP</classname> object will not be a part of the
      SequenceType for a given sequence. For example, a gapped DNA
      sequence can have one of five elements, namely A, C, G, T or a
      Gap. Only the first four of these will be recognised as a member
      of the <classname>DNASequenceType</classname>. It seems
      inappropriate therefore that the
      <function>getElementAt(&nbsp;int&nbsp;)</function>should
      return <classname>Gap.GAP</classname>. This impacts all of the
      other <classname>Sequence</classname> methods (with the
      exception of <function>getSequenceType()</function>).</para>

    <para>In order to support translation between the gapped and
      ungapped length indexes there are two methods.

      <programlisting>
        public int getGappedPositionOf( int index );
        	
        public int getUngappedPositionOf( int index );
      </programlisting>
      
      For these methods
      <function>getGappedPositionOf(&nbsp;getLength()&nbsp;)</function>,
      should return <function>getGappedLength()</function>, whilst
      <function>getUngappedPositionOf(&nbsp;getGappedLength()&nbsp;)</function>
      should return <function>getLength()</function>.</para>

    <para>The final methods required for a
    <classname>GappedSequence</classname> are those to add and remove
      Gaps from the sequence. These are as follows.

      <programlisting>
        public void insertGapAt( int index ) throws
	    NoSuchSequenceElementException, SequenceVetoException;
        
        public void insertGapAt( int index, int length ) throws
	    NoSuchSequenceElementException, SequenceVetoException;
        
        public void deleteGapAt( int index ) throws
	    NoGapAtThisPositionException, NoSuchSequenceElementException, SequenceVetoException;
        
        public void deleteGapAt( int index, int length ) throws
	    NoGapAtThisPositionException, NoSuchSequenceElementException, SequenceVetoException;
      </programlisting>
      These methods take paramaters in terms of Gapped indexs. Changes
      to the sequence caused by these methods will be signalled by the
      event mechanism described in the section
      <link linkend="mutable" endterm = "mutable.title"></link></para>
    
    <para>The <classname>EditableSequence</classname> is designed in
      a similar way, with methods for setting the
      <classname>Element</classname>'s at a given index. These methods
      are as follows</para>
    <programlisting>
    public interface EditableSequence extends MutableSequence
    {
    	public Element setElementAt( Element element, int index )
          throws NoSuchSequenceElementException, SequenceVetoException;
    	
    	public Element[] setElementAt( Element[] element, int index )
          throws NoSuchSequenceElementException, SequenceVetoException;
    	
    	public void insertElementAt( Element element, int index )
          throws NoSuchSequenceElementException, SequenceVetoException;
    	
    	public void insertElementAt( Element[] element, int index )
          throws NoSuchSequenceElementException, SequenceVetoException;
    	
    	public Element deleteElementAt( int index )
          throws NoSuchSequenceElementException, SequenceVetoException;
    	
    	public Element[] deleteElementAt( int index, int length )
          throws NoSuchSequenceElementException, SequenceVetoException;
    }// EditableSequence     
    </programlisting>
    <para>
      As with the <classname>GappedSequence</classname> all of these
      methods signal events and are Veto'able. Additionally these
      methods are subject to a <classname>SequenceType</classname>
      check, throwing an
      <classname>InvalidSequenceTypeException</classname> if this
      fails.
    </para>
  </section>

  <section>
    <title>Complex Sequences</title>

    <para>The final class in the &seqapi; modelling Sequences is the
      <classname>ComplexSequence</classname>. This is for modelling what
      might be called &quot;modififed&quot; sequences. Examples of these
      would include DNA sequences with methylated residues, or protein
      sequences with any of the many post-translational
      modifications. </para>

    <para>This class is implemented in a similar way to the
      <classname>GappedSequence</classname>. The standard
      <classname>Sequence</classname> methods return
      <classname>Element</classname>'s which unmodified, and will be
      identified as part of the
      <classname>SequenceType</classname>. </para>

    <para>It would probably be a good idea to actually write
      this. </para>
  </section>
</section>


<!--
 We need to define local variables to enable psgml mode to work out
 what DTD we are using, and also where we are in the document.

 Local Variables: ***
 sgml-parent-document:("sequence.sgml" "article" "section" ) ***
 End: ***
  -->






