3253-omnibus save
[jalview.git] / src / jalview / io / FeaturesFile.java
1 /*
2  * Jalview - A Sequence Alignment Editor and Viewer ($$Version-Rel$$)
3  * Copyright (C) $$Year-Rel$$ The Jalview Authors
4  * 
5  * This file is part of Jalview.
6  * 
7  * Jalview is free software: you can redistribute it and/or
8  * modify it under the terms of the GNU General Public License 
9  * as published by the Free Software Foundation, either version 3
10  * of the License, or (at your option) any later version.
11  *  
12  * Jalview is distributed in the hope that it will be useful, but 
13  * WITHOUT ANY WARRANTY; without even the implied warranty 
14  * of MERCHANTABILITY or FITNESS FOR A PARTICULAR 
15  * PURPOSE.  See the GNU General Public License for more details.
16  * 
17  * You should have received a copy of the GNU General Public License
18  * along with Jalview.  If not, see <http://www.gnu.org/licenses/>.
19  * The Jalview Authors are detailed in the 'AUTHORS' file.
20  */
21 package jalview.io;
22
23 import jalview.analysis.AlignmentUtils;
24 import jalview.analysis.SequenceIdMatcher;
25 import jalview.api.AlignViewportI;
26 import jalview.api.FeatureColourI;
27 import jalview.api.FeatureRenderer;
28 import jalview.api.FeaturesSourceI;
29 import jalview.datamodel.AlignedCodonFrame;
30 import jalview.datamodel.Alignment;
31 import jalview.datamodel.AlignmentI;
32 import jalview.datamodel.MappedFeatures;
33 import jalview.datamodel.SequenceDummy;
34 import jalview.datamodel.SequenceFeature;
35 import jalview.datamodel.SequenceI;
36 import jalview.datamodel.features.FeatureMatcherSet;
37 import jalview.datamodel.features.FeatureMatcherSetI;
38 import jalview.gui.Desktop;
39 import jalview.io.gff.GffHelperFactory;
40 import jalview.io.gff.GffHelperI;
41 import jalview.schemes.FeatureColour;
42 import jalview.util.ColorUtils;
43 import jalview.util.MapList;
44 import jalview.util.ParseHtmlBodyAndLinks;
45 import jalview.util.StringUtils;
46
47 import java.awt.Color;
48 import java.io.IOException;
49 import java.util.ArrayList;
50 import java.util.Arrays;
51 import java.util.Collections;
52 import java.util.HashMap;
53 import java.util.LinkedHashMap;
54 import java.util.List;
55 import java.util.Map;
56 import java.util.Map.Entry;
57 import java.util.TreeMap;
58
59 /**
60  * Parses and writes features files, which may be in Jalview, GFF2 or GFF3
61  * format. These are tab-delimited formats but with differences in the use of
62  * columns.
63  * 
64  * A Jalview feature file may define feature colours and then declare that the
65  * remainder of the file is in GFF format with the line 'GFF'.
66  * 
67  * GFF3 files may include alignment mappings for features, which Jalview will
68  * attempt to model, and may include sequence data following a ##FASTA line.
69  * 
70  * 
71  * @author AMW
72  * @author jbprocter
73  * @author gmcarstairs
74  */
75 public class FeaturesFile extends AlignFile implements FeaturesSourceI
76 {
77   private static final String EQUALS = "=";
78
79   private static final String TAB_REGEX = "\\t";
80
81   private static final String STARTGROUP = "STARTGROUP";
82
83   private static final String ENDGROUP = "ENDGROUP";
84
85   private static final String STARTFILTERS = "STARTFILTERS";
86
87   private static final String ENDFILTERS = "ENDFILTERS";
88
89   private static final String ID_NOT_SPECIFIED = "ID_NOT_SPECIFIED";
90
91   private static final String NOTE = "Note";
92
93   protected static final String GFF_VERSION = "##gff-version";
94
95   private AlignmentI lastmatchedAl = null;
96
97   private SequenceIdMatcher matcher = null;
98
99   protected AlignmentI dataset;
100
101   protected int gffVersion;
102
103   /**
104    * Creates a new FeaturesFile object.
105    */
106   public FeaturesFile()
107   {
108   }
109
110   /**
111    * Constructor which does not parse the file immediately
112    * 
113    * @param file File or String filename
114    * @param paste
115    * @throws IOException
116    */
117   public FeaturesFile(Object file, DataSourceType paste)
118           throws IOException
119   {
120     super(false, file, paste);
121   }
122
123   /**
124    * @param source
125    * @throws IOException
126    */
127   public FeaturesFile(FileParse source) throws IOException
128   {
129     super(source);
130   }
131
132   /**
133    * Constructor that optionally parses the file immediately
134    * 
135    * @param parseImmediately
136    * @param file
137    * @param type
138    * @throws IOException
139    */
140   public FeaturesFile(boolean parseImmediately, Object file,
141           DataSourceType type) throws IOException
142   {
143     super(parseImmediately, file, type);
144   }
145
146   /**
147    * Parse GFF or sequence features file using case-independent matching,
148    * discarding URLs
149    * 
150    * @param align
151    *          - alignment/dataset containing sequences that are to be annotated
152    * @param colours
153    *          - hashtable to store feature colour definitions
154    * @param removeHTML
155    *          - process html strings into plain text
156    * @return true if features were added
157    */
158   public boolean parse(AlignmentI align,
159           Map<String, FeatureColourI> colours, boolean removeHTML)
160   {
161     return parse(align, colours, removeHTML, false);
162   }
163
164   /**
165    * Extends the default addProperties by also adding peptide-to-cDNA mappings
166    * (if any) derived while parsing a GFF file
167    */
168   @Override
169   public void addProperties(AlignmentI al)
170   {
171     super.addProperties(al);
172     if (dataset != null && dataset.getCodonFrames() != null)
173     {
174       AlignmentI ds = (al.getDataset() == null) ? al : al.getDataset();
175       for (AlignedCodonFrame codons : dataset.getCodonFrames())
176       {
177         ds.addCodonFrame(codons);
178       }
179     }
180   }
181
182   /**
183    * Parse GFF or Jalview format sequence features file
184    * 
185    * @param align
186    *          - alignment/dataset containing sequences that are to be annotated
187    * @param colours
188    *          - map to store feature colour definitions
189    * @param removeHTML
190    *          - process html strings into plain text
191    * @param relaxedIdmatching
192    *          - when true, ID matches to compound sequence IDs are allowed
193    * @return true if features were added
194    */
195   public boolean parse(AlignmentI align,
196           Map<String, FeatureColourI> colours, boolean removeHTML,
197           boolean relaxedIdmatching)
198   {
199     return parse(align, colours, null, removeHTML, relaxedIdmatching);
200   }
201
202   /**
203    * Parse GFF or Jalview format sequence features file
204    * 
205    * @param align
206    *          - alignment/dataset containing sequences that are to be annotated
207    * @param colours
208    *          - map to store feature colour definitions
209    * @param filters
210    *          - map to store feature filter definitions
211    * @param removeHTML
212    *          - process html strings into plain text
213    * @param relaxedIdmatching
214    *          - when true, ID matches to compound sequence IDs are allowed
215    * @return true if features were added
216    */
217   public boolean parse(AlignmentI align,
218           Map<String, FeatureColourI> colours,
219           Map<String, FeatureMatcherSetI> filters, boolean removeHTML,
220           boolean relaxedIdmatching)
221   {
222     Map<String, String> gffProps = new HashMap<>();
223     /*
224      * keep track of any sequences we try to create from the data
225      */
226     List<SequenceI> newseqs = new ArrayList<>();
227
228     String line = null;
229     try
230     {
231       String[] gffColumns;
232       String featureGroup = null;
233
234       while ((line = nextLine()) != null)
235       {
236         // skip comments/process pragmas
237         if (line.length() == 0 || line.startsWith("#"))
238         {
239           if (line.toLowerCase().startsWith("##"))
240           {
241             processGffPragma(line, gffProps, align, newseqs);
242           }
243           continue;
244         }
245
246         gffColumns = line.split(TAB_REGEX);
247         if (gffColumns.length == 1)
248         {
249           if (line.trim().equalsIgnoreCase("GFF"))
250           {
251             /*
252              * Jalview features file with appended GFF
253              * assume GFF2 (though it may declare ##gff-version 3)
254              */
255             gffVersion = 2;
256             continue;
257           }
258         }
259
260         if (gffColumns.length > 0 && gffColumns.length < 4)
261         {
262           /*
263            * if 2 or 3 tokens, we anticipate either 'startgroup', 'endgroup' or
264            * a feature type colour specification
265            */
266           String ft = gffColumns[0];
267           if (ft.equalsIgnoreCase(STARTFILTERS))
268           {
269             parseFilters(filters);
270             continue;
271           }
272           if (ft.equalsIgnoreCase(STARTGROUP))
273           {
274             featureGroup = gffColumns[1];
275           }
276           else if (ft.equalsIgnoreCase(ENDGROUP))
277           {
278             // We should check whether this is the current group,
279             // but at present there's no way of showing more than 1 group
280             featureGroup = null;
281           }
282           else
283           {
284             String colscheme = gffColumns[1];
285             FeatureColourI colour = FeatureColour
286                     .parseJalviewFeatureColour(colscheme);
287             if (colour != null)
288             {
289               colours.put(ft, colour);
290             }
291           }
292           continue;
293         }
294
295         /*
296          * if not a comment, GFF pragma, startgroup, endgroup or feature
297          * colour specification, that just leaves a feature details line
298          * in either Jalview or GFF format
299          */
300         if (gffVersion == 0)
301         {
302           parseJalviewFeature(line, gffColumns, align, colours, removeHTML,
303                   relaxedIdmatching, featureGroup);
304         }
305         else
306         {
307           parseGff(gffColumns, align, relaxedIdmatching, newseqs);
308         }
309       }
310       resetMatcher();
311     } catch (Exception ex)
312     {
313       // should report somewhere useful for UI if necessary
314       warningMessage = ((warningMessage == null) ? "" : warningMessage)
315               + "Parsing error at\n" + line;
316       System.out.println("Error parsing feature file: " + ex + "\n" + line);
317       ex.printStackTrace(System.err);
318       resetMatcher();
319       return false;
320     }
321
322     /*
323      * experimental - add any dummy sequences with features to the alignment
324      * - we need them for Ensembl feature extraction - though maybe not otherwise
325      */
326     for (SequenceI newseq : newseqs)
327     {
328       if (newseq.getFeatures().hasFeatures())
329       {
330         align.addSequence(newseq);
331       }
332     }
333     return true;
334   }
335
336   /**
337    * Reads input lines from STARTFILTERS to ENDFILTERS and adds a feature type
338    * filter to the map for each line parsed. After exit from this method,
339    * nextLine() should return the line after ENDFILTERS (or we are already at
340    * end of file if ENDFILTERS was missing).
341    * 
342    * @param filters
343    * @throws IOException
344    */
345   protected void parseFilters(Map<String, FeatureMatcherSetI> filters)
346           throws IOException
347   {
348     String line;
349     while ((line = nextLine()) != null)
350     {
351       if (line.toUpperCase().startsWith(ENDFILTERS))
352       {
353         return;
354       }
355       String[] tokens = line.split(TAB_REGEX);
356       if (tokens.length != 2)
357       {
358         System.err.println(String.format("Invalid token count %d for %d",
359                 tokens.length, line));
360       }
361       else
362       {
363         String featureType = tokens[0];
364         FeatureMatcherSetI fm = FeatureMatcherSet.fromString(tokens[1]);
365         if (fm != null && filters != null)
366         {
367           filters.put(featureType, fm);
368         }
369       }
370     }
371   }
372
373   /**
374    * Try to parse a Jalview format feature specification and add it as a
375    * sequence feature to any matching sequences in the alignment. Returns true
376    * if successful (a feature was added), or false if not.
377    * 
378    * @param line
379    * @param gffColumns
380    * @param alignment
381    * @param featureColours
382    * @param removeHTML
383    * @param relaxedIdmatching
384    * @param featureGroup
385    */
386   protected boolean parseJalviewFeature(String line, String[] gffColumns,
387           AlignmentI alignment, Map<String, FeatureColourI> featureColours,
388           boolean removeHTML, boolean relaxedIdMatching,
389           String featureGroup)
390   {
391     /*
392      * tokens: description seqid seqIndex start end type [score]
393      */
394     if (gffColumns.length < 6)
395     {
396       System.err.println("Ignoring feature line '" + line
397               + "' with too few columns (" + gffColumns.length + ")");
398       return false;
399     }
400     String desc = gffColumns[0];
401     String seqId = gffColumns[1];
402     SequenceI seq = findSequence(seqId, alignment, null, relaxedIdMatching);
403
404     if (!ID_NOT_SPECIFIED.equals(seqId))
405     {
406       seq = findSequence(seqId, alignment, null, relaxedIdMatching);
407     }
408     else
409     {
410       seqId = null;
411       seq = null;
412       String seqIndex = gffColumns[2];
413       try
414       {
415         int idx = Integer.parseInt(seqIndex);
416         seq = alignment.getSequenceAt(idx);
417       } catch (NumberFormatException ex)
418       {
419         System.err.println("Invalid sequence index: " + seqIndex);
420       }
421     }
422
423     if (seq == null)
424     {
425       System.out.println("Sequence not found: " + line);
426       return false;
427     }
428
429     int startPos = Integer.parseInt(gffColumns[3]);
430     int endPos = Integer.parseInt(gffColumns[4]);
431
432     String ft = gffColumns[5];
433
434     if (!featureColours.containsKey(ft))
435     {
436       /* 
437        * Perhaps an old style groups file with no colours -
438        * synthesize a colour from the feature type
439        */
440       Color colour = ColorUtils.createColourFromName(ft);
441       featureColours.put(ft, new FeatureColour(colour));
442     }
443     SequenceFeature sf = null;
444     if (gffColumns.length > 6)
445     {
446       float score = Float.NaN;
447       try
448       {
449         score = Float.valueOf(gffColumns[6]).floatValue();
450       } catch (NumberFormatException ex)
451       {
452         sf = new SequenceFeature(ft, desc, startPos, endPos, featureGroup);
453       }
454       sf = new SequenceFeature(ft, desc, startPos, endPos, score,
455               featureGroup);
456     }
457     else
458     {
459       sf = new SequenceFeature(ft, desc, startPos, endPos, featureGroup);
460     }
461
462     parseDescriptionHTML(sf, removeHTML);
463
464     seq.addSequenceFeature(sf);
465
466     while (seqId != null
467             && (seq = alignment.findName(seq, seqId, false)) != null)
468     {
469       seq.addSequenceFeature(new SequenceFeature(sf));
470     }
471     return true;
472   }
473
474   /**
475    * clear any temporary handles used to speed up ID matching
476    */
477   protected void resetMatcher()
478   {
479     lastmatchedAl = null;
480     matcher = null;
481   }
482
483   /**
484    * Returns a sequence matching the given id, as follows
485    * <ul>
486    * <li>strict matching is on exact sequence name</li>
487    * <li>relaxed matching allows matching on a token within the sequence name,
488    * or a dbxref</li>
489    * <li>first tries to find a match in the alignment sequences</li>
490    * <li>else tries to find a match in the new sequences already generated while
491    * parsing the features file</li>
492    * <li>else creates a new placeholder sequence, adds it to the new sequences
493    * list, and returns it</li>
494    * </ul>
495    * 
496    * @param seqId
497    * @param align
498    * @param newseqs
499    * @param relaxedIdMatching
500    * 
501    * @return
502    */
503   protected SequenceI findSequence(String seqId, AlignmentI align,
504           List<SequenceI> newseqs, boolean relaxedIdMatching)
505   {
506     // TODO encapsulate in SequenceIdMatcher, share the matcher
507     // with the GffHelper (removing code duplication)
508     SequenceI match = null;
509     if (relaxedIdMatching)
510     {
511       if (lastmatchedAl != align)
512       {
513         lastmatchedAl = align;
514         matcher = new SequenceIdMatcher(align.getSequencesArray());
515         if (newseqs != null)
516         {
517           matcher.addAll(newseqs);
518         }
519       }
520       match = matcher.findIdMatch(seqId);
521     }
522     else
523     {
524       match = align.findName(seqId, true);
525       if (match == null && newseqs != null)
526       {
527         for (SequenceI m : newseqs)
528         {
529           if (seqId.equals(m.getName()))
530           {
531             return m;
532           }
533         }
534       }
535
536     }
537     if (match == null && newseqs != null)
538     {
539       match = new SequenceDummy(seqId);
540       if (relaxedIdMatching)
541       {
542         matcher.addAll(Arrays.asList(new SequenceI[] { match }));
543       }
544       // add dummy sequence to the newseqs list
545       newseqs.add(match);
546     }
547     return match;
548   }
549
550   public void parseDescriptionHTML(SequenceFeature sf, boolean removeHTML)
551   {
552     if (sf.getDescription() == null)
553     {
554       return;
555     }
556     ParseHtmlBodyAndLinks parsed = new ParseHtmlBodyAndLinks(
557             sf.getDescription(), removeHTML, newline);
558
559     if (removeHTML)
560     {
561       sf.setDescription(parsed.getNonHtmlContent());
562     }
563
564     for (String link : parsed.getLinks())
565     {
566       sf.addLink(link);
567     }
568   }
569
570   /**
571    * Returns contents of a Jalview format features file, for visible features, as
572    * filtered by type and group. Features with a null group are displayed if their
573    * feature type is visible. Non-positional features may optionally be included
574    * (with no check on type or group).
575    * 
576    * @param sequences
577    * @param fr
578    * @param includeNonPositional
579    *                               if true, include non-positional features
580    *                               (regardless of group or type)
581    * @param includeComplement
582    *                               if true, include visible complementary
583    *                               (CDS/protein) positional features, with
584    *                               locations converted to local sequence
585    *                               coordinates
586    * @return
587    */
588   public String printJalviewFormat(SequenceI[] sequences,
589           FeatureRenderer fr, boolean includeNonPositional,
590           boolean includeComplement)
591   {
592     Map<String, FeatureColourI> visibleColours = fr
593             .getDisplayedFeatureCols();
594     Map<String, FeatureMatcherSetI> featureFilters = fr.getFeatureFilters();
595
596     // BH check this is out?
597 //    if (!includeNonPositional
598 //            && (visibleColours == null || visibleColours.isEmpty()))
599 //    {
600 //      // no point continuing.
601 //      return "No Features Visible";
602 //    }
603
604     /*
605      * write out feature colours (if we know them)
606      */
607     // TODO: decide if feature links should also be written here ?
608     StringBuilder out = new StringBuilder(256);
609     if (visibleColours != null)
610     {
611       for (Entry<String, FeatureColourI> featureColour : visibleColours
612               .entrySet())
613       {
614         FeatureColourI colour = featureColour.getValue();
615         out.append(colour.toJalviewFormat(featureColour.getKey())).append(
616                 newline);
617       }
618     }
619
620     String[] types = visibleColours == null ? new String[0]
621             : visibleColours.keySet()
622                     .toArray(new String[visibleColours.keySet().size()]);
623
624     /*
625      * feature filters if any
626      */
627     outputFeatureFilters(out, visibleColours, featureFilters);
628
629     /*
630      * output features within groups
631      */
632     int count = outputFeaturesByGroup(out, fr, types, sequences,
633             includeNonPositional);
634
635     if (includeComplement)
636     {
637       count += outputComplementFeatures(out, fr, sequences);
638     }
639
640     return count > 0 ? out.toString() : "No Features Visible";
641   }
642
643   /**
644    * Outputs any visible complementary (CDS/peptide) positional features as
645    * Jalview format, within feature group. The coordinates of the linked features
646    * are converted to the corresponding positions of the local sequences.
647    * 
648    * @param out
649    * @param fr
650    * @param sequences
651    * @return
652    */
653   private int outputComplementFeatures(StringBuilder out,
654           FeatureRenderer fr, SequenceI[] sequences)
655   {
656     AlignViewportI comp = fr.getViewport().getCodingComplement();
657     FeatureRenderer fr2 = Desktop.getAlignFrameFor(comp)
658             .getFeatureRenderer();
659
660     /*
661      * bin features by feature group and sequence
662      */
663     Map<String, Map<String, List<SequenceFeature>>> map = new TreeMap<>(
664             String.CASE_INSENSITIVE_ORDER);
665     int count = 0;
666
667     for (SequenceI seq : sequences)
668     {
669       /*
670        * find complementary features
671        */
672       List<SequenceFeature> complementary = findComplementaryFeatures(seq,
673               fr2);
674       String seqName = seq.getName();
675
676       for (SequenceFeature sf : complementary)
677       {
678         String group = sf.getFeatureGroup();
679         if (!map.containsKey(group))
680         {
681           map.put(group, new LinkedHashMap<>()); // preserves sequence order
682         }
683         Map<String, List<SequenceFeature>> groupFeatures = map.get(group);
684         if (!groupFeatures.containsKey(seqName))
685         {
686           groupFeatures.put(seqName, new ArrayList<>());
687         }
688         List<SequenceFeature> foundFeatures = groupFeatures.get(seqName);
689         foundFeatures.add(sf);
690         count++;
691       }
692     }
693
694     /*
695      * output features by group
696      */
697     for (Entry<String, Map<String, List<SequenceFeature>>> groupFeatures : map.entrySet())
698     {
699       out.append(newline);
700       String group = groupFeatures.getKey();
701       if (!"".equals(group))
702       {
703         out.append(STARTGROUP).append(TAB).append(group).append(newline);
704       }
705       Map<String, List<SequenceFeature>> seqFeaturesMap = groupFeatures
706               .getValue();
707       for (Entry<String, List<SequenceFeature>> seqFeatures : seqFeaturesMap
708               .entrySet())
709       {
710         String sequenceName = seqFeatures.getKey();
711         for (SequenceFeature sf : seqFeatures.getValue())
712         {
713           formatJalviewFeature(out, sequenceName, sf);
714         }
715       }
716       if (!"".equals(group))
717       {
718         out.append(ENDGROUP).append(TAB).append(group).append(newline);
719       }
720     }
721
722     return count;
723   }
724
725   /**
726    * Answers a list of mapped features visible in the (CDS/protein) complement,
727    * with feature positions translated to local sequence coordinates
728    * 
729    * @param seq
730    * @param fr2
731    * @return
732    */
733   protected List<SequenceFeature> findComplementaryFeatures(SequenceI seq,
734           FeatureRenderer fr2)
735   {
736     /*
737      * avoid duplication of features (e.g. peptide feature 
738      * at all 3 mapped codon positions)
739      */
740     List<SequenceFeature> found = new ArrayList<>();
741     List<SequenceFeature> complementary = new ArrayList<>();
742
743     for (int pos = seq.getStart(); pos <= seq.getEnd(); pos++)
744     {
745       MappedFeatures mf = fr2.findComplementFeaturesAtResidue(seq, pos);
746
747       if (mf != null)
748       {
749         MapList mapping = mf.mapping.getMap();
750         for (SequenceFeature sf : mf.features)
751         {
752           /*
753            * make a virtual feature with local coordinates
754            */
755           if (!found.contains(sf))
756           {
757             String group = sf.getFeatureGroup();
758             if (group == null)
759             {
760               group = "";
761             }
762             found.add(sf);
763             int begin = sf.getBegin();
764             int end = sf.getEnd();
765             int[] range = mf.mapping.getTo() == seq.getDatasetSequence()
766                     ? mapping.locateInTo(begin, end)
767                     : mapping.locateInFrom(begin, end);
768             SequenceFeature sf2 = new SequenceFeature(sf, range[0],
769                     range[1], group, sf.getScore());
770             complementary.add(sf2);
771           }
772         }
773       }
774     }
775
776     return complementary;
777   }
778
779   /**
780    * Outputs any feature filters defined for visible feature types, sandwiched by
781    * STARTFILTERS and ENDFILTERS lines
782    * 
783    * @param out
784    * @param visible
785    * @param featureFilters
786    */
787   void outputFeatureFilters(StringBuilder out,
788           Map<String, FeatureColourI> visible,
789           Map<String, FeatureMatcherSetI> featureFilters)
790   {
791     if (visible == null || featureFilters == null
792             || featureFilters.isEmpty())
793     {
794       return;
795     }
796
797     boolean first = true;
798     for (String featureType : visible.keySet())
799     {
800       FeatureMatcherSetI filter = featureFilters.get(featureType);
801       if (filter != null)
802       {
803         if (first)
804         {
805           first = false;
806           out.append(newline).append(STARTFILTERS).append(newline);
807         }
808         out.append(featureType).append(TAB).append(filter.toStableString())
809                 .append(newline);
810       }
811     }
812     if (!first)
813     {
814       out.append(ENDFILTERS).append(newline);
815     }
816
817   }
818
819   /**
820    * Appends output of visible sequence features within feature groups to the
821    * output buffer. Groups other than the null or empty group are sandwiched by
822    * STARTGROUP and ENDGROUP lines. Answers the number of features written.
823    * 
824    * @param out
825    * @param fr
826    * @param featureTypes
827    * @param sequences
828    * @param includeNonPositional
829    * @return
830    */
831   private int outputFeaturesByGroup(StringBuilder out,
832           FeatureRenderer fr, String[] featureTypes,
833           SequenceI[] sequences, boolean includeNonPositional)
834   {
835     List<String> featureGroups = fr.getFeatureGroups();
836
837     /*
838      * sort groups alphabetically, and ensure that features with a
839      * null or empty group are output after those in named groups
840      */
841     List<String> sortedGroups = new ArrayList<>(featureGroups);
842     sortedGroups.remove(null);
843     sortedGroups.remove("");
844     Collections.sort(sortedGroups);
845     sortedGroups.add(null);
846     sortedGroups.add("");
847
848     int count = 0;
849     List<String> visibleGroups = fr.getDisplayedFeatureGroups();
850
851     /*
852      * loop over all groups (may be visible or not);
853      * non-positional features are output even if group is not visible
854      */
855     for (String group : sortedGroups)
856     {
857       boolean firstInGroup = true;
858       boolean isNullGroup = group == null || "".equals(group);
859
860       for (int i = 0; i < sequences.length; i++)
861       {
862         String sequenceName = sequences[i].getName();
863         List<SequenceFeature> features = new ArrayList<>();
864
865         /*
866          * get any non-positional features in this group, if wanted
867          * (for any feature type, whether visible or not)
868          */
869         if (includeNonPositional)
870         {
871           features.addAll(sequences[i].getFeatures()
872                   .getFeaturesForGroup(false, group));
873         }
874
875         /*
876          * add positional features for visible feature types, but
877          * (for named groups) only if feature group is visible
878          */
879         if (featureTypes.length > 0
880                 && (isNullGroup || visibleGroups.contains(group)))
881         {
882           features.addAll(sequences[i].getFeatures().getFeaturesForGroup(
883                   true, group, featureTypes));
884         }
885
886         for (SequenceFeature sf : features)
887         {
888           if (sf.isNonPositional() || fr.isVisible(sf))
889           {
890             count++;
891             if (firstInGroup)
892             {
893               out.append(newline);
894               if (!isNullGroup)
895               {
896                 out.append(STARTGROUP).append(TAB).append(group)
897                         .append(newline);
898               }
899             }
900             firstInGroup = false;
901             formatJalviewFeature(out, sequenceName, sf);
902           }
903         }
904       }
905
906       if (!isNullGroup && !firstInGroup)
907       {
908         out.append(ENDGROUP).append(TAB).append(group).append(newline);
909       }
910     }
911     return count;
912   }
913
914   /**
915    * Formats one feature in Jalview format and appends to the string buffer
916    * 
917    * @param out
918    * @param sequenceName
919    * @param sequenceFeature
920    */
921   protected String formatJalviewFeature(
922           StringBuilder out, String sequenceName,
923           SequenceFeature sequenceFeature)
924   {
925     if (sequenceFeature.description == null
926             || sequenceFeature.description.equals(""))
927     {
928       out.append(sequenceFeature.type).append(TAB);
929     }
930     else
931     {
932       if (sequenceFeature.links != null
933               && sequenceFeature.getDescription().indexOf("<html>") == -1)
934       {
935         out.append("<html>");
936       }
937
938       out.append(sequenceFeature.description);
939       if (sequenceFeature.links != null)
940       {
941         for (int l = 0; l < sequenceFeature.links.size(); l++)
942         {
943           String label = sequenceFeature.links.elementAt(l);
944           String href = label.substring(label.indexOf("|") + 1);
945           label = label.substring(0, label.indexOf("|"));
946
947           if (sequenceFeature.description.indexOf(href) == -1)
948           {
949             out.append(" <a href=\"").append(href).append("\">")
950                     .append(label).append("</a>");
951           }
952         }
953
954         if (sequenceFeature.getDescription().indexOf("</html>") == -1)
955         {
956           out.append("</html>");
957         }
958       }
959
960       out.append(TAB);
961     }
962     out.append(sequenceName);
963     out.append("\t-1\t");
964     out.append(sequenceFeature.begin);
965     out.append(TAB);
966     out.append(sequenceFeature.end);
967     out.append(TAB);
968     out.append(sequenceFeature.type);
969     if (!Float.isNaN(sequenceFeature.score))
970     {
971       out.append(TAB);
972       out.append(sequenceFeature.score);
973     }
974     out.append(newline);
975
976     return out.toString();
977   }
978
979   /**
980    * Parse method that is called when a GFF file is dragged to the desktop
981    */
982   @Override
983   public void parse()
984   {
985     AlignViewportI av = getViewport();
986     if (av != null)
987     {
988       AlignmentI a = av.getAlignment();
989       if (a != null)
990       {
991         dataset = a.getDataset();
992       }
993       if (dataset == null)
994       {
995         // working in the applet context ?
996         dataset = a;
997       }
998     }
999     else
1000     {
1001       dataset = new Alignment(new SequenceI[] {});
1002     }
1003
1004     Map<String, FeatureColourI> featureColours = new HashMap<>();
1005     boolean parseResult = parse(dataset, featureColours, false, true);
1006     if (!parseResult)
1007     {
1008       // pass error up somehow
1009     }
1010     if (av != null)
1011     {
1012       // update viewport with the dataset data ?
1013     }
1014     else
1015     {
1016       setSeqs(dataset.getSequencesArray());
1017     }
1018   }
1019
1020   /**
1021    * Implementation of unused abstract method
1022    * 
1023    * @return error message
1024    */
1025   @Override
1026   public String print(SequenceI[] sqs, boolean jvsuffix)
1027   {
1028     System.out.println("Use printGffFormat() or printJalviewFormat()");
1029     return null;
1030   }
1031
1032   /**
1033    * Returns features output in GFF2 format
1034    * 
1035    * @param sequences
1036    *          the sequences whose features are to be output
1037    * @param visible
1038    *          a map whose keys are the type names of visible features
1039    * @param visibleFeatureGroups
1040    * @param includeNonPositionalFeatures
1041    * @param includeComplement
1042    * @return
1043    */
1044   public String printGffFormat(SequenceI[] sequences,
1045           FeatureRenderer fr, boolean includeNonPositionalFeatures,
1046           boolean includeComplement)
1047   {
1048     FeatureRenderer fr2 = null;
1049     if (includeComplement)
1050   {
1051       AlignViewportI comp = fr.getViewport().getCodingComplement();
1052       fr2 = Desktop.getAlignFrameFor(comp).getFeatureRenderer();
1053     }
1054
1055     Map<String, FeatureColourI> visibleColours = fr.getDisplayedFeatureCols();
1056
1057     StringBuilder out = new StringBuilder(256);
1058
1059     out.append(String.format("%s %d\n", GFF_VERSION, gffVersion == 0 ? 2 : gffVersion));
1060
1061     String[] types = visibleColours == null ? new String[0]
1062             : visibleColours.keySet()
1063                     .toArray(new String[visibleColours.keySet().size()]);
1064
1065     for (SequenceI seq : sequences)
1066     {
1067       List<SequenceFeature> seqFeatures = new ArrayList<>();
1068       List<SequenceFeature> features = new ArrayList<>();
1069       if (includeNonPositionalFeatures)
1070       {
1071         features.addAll(seq.getFeatures().getNonPositionalFeatures());
1072       }
1073       if (visibleColours != null && !visibleColours.isEmpty())
1074       {
1075         features.addAll(seq.getFeatures().getPositionalFeatures(types));
1076       }
1077
1078       for (SequenceFeature sf : features)
1079       {
1080         if (sf.isNonPositional() || fr.isVisible(sf))
1081         {
1082           /*
1083            * drop features hidden by group visibility, colour threshold,
1084            * or feature filter condition
1085            */
1086           seqFeatures.add(sf);
1087         }
1088       }
1089
1090       if (includeComplement)
1091       {
1092         seqFeatures.addAll(findComplementaryFeatures(seq, fr2));
1093       }
1094
1095       /*
1096        * sort features here if wanted
1097        */
1098       for (SequenceFeature sf : seqFeatures)
1099       {
1100         formatGffFeature(out, seq, sf);
1101         out.append(newline);
1102       }
1103     }
1104
1105     return out.toString();
1106   }
1107
1108   /**
1109    * Formats one feature as GFF and appends to the string buffer
1110    */
1111   private void formatGffFeature(StringBuilder out, SequenceI seq,
1112           SequenceFeature sf)
1113   {
1114         String source = sf.featureGroup;
1115         if (source == null)
1116         {
1117           source = sf.getDescription();
1118         }
1119
1120         out.append(seq.getName());
1121         out.append(TAB);
1122         out.append(source);
1123         out.append(TAB);
1124         out.append(sf.type);
1125         out.append(TAB);
1126         out.append(sf.begin);
1127         out.append(TAB);
1128         out.append(sf.end);
1129         out.append(TAB);
1130         out.append(sf.score);
1131         out.append(TAB);
1132
1133         int strand = sf.getStrand();
1134         out.append(strand == 1 ? "+" : (strand == -1 ? "-" : "."));
1135         out.append(TAB);
1136
1137         String phase = sf.getPhase();
1138         out.append(phase == null ? "." : phase);
1139
1140     if (sf.otherDetails != null && !sf.otherDetails.isEmpty())
1141         {
1142       Map<String, Object> map = sf.otherDetails;
1143       formatAttributes(out, map);
1144     }
1145   }
1146
1147   /**
1148    * A helper method that outputs attributes stored in the map as
1149    * semicolon-delimited values e.g.
1150    * 
1151    * <pre>
1152    * AC_Male=0;AF_NFE=0.00000e 00;Hom_FIN=0;GQ_MEDIAN=9
1153    * </pre>
1154    * 
1155    * A map-valued attribute is formatted as a comma-delimited list within braces,
1156    * for example
1157    * 
1158    * <pre>
1159    * jvmap_CSQ={ALLELE_NUM=1,UNIPARC=UPI0002841053,Feature=ENST00000585561}
1160    * </pre>
1161    * 
1162    * The {@code jvmap_} prefix designates a values map and is removed if the value
1163    * is parsed when read in. (The GFF3 specification allows 'semi-structured data'
1164    * to be represented provided the attribute name begins with a lower case
1165    * letter.)
1166    * 
1167    * @param sb
1168    * @param map
1169    * @see http://gmod.org/wiki/GFF3#GFF3_Format
1170    */
1171   void formatAttributes(StringBuilder sb, Map<String, Object> map)
1172   {
1173     sb.append(TAB);
1174     boolean first = true;
1175     for (String key : map.keySet())
1176     {
1177       if (SequenceFeature.STRAND.equals(key)
1178               || SequenceFeature.PHASE.equals(key))
1179       {
1180         /*
1181          * values stashed in map but output to their own columns
1182          */
1183         continue;
1184       }
1185       {
1186         if (!first)
1187         {
1188           sb.append(";");
1189         }
1190       }
1191       first = false;
1192       Object value = map.get(key);
1193       if (value instanceof Map<?, ?>)
1194       {
1195         formatMapAttribute(sb, key, (Map<?, ?>) value);
1196       }
1197       else
1198       {
1199         String formatted = StringUtils.urlEncode(value.toString(),
1200                 GffHelperI.GFF_ENCODABLE);
1201         sb.append(key).append(EQUALS).append(formatted);
1202       }
1203     }
1204   }
1205
1206   /**
1207    * Formats the map entries as
1208    * 
1209    * <pre>
1210    * key=key1=value1,key2=value2,...
1211    * </pre>
1212    * 
1213    * and appends this to the string buffer
1214    * 
1215    * @param sb
1216    * @param key
1217    * @param map
1218    */
1219   private void formatMapAttribute(StringBuilder sb, String key,
1220           Map<?, ?> map)
1221   {
1222     if (map == null || map.isEmpty())
1223     {
1224       return;
1225     }
1226
1227     /*
1228      * AbstractMap.toString would be a shortcut here, but more reliable
1229      * to code the required format in case toString changes in future
1230      */
1231     sb.append(key).append(EQUALS);
1232     boolean first = true;
1233     for (Entry<?, ?> entry : map.entrySet())
1234     {
1235       if (!first)
1236       {
1237         sb.append(",");
1238       }
1239       first = false;
1240       sb.append(entry.getKey().toString()).append(EQUALS);
1241       String formatted = StringUtils.urlEncode(entry.getValue().toString(),
1242               GffHelperI.GFF_ENCODABLE);
1243       sb.append(formatted);
1244     }
1245   }
1246
1247   /**
1248    * Returns a mapping given list of one or more Align descriptors (exonerate
1249    * format)
1250    * 
1251    * @param alignedRegions
1252    *          a list of "Align fromStart toStart fromCount"
1253    * @param mapIsFromCdna
1254    *          if true, 'from' is dna, else 'from' is protein
1255    * @param strand
1256    *          either 1 (forward) or -1 (reverse)
1257    * @return
1258    * @throws IOException
1259    */
1260   protected MapList constructCodonMappingFromAlign(
1261           List<String> alignedRegions, boolean mapIsFromCdna, int strand)
1262           throws IOException
1263   {
1264     if (strand == 0)
1265     {
1266       throw new IOException(
1267               "Invalid strand for a codon mapping (cannot be 0)");
1268     }
1269     int regions = alignedRegions.size();
1270     // arrays to hold [start, end] for each aligned region
1271     int[] fromRanges = new int[regions * 2]; // from dna
1272     int[] toRanges = new int[regions * 2]; // to protein
1273     int fromRangesIndex = 0;
1274     int toRangesIndex = 0;
1275
1276     for (String range : alignedRegions)
1277     {
1278       /* 
1279        * Align mapFromStart mapToStart mapFromCount
1280        * e.g. if mapIsFromCdna
1281        *     Align 11270 143 120
1282        * means:
1283        *     120 bases from pos 11270 align to pos 143 in peptide
1284        * if !mapIsFromCdna this would instead be
1285        *     Align 143 11270 40 
1286        */
1287       String[] tokens = range.split(" ");
1288       if (tokens.length != 3)
1289       {
1290         throw new IOException("Wrong number of fields for Align");
1291       }
1292       int fromStart = 0;
1293       int toStart = 0;
1294       int fromCount = 0;
1295       try
1296       {
1297         fromStart = Integer.parseInt(tokens[0]);
1298         toStart = Integer.parseInt(tokens[1]);
1299         fromCount = Integer.parseInt(tokens[2]);
1300       } catch (NumberFormatException nfe)
1301       {
1302         throw new IOException(
1303                 "Invalid number in Align field: " + nfe.getMessage());
1304       }
1305
1306       /*
1307        * Jalview always models from dna to protein, so adjust values if the
1308        * GFF mapping is from protein to dna
1309        */
1310       if (!mapIsFromCdna)
1311       {
1312         fromCount *= 3;
1313         int temp = fromStart;
1314         fromStart = toStart;
1315         toStart = temp;
1316       }
1317       fromRanges[fromRangesIndex++] = fromStart;
1318       fromRanges[fromRangesIndex++] = fromStart + strand * (fromCount - 1);
1319
1320       /*
1321        * If a codon has an intron gap, there will be contiguous 'toRanges';
1322        * this is handled for us by the MapList constructor. 
1323        * (It is not clear that exonerate ever generates this case)  
1324        */
1325       toRanges[toRangesIndex++] = toStart;
1326       toRanges[toRangesIndex++] = toStart + (fromCount - 1) / 3;
1327     }
1328
1329     return new MapList(fromRanges, toRanges, 3, 1);
1330   }
1331
1332   /**
1333    * Parse a GFF format feature. This may include creating a 'dummy' sequence to
1334    * hold the feature, or for its mapped sequence, or both, to be resolved
1335    * either later in the GFF file (##FASTA section), or when the user loads
1336    * additional sequences.
1337    * 
1338    * @param gffColumns
1339    * @param alignment
1340    * @param relaxedIdMatching
1341    * @param newseqs
1342    * @return
1343    */
1344   protected SequenceI parseGff(String[] gffColumns, AlignmentI alignment,
1345           boolean relaxedIdMatching, List<SequenceI> newseqs)
1346   {
1347     /*
1348      * GFF: seqid source type start end score strand phase [attributes]
1349      */
1350     if (gffColumns.length < 5)
1351     {
1352       System.err.println("Ignoring GFF feature line with too few columns ("
1353               + gffColumns.length + ")");
1354       return null;
1355     }
1356
1357     /*
1358      * locate referenced sequence in alignment _or_ 
1359      * as a forward or external reference (SequenceDummy)
1360      */
1361     String seqId = gffColumns[0];
1362     SequenceI seq = findSequence(seqId, alignment, newseqs,
1363             relaxedIdMatching);
1364
1365     SequenceFeature sf = null;
1366     GffHelperI helper = GffHelperFactory.getHelper(gffColumns);
1367     if (helper != null)
1368     {
1369       try
1370       {
1371         sf = helper.processGff(seq, gffColumns, alignment, newseqs,
1372                 relaxedIdMatching);
1373         if (sf != null)
1374         {
1375           seq.addSequenceFeature(sf);
1376           while ((seq = alignment.findName(seq, seqId, true)) != null)
1377           {
1378             seq.addSequenceFeature(new SequenceFeature(sf));
1379           }
1380         }
1381       } catch (IOException e)
1382       {
1383         System.err.println("GFF parsing failed with: " + e.getMessage());
1384         return null;
1385       }
1386     }
1387
1388     return seq;
1389   }
1390
1391   // BH! check that we did not lose something here. 
1392 //  /**
1393 //   * Process the 'column 9' data of the GFF file. This is less formally defined,
1394 //   * and its interpretation will vary depending on the tool that has generated
1395 //   * it.
1396 //   * 
1397 //   * @param attributes
1398 //   * @param sf
1399 //   */
1400 //  protected void processGffColumnNine(String attributes, SequenceFeature sf)
1401 //  {
1402 //    sf.setAttributes(attributes);
1403 //
1404 //    /*
1405 //     * Parse attributes in column 9 and add them to the sequence feature's 
1406 //     * 'otherData' table; use Note as a best proxy for description
1407 //     */
1408 //    char nameValueSeparator = gffVersion == 3 ? '=' : ' ';
1409 //    // TODO check we don't break GFF2 values which include commas here
1410 //    Map<String, List<String>> nameValues = GffHelperBase
1411 //            .parseNameValuePairs(attributes, ";", nameValueSeparator, ",");
1412 //    for (Entry<String, List<String>> attr : nameValues.entrySet())
1413 //    {
1414 //      String values = StringUtils.listToDelimitedString(attr.getValue(),
1415 //              "; ");
1416 //      sf.setValue(attr.getKey(), values);
1417 //      if (NOTE.equals(attr.getKey()))
1418 //      {
1419 //        sf.setDescription(values);
1420 //      }
1421 //    }
1422 //  }
1423
1424   /**
1425    * After encountering ##fasta in a GFF3 file, process the remainder of the
1426    * file as FAST sequence data. Any placeholder sequences created during
1427    * feature parsing are updated with the actual sequences.
1428    * 
1429    * @param align
1430    * @param newseqs
1431    * @throws IOException
1432    */
1433   protected void processAsFasta(AlignmentI align, List<SequenceI> newseqs)
1434           throws IOException
1435   {
1436     try
1437     {
1438       mark();
1439     } catch (IOException q)
1440     {
1441     }
1442     FastaFile parser = new FastaFile(this);
1443     List<SequenceI> includedseqs = parser.getSeqs();
1444
1445     SequenceIdMatcher smatcher = new SequenceIdMatcher(newseqs);
1446
1447     /*
1448      * iterate over includedseqs, and replacing matching ones with newseqs
1449      * sequences. Generic iterator not used here because we modify
1450      * includedseqs as we go
1451      */
1452     for (int p = 0, pSize = includedseqs.size(); p < pSize; p++)
1453     {
1454       // search for any dummy seqs that this sequence can be used to update
1455       SequenceI includedSeq = includedseqs.get(p);
1456       SequenceI dummyseq = smatcher.findIdMatch(includedSeq);
1457       if (dummyseq != null && dummyseq instanceof SequenceDummy)
1458       {
1459         // probably have the pattern wrong
1460         // idea is that a flyweight proxy for a sequence ID can be created for
1461         // 1. stable reference creation
1462         // 2. addition of annotation
1463         // 3. future replacement by a real sequence
1464         // current pattern is to create SequenceDummy objects - a convenience
1465         // constructor for a Sequence.
1466         // problem is that when promoted to a real sequence, all references
1467         // need to be updated somehow. We avoid that by keeping the same object.
1468         ((SequenceDummy) dummyseq).become(includedSeq);
1469         dummyseq.createDatasetSequence();
1470
1471         /*
1472          * Update mappings so they are now to the dataset sequence
1473          */
1474         for (AlignedCodonFrame mapping : align.getCodonFrames())
1475         {
1476           mapping.updateToDataset(dummyseq);
1477         }
1478
1479         /*
1480          * replace parsed sequence with the realised forward reference
1481          */
1482         includedseqs.set(p, dummyseq);
1483
1484         /*
1485          * and remove from the newseqs list
1486          */
1487         newseqs.remove(dummyseq);
1488       }
1489     }
1490
1491     /*
1492      * finally add sequences to the dataset
1493      */
1494     for (SequenceI seq : includedseqs)
1495     {
1496       // experimental: mapping-based 'alignment' to query sequence
1497       AlignmentUtils.alignSequenceAs(seq, align,
1498               String.valueOf(align.getGapCharacter()), false, true);
1499
1500       // rename sequences if GFF handler requested this
1501       // TODO a more elegant way e.g. gffHelper.postProcess(newseqs) ?
1502       List<SequenceFeature> sfs = seq.getFeatures().getPositionalFeatures();
1503       if (!sfs.isEmpty())
1504       {
1505         String newName = (String) sfs.get(0).getValue(
1506                 GffHelperI.RENAME_TOKEN);
1507         if (newName != null)
1508         {
1509           seq.setName(newName);
1510         }
1511       }
1512       align.addSequence(seq);
1513     }
1514   }
1515
1516   /**
1517    * Process a ## directive
1518    * 
1519    * @param line
1520    * @param gffProps
1521    * @param align
1522    * @param newseqs
1523    * @throws IOException
1524    */
1525   protected void processGffPragma(String line, Map<String, String> gffProps,
1526           AlignmentI align, List<SequenceI> newseqs) throws IOException
1527   {
1528     line = line.trim();
1529     if ("###".equals(line))
1530     {
1531       // close off any open 'forward references'
1532       return;
1533     }
1534
1535     String[] tokens = line.substring(2).split(" ");
1536     String pragma = tokens[0];
1537     String value = tokens.length == 1 ? null : tokens[1];
1538
1539     if ("gff-version".equalsIgnoreCase(pragma))
1540     {
1541       if (value != null)
1542       {
1543         try
1544         {
1545           // value may be e.g. "3.1.2"
1546           gffVersion = Integer.parseInt(value.split("\\.")[0]);
1547         } catch (NumberFormatException e)
1548         {
1549           // ignore
1550         }
1551       }
1552     }
1553     else if ("sequence-region".equalsIgnoreCase(pragma))
1554     {
1555       // could capture <seqid start end> if wanted here
1556     }
1557     else if ("feature-ontology".equalsIgnoreCase(pragma))
1558     {
1559       // should resolve against the specified feature ontology URI
1560     }
1561     else if ("attribute-ontology".equalsIgnoreCase(pragma))
1562     {
1563       // URI of attribute ontology - not currently used in GFF3
1564     }
1565     else if ("source-ontology".equalsIgnoreCase(pragma))
1566     {
1567       // URI of source ontology - not currently used in GFF3
1568     }
1569     else if ("species-build".equalsIgnoreCase(pragma))
1570     {
1571       // save URI of specific NCBI taxon version of annotations
1572       gffProps.put("species-build", value);
1573     }
1574     else if ("fasta".equalsIgnoreCase(pragma))
1575     {
1576       // process the rest of the file as a fasta file and replace any dummy
1577       // sequence IDs
1578       processAsFasta(align, newseqs);
1579     }
1580     else
1581     {
1582       System.err.println("Ignoring unknown pragma: " + line);
1583     }
1584   }
1585 }