src/jalview/util/MappingUtils.java

   1 package jalview.util;
   2
   3 import jalview.analysis.AlignmentSorter;
   4 import jalview.api.AlignViewportI;
   5 import jalview.commands.CommandI;
   6 import jalview.commands.EditCommand;
   7 import jalview.commands.EditCommand.Action;
   8 import jalview.commands.EditCommand.Edit;
   9 import jalview.commands.OrderCommand;
  10 import jalview.datamodel.AlignedCodonFrame;
  11 import jalview.datamodel.AlignmentI;
  12 import jalview.datamodel.AlignmentOrder;
  13 import jalview.datamodel.ColumnSelection;
  14 import jalview.datamodel.SearchResults;
  15 import jalview.datamodel.SearchResults.Match;
  16 import jalview.datamodel.Sequence;
  17 import jalview.datamodel.SequenceGroup;
  18 import jalview.datamodel.SequenceI;
  19 import jalview.gui.AlignViewport;
  20
  21 import java.util.ArrayList;
  22 import java.util.HashMap;
  23 import java.util.Iterator;
  24 import java.util.List;
  25 import java.util.Map;
  26 import java.util.Set;
  27
  28 /**
  29  * Helper methods for manipulations involving sequence mappings.
  30  *
  31  * @author gmcarstairs
  32  *
  33  */
  34 public final class MappingUtils
  35 {
  36
  37   /**
  38    * Helper method to map a CUT or PASTE command.
  39    *
  40    * @param edit
  41    *          the original command
  42    * @param undo
  43    *          if true, the command is to be undone
  44    * @param targetSeqs
  45    *          the mapped sequences to apply the mapped command to
  46    * @param result
  47    *          the mapped EditCommand to add to
  48    * @param mappings
  49    */
  50   protected static void mapCutOrPaste(Edit edit, boolean undo,
  51           List<SequenceI> targetSeqs, EditCommand result,
  52           Set<AlignedCodonFrame> mappings)
  53   {
  54     Action action = edit.getAction();
  55     if (undo)
  56     {
  57       action = action.getUndoAction();
  58     }
  59     // TODO write this
  60     System.err.println("MappingUtils.mapCutOrPaste not yet implemented");
  61   }
  62
  63   /**
  64    * Returns a new EditCommand representing the given command as mapped to the
  65    * given sequences. If there is no mapping, returns null.
  66    *
  67    * @param command
  68    * @param undo
  69    * @param mapTo
  70    * @param gapChar
  71    * @param mappings
  72    * @return
  73    */
  74   public static EditCommand mapEditCommand(EditCommand command,
  75           boolean undo, final AlignmentI mapTo, char gapChar,
  76           Set<AlignedCodonFrame> mappings)
  77   {
  78     /*
  79      * For now, only support mapping from protein edits to cDna
  80      */
  81     if (!mapTo.isNucleotide())
  82     {
  83       return null;
  84     }
  85
  86     /*
  87      * Cache a copy of the target sequences so we can mimic successive edits on
  88      * them. This lets us compute mappings for all edits in the set.
  89      */
  90     Map<SequenceI, SequenceI> targetCopies = new HashMap<SequenceI, SequenceI>();
  91     for (SequenceI seq : mapTo.getSequences())
  92     {
  93       SequenceI ds = seq.getDatasetSequence();
  94       if (ds != null)
  95       {
  96         final SequenceI copy = new Sequence("", new String(
  97                 seq.getSequence()));
  98         copy.setDatasetSequence(ds);
  99         targetCopies.put(ds, copy);
 100       }
 101     }
 102
 103     /*
 104      * Compute 'source' sequences as they were before applying edits:
 105      */
 106     Map<SequenceI, SequenceI> originalSequences = command.priorState(undo);
 107
 108     EditCommand result = new EditCommand();
 109     Iterator<Edit> edits = command.getEditIterator(!undo);
 110     while (edits.hasNext())
 111     {
 112       Edit edit = edits.next();
 113       if (edit.getAction() == Action.CUT
 114               || edit.getAction() == Action.PASTE)
 115       {
 116         mapCutOrPaste(edit, undo, mapTo.getSequences(), result, mappings);
 117       }
 118       else if (edit.getAction() == Action.INSERT_GAP
 119               || edit.getAction() == Action.DELETE_GAP)
 120       {
 121         mapInsertOrDelete(edit, undo, originalSequences,
 122                 mapTo.getSequences(), targetCopies, gapChar, result,
 123                 mappings);
 124       }
 125     }
 126     return result.getSize() > 0 ? result : null;
 127   }
 128
 129   /**
 130    * Helper method to map an edit command to insert or delete gaps.
 131    *
 132    * @param edit
 133    *          the original command
 134    * @param undo
 135    *          if true, the action is to undo the command
 136    * @param originalSequences
 137    *          the sequences the command acted on
 138    * @param targetSeqs
 139    * @param targetCopies
 140    * @param gapChar
 141    * @param result
 142    *          the new EditCommand to add mapped commands to
 143    * @param mappings
 144    */
 145   protected static void mapInsertOrDelete(Edit edit, boolean undo,
 146           Map<SequenceI, SequenceI> originalSequences,
 147           final List<SequenceI> targetSeqs,
 148           Map<SequenceI, SequenceI> targetCopies, char gapChar,
 149           EditCommand result, Set<AlignedCodonFrame> mappings)
 150   {
 151     Action action = edit.getAction();
 152
 153     /*
 154      * Invert sense of action if an Undo.
 155      */
 156     if (undo)
 157     {
 158       action = action.getUndoAction();
 159     }
 160     final int count = edit.getNumber();
 161     final int editPos = edit.getPosition();
 162     for (SequenceI seq : edit.getSequences())
 163     {
 164       /*
 165        * Get residue position at (or to right of) edit location. Note we use our
 166        * 'copy' of the sequence before editing for this.
 167        */
 168       SequenceI ds = seq.getDatasetSequence();
 169       if (ds == null)
 170       {
 171         continue;
 172       }
 173       final SequenceI actedOn = originalSequences.get(ds);
 174       final int seqpos = actedOn.findPosition(editPos);
 175
 176       /*
 177        * Determine all mappings from this position to mapped sequences.
 178        */
 179       SearchResults sr = buildSearchResults(seq, seqpos, mappings);
 180
 181       if (!sr.isEmpty())
 182       {
 183         for (SequenceI targetSeq : targetSeqs)
 184         {
 185           ds = targetSeq.getDatasetSequence();
 186           if (ds == null)
 187           {
 188             continue;
 189           }
 190           SequenceI copyTarget = targetCopies.get(ds);
 191           final int[] match = sr.getResults(copyTarget, 0,
 192                   copyTarget.getLength());
 193           if (match != null)
 194           {
 195             final int ratio = 3; // TODO: compute this - how?
 196             final int mappedCount = count * ratio;
 197
 198             /*
 199              * Shift Delete start position left, as it acts on positions to its
 200              * right.
 201              */
 202             int mappedEditPos = action == Action.DELETE_GAP ? match[0]
 203                     - mappedCount : match[0];
 204             Edit e = result.new Edit(action, new SequenceI[]
 205             { targetSeq }, mappedEditPos, mappedCount, gapChar);
 206             result.addEdit(e);
 207
 208             /*
 209              * and 'apply' the edit to our copy of its target sequence
 210              */
 211             if (action == Action.INSERT_GAP)
 212             {
 213               copyTarget.setSequence(new String(StringUtils.insertCharAt(
 214                       copyTarget.getSequence(), mappedEditPos, mappedCount,
 215                       gapChar)));
 216             }
 217             else if (action == Action.DELETE_GAP)
 218             {
 219               copyTarget.setSequence(new String(StringUtils.deleteChars(
 220                       copyTarget.getSequence(), mappedEditPos,
 221                       mappedEditPos + mappedCount)));
 222             }
 223           }
 224         }
 225       }
 226       /*
 227        * and 'apply' the edit to our copy of its source sequence
 228        */
 229       if (action == Action.INSERT_GAP)
 230       {
 231         actedOn.setSequence(new String(StringUtils.insertCharAt(
 232                 actedOn.getSequence(), editPos, count, gapChar)));
 233       }
 234       else if (action == Action.DELETE_GAP)
 235       {
 236         actedOn.setSequence(new String(StringUtils.deleteChars(
 237                 actedOn.getSequence(), editPos, editPos + count)));
 238       }
 239     }
 240   }
 241
 242   /**
 243    * Returns a SearchResults object describing the mapped region corresponding
 244    * to the specified sequence position.
 245    *
 246    * @param seq
 247    * @param index
 248    * @param seqmappings
 249    * @return
 250    */
 251   public static SearchResults buildSearchResults(SequenceI seq, int index,
 252           Set<AlignedCodonFrame> seqmappings)
 253   {
 254     SearchResults results;
 255     results = new SearchResults();
 256     if (index >= seq.getStart() && index <= seq.getEnd())
 257     {
 258       for (AlignedCodonFrame acf : seqmappings)
 259       {
 260         acf.markMappedRegion(seq, index, results);
 261       }
 262     }
 263     return results;
 264   }
 265
 266   /**
 267    * Returns a (possibly empty) SequenceGroup containing any sequences in the
 268    * mapped viewport corresponding to the given group in the source viewport.
 269    *
 270    * @param sg
 271    * @param mapFrom
 272    * @param mapTo
 273    * @return
 274    */
 275   public static SequenceGroup mapSequenceGroup(SequenceGroup sg,
 276           AlignViewportI mapFrom, AlignViewportI mapTo)
 277   {
 278     /*
 279      * Note the SequenceGroup holds aligned sequences, the mappings hold dataset
 280      * sequences.
 281      */
 282     boolean targetIsNucleotide = mapTo.isNucleotide();
 283     AlignViewportI protein = targetIsNucleotide ? mapFrom : mapTo;
 284     Set<AlignedCodonFrame> codonFrames = protein.getAlignment()
 285             .getCodonFrames();
 286
 287     /*
 288      * Copy group name, colours, but not sequences
 289      */
 290     SequenceGroup mappedGroup = new SequenceGroup(sg);
 291     mappedGroup.clear();
 292     // TODO set width of mapped group
 293
 294     for (SequenceI selected : sg.getSequences())
 295     {
 296       for (AlignedCodonFrame acf : codonFrames)
 297       {
 298         SequenceI mappedSequence = targetIsNucleotide ? acf
 299                 .getDnaForAaSeq(selected) : acf.getAaForDnaSeq(selected);
 300         if (mappedSequence != null)
 301         {
 302           for (SequenceI seq : mapTo.getAlignment().getSequences())
 303           {
 304             if (seq.getDatasetSequence() == mappedSequence)
 305             {
 306               mappedGroup.addSequence(seq, false);
 307               break;
 308             }
 309           }
 310         }
 311       }
 312     }
 313     return mappedGroup;
 314   }
 315
 316   /**
 317    * Returns an OrderCommand equivalent to the given one, but acting on mapped
 318    * sequences as described by the mappings, or null if no mapping can be made.
 319    *
 320    * @param command
 321    *          the original order command
 322    * @param undo
 323    *          if true, the action is to undo the sort
 324    * @param mapTo
 325    *          the alignment we are mapping to
 326    * @param mappings
 327    *          the mappings available
 328    * @return
 329    */
 330   public static CommandI mapOrderCommand(OrderCommand command,
 331           boolean undo, AlignmentI mapTo, Set<AlignedCodonFrame> mappings)
 332   {
 333     SequenceI[] sortOrder = command.getSequenceOrder(undo);
 334     List<SequenceI> mappedOrder = new ArrayList<SequenceI>();
 335     int j = 0;
 336     for (SequenceI seq : sortOrder)
 337     {
 338       for (AlignedCodonFrame acf : mappings)
 339       {
 340         /*
 341          * Try protein-to-Dna, failing that try dna-to-protein
 342          */
 343         SequenceI mappedSeq = acf.getDnaForAaSeq(seq);
 344         if (mappedSeq == null)
 345         {
 346           mappedSeq = acf.getAaForDnaSeq(seq);
 347         }
 348         if (mappedSeq != null)
 349         {
 350           for (SequenceI seq2 : mapTo.getSequences())
 351           {
 352             if (seq2.getDatasetSequence() == mappedSeq)
 353             {
 354               mappedOrder.add(seq2);
 355               j++;
 356               break;
 357             }
 358           }
 359         }
 360       }
 361     }
 362
 363     /*
 364      * Return null if no mappings made.
 365      */
 366     if (j == 0)
 367     {
 368       return null;
 369     }
 370
 371     /*
 372      * Add any unmapped sequences on the end of the sort in their original
 373      * ordering.
 374      */
 375     if (j < mapTo.getHeight())
 376     {
 377       for (SequenceI seq : mapTo.getSequences())
 378       {
 379         if (!mappedOrder.contains(seq))
 380         {
 381           mappedOrder.add(seq);
 382         }
 383       }
 384     }
 385
 386     /*
 387      * Have to align the sequences before constructing the OrderCommand - which
 388      * then realigns them?!?
 389      */
 390     final SequenceI[] mappedOrderArray = mappedOrder
 391             .toArray(new SequenceI[mappedOrder.size()]);
 392     SequenceI[] oldOrder = mapTo.getSequencesArray();
 393     AlignmentSorter.sortBy(mapTo, new AlignmentOrder(mappedOrderArray));
 394     final OrderCommand result = new OrderCommand(command.getDescription(),
 395             oldOrder, mapTo);
 396     return result;
 397   }
 398
 399   /**
 400    * Returns a ColumnSelection in the 'mapTo' view which corresponds to the
 401    * given selection in the 'mapFrom' view. We assume one is nucleotide, the
 402    * other is protein (and holds the mappings from codons to protein residues).
 403    *
 404    * @param colsel
 405    * @param mapFrom
 406    * @param mapTo
 407    * @return
 408    */
 409   public static ColumnSelection mapColumnSelection(ColumnSelection colsel,
 410           AlignViewportI mapFrom, AlignViewport mapTo)
 411   {
 412     boolean targetIsNucleotide = mapTo.isNucleotide();
 413     AlignViewportI protein = targetIsNucleotide ? mapFrom : mapTo;
 414     Set<AlignedCodonFrame> codonFrames = protein.getAlignment()
 415             .getCodonFrames();
 416     ColumnSelection mappedColumns = new ColumnSelection();
 417     char fromGapChar = mapFrom.getAlignment().getGapCharacter();
 418
 419     for (Object obj : colsel.getSelected())
 420     {
 421       int col = ((Integer) obj).intValue();
 422       int mappedToMin = Integer.MAX_VALUE;
 423       int mappedToMax = Integer.MIN_VALUE;
 424
 425       /*
 426        * For each sequence in the 'from' alignment
 427        */
 428       for (SequenceI fromSeq : mapFrom.getAlignment().getSequences())
 429       {
 430         /*
 431          * Ignore gaps (unmapped anyway)
 432          */
 433         if (fromSeq.getCharAt(col) == fromGapChar)
 434         {
 435           continue;
 436         }
 437
 438         /*
 439          * Get the residue position and find the mapped position.
 440          */
 441         int residuePos = fromSeq.findPosition(col);
 442         SearchResults sr = buildSearchResults(fromSeq, residuePos,
 443                 codonFrames);
 444         for (Match m : sr.getResults())
 445         {
 446           int mappedStartResidue = m.getStart();
 447           int mappedEndResidue = m.getEnd();
 448           SequenceI mappedSeq = m.getSequence();
 449
 450           /*
 451            * Locate the aligned sequence whose dataset is mappedSeq. TODO a
 452            * datamodel that can do this efficiently.
 453            */
 454           for (SequenceI toSeq : mapTo.getAlignment().getSequences())
 455           {
 456             if (toSeq.getDatasetSequence() == mappedSeq)
 457             {
 458               int mappedStartCol = toSeq.findIndex(mappedStartResidue);
 459               int mappedEndCol = toSeq.findIndex(mappedEndResidue);
 460               mappedToMin = Math.min(mappedToMin, mappedStartCol);
 461               mappedToMax = Math.max(mappedToMax, mappedEndCol);
 462               // System.out.println(fromSeq.getName() + " mapped to cols "
 463               // + mappedStartCol + ":" + mappedEndCol);
 464               break;
 465               // TODO remove break if we ever want to map one to many sequences
 466             }
 467           }
 468         }
 469       }
 470       /*
 471        * Add mapped columns to mapped selection (converting base 1 to base 0)
 472        */
 473       for (int i = mappedToMin; i <= mappedToMax; i++)
 474       {
 475         mappedColumns.addElement(i - 1);
 476       }
 477     }
 478     return mappedColumns;
 479   }
 480
 481 }