2 // FORESTER -- software libraries and applications
3 // for evolutionary biology research and applications.
5 // Copyright (C) 2014 Christian M. Zmasek
6 // Copyright (C) 2014 Sanford-Burnham Medical Research Institute
9 // This library is free software; you can redistribute it and/or
10 // modify it under the terms of the GNU Lesser General Public
11 // License as published by the Free Software Foundation; either
12 // version 2.1 of the License, or (at your option) any later version.
14 // This library is distributed in the hope that it will be useful,
15 // but WITHOUT ANY WARRANTY; without even the implied warranty of
16 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
17 // Lesser General Public License for more details.
19 // You should have received a copy of the GNU Lesser General Public
20 // License along with this library; if not, write to the Free Software
21 // Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
23 // WWW: https://sites.google.com/site/cmzmasek/home/software/forester
25 package org.forester.msa_compactor;
27 import java.awt.Color;
29 import java.io.IOException;
30 import java.io.Writer;
31 import java.math.RoundingMode;
32 import java.text.DecimalFormat;
33 import java.text.NumberFormat;
34 import java.util.ArrayList;
35 import java.util.Arrays;
36 import java.util.List;
37 import java.util.SortedSet;
38 import java.util.TreeSet;
40 import org.forester.archaeopteryx.Archaeopteryx;
41 import org.forester.archaeopteryx.Configuration;
42 import org.forester.evoinference.distance.NeighborJoiningF;
43 import org.forester.evoinference.distance.PairwiseDistanceCalculator;
44 import org.forester.evoinference.distance.PairwiseDistanceCalculator.PWD_DISTANCE_METHOD;
45 import org.forester.evoinference.matrix.distance.BasicSymmetricalDistanceMatrix;
46 import org.forester.evoinference.tools.BootstrapResampler;
47 import org.forester.io.parsers.nhx.NHXParser.TAXONOMY_EXTRACTION;
48 import org.forester.io.parsers.phyloxml.PhyloXmlDataFormatException;
49 import org.forester.io.parsers.util.ParserUtils;
50 import org.forester.io.writers.SequenceWriter;
51 import org.forester.io.writers.SequenceWriter.SEQ_FORMAT;
52 import org.forester.msa.DeleteableMsa;
53 import org.forester.msa.Mafft;
54 import org.forester.msa.Msa;
55 import org.forester.msa.Msa.MSA_FORMAT;
56 import org.forester.msa.MsaInferrer;
57 import org.forester.msa.MsaMethods;
58 import org.forester.msa.ResampleableMsa;
59 import org.forester.phylogeny.Phylogeny;
60 import org.forester.phylogeny.PhylogenyMethods;
61 import org.forester.phylogeny.PhylogenyMethods.DESCENDANT_SORT_PRIORITY;
62 import org.forester.phylogeny.PhylogenyNode;
63 import org.forester.phylogeny.data.NodeVisualData;
64 import org.forester.phylogeny.data.NodeVisualData.NodeFill;
65 import org.forester.phylogeny.data.NodeVisualData.NodeShape;
66 import org.forester.phylogeny.iterators.PhylogenyNodeIterator;
67 import org.forester.sequence.Sequence;
68 import org.forester.tools.ConfidenceAssessor;
69 import org.forester.util.ForesterUtil;
71 public class MsaCompactor {
73 final private static NumberFormat NF_3 = new DecimalFormat( "#.###" );
74 final private static NumberFormat NF_4 = new DecimalFormat( "#.####" );
75 private double _gap_ratio = -1;
76 private final short _longest_id_length;
78 private String _maffts_opts = "--auto";
79 private int _min_length = -1;
81 private String _infile_name = null;
82 private DeleteableMsa _msa = null;
83 private boolean _norm = true;
84 private File _out_file_base = null;
85 private MSA_FORMAT _output_format = MSA_FORMAT.FASTA;
86 private String _path_to_mafft = null;
88 private boolean _realign = false;
89 private final SortedSet<String> _removed_seq_ids;
90 private final ArrayList<Sequence> _removed_seqs;
91 private File _removed_seqs_out_base = null;
92 private boolean _report_aln_mean_identity = false;
93 private int _step = -1;
94 private int _step_for_diagnostics = -1;
95 private boolean _phylogentic_inference = false;
97 NF_4.setRoundingMode( RoundingMode.HALF_UP );
98 NF_3.setRoundingMode( RoundingMode.HALF_UP );
101 public MsaCompactor( final DeleteableMsa msa ) {
103 _removed_seq_ids = new TreeSet<String>();
104 _longest_id_length = _msa.determineMaxIdLength();
105 _removed_seqs = new ArrayList<Sequence>();
108 public final List<MsaProperties> chart( final int step, final boolean realign, final boolean norm )
109 throws IOException, InterruptedException {
110 final GapContribution stats[] = calcGapContribtionsStats( norm );
111 final List<String> to_remove_ids = new ArrayList<String>();
112 final List<MsaProperties> msa_props = new ArrayList<MsaProperties>();
113 for( final GapContribution gap_gontribution : stats ) {
114 to_remove_ids.add( gap_gontribution.getId() );
119 int x = ForesterUtil.roundToInt( _msa.getNumberOfSequences() / 20.0 );
123 MsaProperties msa_prop = new MsaProperties( _msa, _report_aln_mean_identity );
124 msa_props.add( msa_prop );
125 if ( _phylogentic_inference ) {
126 System.out.println( "calculating phylogentic tree..." );
127 System.out.println();
131 printMsaProperties( "", msa_prop );
132 System.out.println();
134 while ( _msa.getNumberOfSequences() > x ) {
135 final String id = to_remove_ids.get( i );
136 _msa.deleteRow( id, false );
137 if ( realign && isPrintMsaStatsWriteOutfileAndRealign( i ) ) {
140 msa_prop = new MsaProperties( _msa, _report_aln_mean_identity );
141 msa_props.add( msa_prop );
142 printMsaProperties( id, msa_prop );
143 System.out.print( "(realigned)" );
144 System.out.println();
146 else if ( isPrintMsaStats( i ) ) {
148 msa_prop = new MsaProperties( _msa, _report_aln_mean_identity );
149 msa_props.add( msa_prop );
150 printMsaProperties( id, msa_prop );
151 System.out.println();
158 final public void deleteGapColumns( final double max_allowed_gap_ratio ) {
159 _msa.deleteGapColumns( max_allowed_gap_ratio );
162 final public Msa getMsa() {
166 final public SortedSet<String> getRemovedSeqIds() {
167 return _removed_seq_ids;
170 public final void removeSequencesByMinimalLength( final int min_effective_length ) {
171 printMsaProperties( "", new MsaProperties( _msa, _report_aln_mean_identity ) );
172 System.out.println();
173 _msa = DeleteableMsa.createInstance( MsaMethods.removeSequencesByMinimalLength( _msa, min_effective_length ) );
175 printMsaProperties( "", new MsaProperties( _msa, _report_aln_mean_identity ) );
176 System.out.println();
179 public final List<MsaProperties> removeViaGapAverage( final double mean_gapiness ) throws IOException,
180 InterruptedException {
181 final GapContribution stats[] = calcGapContribtionsStats( _norm );
182 final List<String> to_remove_ids = new ArrayList<String>();
183 final List<MsaProperties> msa_props = new ArrayList<MsaProperties>();
184 for( final GapContribution gap_gontribution : stats ) {
185 to_remove_ids.add( gap_gontribution.getId() );
188 MsaProperties msa_prop = new MsaProperties( _msa, _report_aln_mean_identity );
189 msa_props.add( msa_prop );
190 printMsaProperties( "", msa_prop );
191 System.out.println();
193 while ( MsaMethods.calcGapRatio( _msa ) > mean_gapiness ) {
194 final String id = to_remove_ids.get( i );
195 _removed_seq_ids.add( id );
196 final Sequence deleted = _msa.deleteRow( id, true );
197 _removed_seqs.add( deleted );
199 if ( isPrintMsaStatsWriteOutfileAndRealign( i ) || ( MsaMethods.calcGapRatio( _msa ) <= mean_gapiness ) ) {
200 msa_prop = printMsaStatsWriteOutfileAndRealign( _realign, id );
201 msa_props.add( msa_prop );
202 System.out.println();
204 else if ( isPrintMsaStats( i ) ) {
205 msa_prop = new MsaProperties( _msa, _report_aln_mean_identity );
206 msa_props.add( msa_prop );
207 printMsaProperties( id, msa_prop );
208 System.out.println();
212 if ( _removed_seqs_out_base != null ) {
213 final String msg = writeAndAlignRemovedSeqs();
214 System.out.println();
215 System.out.println( msg );
220 public List<MsaProperties> removeViaLength( final int length ) throws IOException, InterruptedException {
221 final GapContribution stats[] = calcGapContribtionsStats( _norm );
222 final List<String> to_remove_ids = new ArrayList<String>();
223 final List<MsaProperties> msa_props = new ArrayList<MsaProperties>();
224 for( final GapContribution gap_gontribution : stats ) {
225 to_remove_ids.add( gap_gontribution.getId() );
228 MsaProperties msa_prop = new MsaProperties( _msa, _report_aln_mean_identity );
229 msa_props.add( msa_prop );
230 printMsaProperties( "", msa_prop );
231 System.out.println();
233 while ( _msa.getLength() > length ) {
234 final String id = to_remove_ids.get( i );
235 _removed_seq_ids.add( id );
236 final Sequence deleted = _msa.deleteRow( id, true );
237 _removed_seqs.add( deleted );
239 if ( isPrintMsaStatsWriteOutfileAndRealign( i ) || ( _msa.getLength() <= length ) ) {
240 msa_prop = printMsaStatsWriteOutfileAndRealign( _realign, id );
241 msa_props.add( msa_prop );
242 System.out.println();
244 else if ( isPrintMsaStats( i ) ) {
245 msa_prop = new MsaProperties( _msa, _report_aln_mean_identity );
246 printMsaProperties( id, msa_prop );
247 msa_props.add( msa_prop );
248 System.out.println();
252 if ( _removed_seqs_out_base != null ) {
253 final String msg = writeAndAlignRemovedSeqs();
254 System.out.println();
255 System.out.println( msg );
260 public final List<MsaProperties> removeWorstOffenders( final int to_remove ) throws IOException,
261 InterruptedException {
262 final GapContribution stats[] = calcGapContribtionsStats( _norm );
263 final List<String> to_remove_ids = new ArrayList<String>();
264 final List<MsaProperties> msa_props = new ArrayList<MsaProperties>();
265 for( int j = 0; j < to_remove; ++j ) {
266 to_remove_ids.add( stats[ j ].getId() );
267 _removed_seq_ids.add( stats[ j ].getId() );
270 MsaProperties msa_prop = new MsaProperties( _msa, _report_aln_mean_identity );
271 msa_props.add( msa_prop );
272 printMsaProperties( "", msa_prop );
273 System.out.println();
274 for( int i = 0; i < to_remove_ids.size(); ++i ) {
275 final String id = to_remove_ids.get( i );
276 _removed_seq_ids.add( id );
277 final Sequence deleted = _msa.deleteRow( id, true );
278 _removed_seqs.add( deleted );
280 if ( isPrintMsaStatsWriteOutfileAndRealign( i ) || ( i == ( to_remove_ids.size() - 1 ) ) ) {
281 msa_prop = printMsaStatsWriteOutfileAndRealign( _realign, id );
282 msa_props.add( msa_prop );
283 System.out.println();
285 else if ( isPrintMsaStats( i ) ) {
286 msa_prop = new MsaProperties( _msa, _report_aln_mean_identity );
287 msa_props.add( msa_prop );
288 printMsaProperties( id, msa_prop );
289 System.out.println();
292 if ( _removed_seqs_out_base != null ) {
293 final String msg = writeAndAlignRemovedSeqs();
294 System.out.println();
295 System.out.println( msg );
300 public final void setGapRatio( final double gap_ratio ) {
301 _gap_ratio = gap_ratio;
304 public final void setMafftOptions( final String maffts_opts ) {
305 _maffts_opts = maffts_opts;
308 public final void setMinLength( final int min_length ) {
309 _min_length = min_length;
312 public final void setNorm( final boolean norm ) {
316 final public void setOutFileBase( final File out_file_base ) {
317 _out_file_base = out_file_base;
320 public final void setOutputFormat( final MSA_FORMAT output_format ) {
321 _output_format = output_format;
324 public void setPathToMafft( final String path_to_mafft ) {
325 _path_to_mafft = path_to_mafft;
328 public final void setRealign( final boolean realign ) {
332 public final void setRemovedSeqsOutBase( final File removed_seqs_out_base ) {
333 _removed_seqs_out_base = removed_seqs_out_base;
336 public final void setReportAlnMeanIdentity( final boolean report_aln_mean_identity ) {
337 _report_aln_mean_identity = report_aln_mean_identity;
340 public final void setStep( final int step ) {
344 public final void setStepForDiagnostics( final int step_for_diagnostics ) {
345 _step_for_diagnostics = step_for_diagnostics;
348 final public String writeAndAlignRemovedSeqs() throws IOException, InterruptedException {
349 final StringBuilder msg = new StringBuilder();
350 final String n = _removed_seqs_out_base + "_" + _removed_seqs.size() + ".fasta";
351 SequenceWriter.writeSeqs( _removed_seqs, new File( n ), SEQ_FORMAT.FASTA, 100 );
352 msg.append( "wrote " + _removed_seqs.size() + " removed sequences to " + "\"" + n + "\"" );
354 final MsaInferrer mafft = Mafft.createInstance( _path_to_mafft );
355 final List<String> opts = new ArrayList<String>();
356 for( final String o : _maffts_opts.split( "\\s" ) ) {
359 final Msa removed_msa = mafft.infer( _removed_seqs, opts );
360 final Double gr = MsaMethods.calcGapRatio( removed_msa );
361 String s = _removed_seqs_out_base + "_" + removed_msa.getNumberOfSequences() + "_"
362 + removed_msa.getLength() + "_" + ForesterUtil.roundToInt( gr * 100 );
363 final String suffix = obtainSuffix();
365 writeMsa( removed_msa, s, _output_format );
366 msg.append( ", and as MSA of length " + removed_msa.getLength() + " to \"" + s + "\"" );
368 return msg.toString();
371 final public String writeMsa( final File outfile ) throws IOException {
372 final Double gr = MsaMethods.calcGapRatio( _msa );
373 final String s = outfile + "_" + _msa.getNumberOfSequences() + "_" + _msa.getLength() + "_"
374 + ForesterUtil.roundToInt( gr * 100 );
375 writeMsa( _msa, s + obtainSuffix(), _output_format );
379 final int calcNonGapResidues( final Sequence seq ) {
381 for( int i = 0; i < seq.getLength(); ++i ) {
382 if ( !seq.isGapAt( i ) ) {
389 private final GapContribution[] calcGapContribtions( final boolean normalize_for_effective_seq_length ) {
390 final double gappiness[] = calcGappiness();
391 final GapContribution stats[] = new GapContribution[ _msa.getNumberOfSequences() ];
392 for( int row = 0; row < _msa.getNumberOfSequences(); ++row ) {
393 stats[ row ] = new GapContribution( _msa.getIdentifier( row ) );
394 for( int col = 0; col < _msa.getLength(); ++col ) {
395 if ( !_msa.isGapAt( row, col ) ) {
396 stats[ row ].addToValue( gappiness[ col ] );
399 if ( normalize_for_effective_seq_length ) {
400 stats[ row ].divideValue( calcNonGapResidues( _msa.getSequence( row ) ) );
403 stats[ row ].divideValue( _msa.getLength() );
409 final private GapContribution[] calcGapContribtionsStats( final boolean norm ) {
410 final GapContribution stats[] = calcGapContribtions( norm );
411 Arrays.sort( stats );
415 private final double[] calcGappiness() {
416 final int l = _msa.getLength();
417 final double gappiness[] = new double[ l ];
418 final int seqs = _msa.getNumberOfSequences();
419 for( int i = 0; i < l; ++i ) {
420 gappiness[ i ] = ( double ) MsaMethods.calcGapSumPerColumn( _msa, i ) / seqs;
425 private final Phylogeny inferNJphylogeny( final PWD_DISTANCE_METHOD pwd_distance_method,
427 final boolean write_matrix,
428 final String matrix_name ) {
429 BasicSymmetricalDistanceMatrix m = null;
430 switch ( pwd_distance_method ) {
431 case KIMURA_DISTANCE:
432 m = PairwiseDistanceCalculator.calcKimuraDistances( msa );
434 case POISSON_DISTANCE:
435 m = PairwiseDistanceCalculator.calcPoissonDistances( msa );
437 case FRACTIONAL_DISSIMILARITY:
438 m = PairwiseDistanceCalculator.calcFractionalDissimilarities( msa );
441 throw new IllegalArgumentException( "invalid pwd method" );
443 if ( write_matrix ) {
445 m.write( ForesterUtil.createBufferedWriter( matrix_name ) );
447 catch ( final IOException e ) {
451 final NeighborJoiningF nj = NeighborJoiningF.createInstance( false, 5 );
452 final Phylogeny phy = nj.execute( m );
456 private final boolean isPrintMsaStats( final int i ) {
457 return ( ( ( _step == 1 ) && ( _step_for_diagnostics == 1 ) ) || ( ( _step_for_diagnostics > 0 ) && ( ( ( i + 1 ) % _step_for_diagnostics ) == 0 ) ) );
460 private final boolean isPrintMsaStatsWriteOutfileAndRealign( final int i ) {
461 return ( ( ( _step == 1 ) && ( _step_for_diagnostics == 1 ) ) || ( ( _step > 0 ) && ( ( ( i + 1 ) % _step ) == 0 ) ) );
464 private final StringBuilder msaPropertiesAsSB( final MsaProperties msa_properties ) {
465 final StringBuilder sb = new StringBuilder();
466 sb.append( msa_properties.getNumberOfSequences() );
468 sb.append( msa_properties.getLength() );
470 sb.append( NF_4.format( msa_properties.getGapRatio() ) );
471 if ( _report_aln_mean_identity ) {
473 sb.append( NF_4.format( msa_properties.getAverageIdentityRatio() ) );
478 private String obtainSuffix() {
479 if ( _output_format == MSA_FORMAT.FASTA ) {
482 else if ( _output_format == MSA_FORMAT.PHYLIP ) {
488 private final Phylogeny pi( final String matrix, final int boostrap ) {
489 final Phylogeny master_phy = inferNJphylogeny( PWD_DISTANCE_METHOD.KIMURA_DISTANCE, _msa, true, matrix );
492 final ResampleableMsa resampleable_msa = new ResampleableMsa( _msa );
493 final int[][] resampled_column_positions = BootstrapResampler.createResampledColumnPositions( _msa.getLength(),
496 final Phylogeny[] eval_phys = new Phylogeny[ n ];
497 for( int i = 0; i < n; ++i ) {
498 resampleable_msa.resample( resampled_column_positions[ i ] );
499 eval_phys[ i ] = inferNJphylogeny( PWD_DISTANCE_METHOD.KIMURA_DISTANCE, resampleable_msa, false, null );
501 ConfidenceAssessor.evaluate( "bootstrap", eval_phys, master_phy, true, 1 );
502 PhylogenyMethods.extractFastaInformation( master_phy );
506 private final Phylogeny pi( final List<String> to_remove_ids ) {
507 final Phylogeny phy = inferNJphylogeny( PWD_DISTANCE_METHOD.KIMURA_DISTANCE, _msa, false, "" );
508 for( int i = 0; i < to_remove_ids.size(); ++i ) {
509 final String id = to_remove_ids.get( i );
510 final PhylogenyNode n = phy.getNode( id );
511 n.setName( n.getName() + " [" + ( i + 1 ) + "]" );
512 final NodeVisualData vis = new NodeVisualData();
513 vis.setFillType( NodeFill.SOLID );
514 vis.setShape( NodeShape.RECTANGLE );
516 vis.setNodeColor( new Color( i > 255 ? 0 : 255 - i, 0, 0 ) );
517 n.getNodeData().setNodeVisualData( vis );
519 PhylogenyMethods.midpointRoot( phy );
520 PhylogenyMethods.orderAppearance( phy.getRoot(), true, true, DESCENDANT_SORT_PRIORITY.NODE_NAME );
521 final boolean x = PhylogenyMethods.extractFastaInformation( phy );
523 final PhylogenyNodeIterator it = phy.iteratorExternalForward();
524 while ( it.hasNext() ) {
525 final PhylogenyNode n = it.next();
526 final String name = n.getName().trim();
527 if ( !ForesterUtil.isEmpty( name ) ) {
529 ParserUtils.extractTaxonomyDataFromNodeName( n, TAXONOMY_EXTRACTION.AGGRESSIVE );
531 catch ( final PhyloXmlDataFormatException e ) {
537 final Configuration config = new Configuration();
538 config.setDisplayAsPhylogram( true );
539 config.setUseStyle( true );
540 config.setDisplayTaxonomyCode( false );
541 config.setDisplayTaxonomyCommonNames( false );
542 config.setDisplayTaxonomyScientificNames( false );
543 config.setDisplaySequenceNames( false );
544 config.setDisplaySequenceSymbols( false );
545 config.setDisplayGeneNames( false );
546 config.setShowScale( true );
547 config.setAddTaxonomyImagesCB( false );
548 config.setBaseFontSize( 9 );
549 config.setBaseFontFamilyName( "Arial" );
550 Archaeopteryx.createApplication( phy, config, _infile_name );
554 private final void printMsaProperties( final String id, final MsaProperties msa_properties ) {
555 if ( ( _step == 1 ) || ( _step_for_diagnostics == 1 ) ) {
556 System.out.print( ForesterUtil.pad( id, _longest_id_length, ' ', false ) );
557 System.out.print( "\t" );
559 System.out.print( msaPropertiesAsSB( msa_properties ) );
560 System.out.print( "\t" );
563 final private MsaProperties printMsaStatsWriteOutfileAndRealign( final boolean realign, final String id )
564 throws IOException, InterruptedException {
568 final MsaProperties msa_prop = new MsaProperties( _msa, _report_aln_mean_identity );
569 printMsaProperties( id, msa_prop );
570 final String s = writeOutfile();
571 System.out.print( "-> " + s + ( realign ? "\t(realigned)" : "" ) );
575 private final void printTableHeader() {
576 if ( ( _step == 1 ) || ( _step_for_diagnostics == 1 ) ) {
577 System.out.print( ForesterUtil.pad( "Id", _longest_id_length, ' ', false ) );
578 System.out.print( "\t" );
580 System.out.print( "Seqs" );
581 System.out.print( "\t" );
582 System.out.print( "Length" );
583 System.out.print( "\t" );
584 System.out.print( "Gaps" );
585 System.out.print( "\t" );
586 if ( _report_aln_mean_identity ) {
587 System.out.print( "MSA qual" );
588 System.out.print( "\t" );
590 System.out.println();
593 final private void realignWithMafft() throws IOException, InterruptedException {
594 final MsaInferrer mafft = Mafft.createInstance( _path_to_mafft );
595 final List<String> opts = new ArrayList<String>();
596 for( final String o : _maffts_opts.split( "\\s" ) ) {
599 _msa = DeleteableMsa.createInstance( mafft.infer( _msa.asSequenceList(), opts ) );
602 final private void removeGapColumns() {
603 _msa.deleteGapOnlyColumns();
606 private final String writeOutfile() throws IOException {
607 final String s = writeMsa( _out_file_base );
611 // Returns null if not path found.
612 final public static String guessPathToMafft() {
614 if ( ForesterUtil.OS_NAME.toLowerCase().indexOf( "win" ) >= 0 ) {
615 path = "C:\\Program Files\\mafft-win\\mafft.bat";
616 if ( MsaInferrer.isInstalled( path ) ) {
620 path = "/home/czmasek/SOFTWARE/MSA/MAFFT/mafft-7.130-without-extensions/scripts/mafft";
621 if ( MsaInferrer.isInstalled( path ) ) {
624 path = "/usr/local/bin/mafft";
625 if ( MsaInferrer.isInstalled( path ) ) {
628 path = "/usr/bin/mafft";
629 if ( MsaInferrer.isInstalled( path ) ) {
633 if ( MsaInferrer.isInstalled( path ) ) {
637 if ( MsaInferrer.isInstalled( path ) ) {
643 final private static void writeMsa( final Msa msa, final String outfile, final MSA_FORMAT format )
645 final Writer w = ForesterUtil.createBufferedWriter( outfile );
646 msa.write( w, format );
650 public void setPeformPhylogenticInference( final boolean phylogentic_inference ) {
651 _phylogentic_inference = phylogentic_inference;
654 public void setInfileName( final String infile_name ) {
655 _infile_name = infile_name;