001/* 002 * BioJava development code 003 * 004 * This code may be freely distributed and modified under the 005 * terms of the GNU Lesser General Public Licence. This should 006 * be distributed with the code. If you do not have a copy, 007 * see: 008 * 009 * http://www.gnu.org/copyleft/lesser.html 010 * 011 * Copyright for this code is held jointly by the individual 012 * authors. These should be listed in @author doc comments. 013 * 014 * For more information on the BioJava project and its aims, 015 * or to join the biojava-l mailing list, visit the home page 016 * at: 017 * 018 * http://www.biojava.org/ 019 * 020 * Created on June 7, 2010 021 * Author: Mark Chapman 022 */ 023 024package org.biojava.nbio.alignment; 025 026import org.biojava.nbio.core.alignment.template.ProfilePair; 027import org.biojava.nbio.core.alignment.template.SequencePair; 028import org.biojava.nbio.core.alignment.matrices.SubstitutionMatrixHelper; 029import org.biojava.nbio.core.alignment.template.Profile; 030import org.biojava.nbio.core.alignment.template.SubstitutionMatrix; 031import org.biojava.nbio.alignment.template.*; 032import org.biojava.nbio.core.sequence.compound.AmbiguityDNACompoundSet; 033import org.biojava.nbio.core.sequence.compound.AminoAcidCompoundSet; 034import org.biojava.nbio.core.sequence.compound.DNACompoundSet; 035import org.biojava.nbio.core.sequence.template.Compound; 036import org.biojava.nbio.core.sequence.template.CompoundSet; 037import org.biojava.nbio.core.sequence.template.Sequence; 038import org.biojava.nbio.core.util.ConcurrencyTools; 039import org.slf4j.Logger; 040import org.slf4j.LoggerFactory; 041 042import java.util.ArrayList; 043import java.util.List; 044import java.util.concurrent.ExecutionException; 045import java.util.concurrent.Future; 046 047/** 048 * Static utility to easily run alignment routines. To exit cleanly after running any parallel method that mentions 049 * use of the {@link ConcurrencyTools} utility, {@link ConcurrencyTools#shutdown()} or 050 * {@link ConcurrencyTools#shutdownAndAwaitTermination()} must be called. 051 * 052 * @author Mark Chapman 053 */ 054public class Alignments { 055 056 private final static Logger logger = LoggerFactory.getLogger(Alignments.class); 057 058 /** 059 * List of implemented sequence pair in a profile scoring routines. 060 */ 061 public static enum PairInProfileScorerType { 062 IDENTITIES, // similar to MUSCLE 063 SIMILARITIES 064 } 065 066 /** 067 * List of implemented pairwise sequence alignment routines. 068 */ 069 public static enum PairwiseSequenceAlignerType { 070 GLOBAL, // Needleman-Wunsch/Gotoh 071 GLOBAL_LINEAR_SPACE, // Guan-Uberbacher 072 LOCAL, // Smith-Waterman/Gotoh 073 LOCAL_LINEAR_SPACE // Smith-Waterman/Gotoh with smart traceback at each maximum 074 } 075 076 /** 077 * List of implemented pairwise sequence scoring routines. 078 */ 079 public static enum PairwiseSequenceScorerType { 080 GLOBAL, 081 GLOBAL_IDENTITIES, // similar to CLUSTALW and CLUSTALW2 082 GLOBAL_SIMILARITIES, 083 LOCAL, 084 LOCAL_IDENTITIES, 085 LOCAL_SIMILARITIES, 086 KMERS, // similar to CLUSTAL and MUSCLE 087 WU_MANBER // similar to KALIGN 088 } 089 090 /** 091 * List of implemented profile-profile alignment routines. 092 */ 093 public static enum ProfileProfileAlignerType { 094 GLOBAL, // similar to MUSCLE and KALIGN 095 GLOBAL_LINEAR_SPACE, // similar to CLUSTALW and CLUSTALW2 096 GLOBAL_CONSENSUS, // similar to CLUSTAL 097 LOCAL, 098 LOCAL_LINEAR_SPACE, 099 LOCAL_CONSENSUS 100 } 101 102 /** 103 * List of implemented profile refinement routines. 104 */ 105 public static enum RefinerType { 106 PARTITION_SINGLE, // similar to CLUSTALW2 107 PARTITION_SINGLE_ALL, // similar to CLUSTALW2 108 PARTITION_TREE, // similar to MUSCLE 109 PARTITION_TREE_ALL, 110 RESCORE_IDENTITIES, // similar to MUSCLE 111 RESCORE_SIMILARITIES 112 } 113 114 // prevents instantiation 115 private Alignments() { } 116 117 // public factory methods 118 119 /** 120 * Factory method which computes a sequence alignment for all {@link Sequence} pairs in the given {@link List}. 121 * This method runs the alignments in parallel by submitting all of the alignments to the shared thread pool of the 122 * {@link ConcurrencyTools} utility. 123 * 124 * @param <S> each {@link Sequence} of an alignment pair is of type S 125 * @param <C> each element of an {@link AlignedSequence} is a {@link Compound} of type C 126 * @param sequences the {@link List} of {@link Sequence}s to align 127 * @param type chosen type from list of pairwise sequence alignment routines 128 * @param gapPenalty the gap penalties used during alignment 129 * @param subMatrix the set of substitution scores used during alignment 130 * @return list of sequence alignment pairs 131 */ 132 public static <S extends Sequence<C>, C extends Compound> List<SequencePair<S, C>> getAllPairsAlignments( 133 List<S> sequences, PairwiseSequenceAlignerType type, GapPenalty gapPenalty, 134 SubstitutionMatrix<C> subMatrix) { 135 return runPairwiseAligners(getAllPairsAligners(sequences, type, gapPenalty, subMatrix)); 136 } 137 138 /** 139 * Factory method which computes a multiple sequence alignment for the given {@link List} of {@link Sequence}s. 140 * 141 * @param <S> each {@link Sequence} of the {@link List} is of type S 142 * @param <C> each element of a {@link Sequence} is a {@link Compound} of type C 143 * @param sequences the {@link List} of {@link Sequence}s to align 144 * @param settings optional settings that adjust the alignment 145 * @return multiple sequence alignment {@link Profile} 146 */ 147 public static <S extends Sequence<C>, C extends Compound> Profile<S, C> getMultipleSequenceAlignment( 148 List<S> sequences, Object... settings) { // TODO convert other factories to this parameter style? 149 CompoundSet<C> cs = sequences.get(0).getCompoundSet(); 150 PairwiseSequenceScorerType ps = PairwiseSequenceScorerType.GLOBAL_IDENTITIES; 151 GapPenalty gapPenalty = new SimpleGapPenalty(); 152 SubstitutionMatrix<C> subMatrix = null; 153 if (cs == AminoAcidCompoundSet.getAminoAcidCompoundSet()) { 154 @SuppressWarnings("unchecked") // compound types must be equal since compound sets are equal 155 SubstitutionMatrix<C> temp = (SubstitutionMatrix<C>) SubstitutionMatrixHelper.getBlosum62(); 156 subMatrix = temp; 157 } else if (cs == DNACompoundSet.getDNACompoundSet()) { 158 @SuppressWarnings("unchecked") // compound types must be equal since compound sets are equal 159 SubstitutionMatrix<C> temp = (SubstitutionMatrix<C>) SubstitutionMatrixHelper.getNuc4_4(); 160 subMatrix = temp; 161 162 } else if (cs == AmbiguityDNACompoundSet.getDNACompoundSet()) { 163 @SuppressWarnings("unchecked") // compound types must be equal since compound sets are equal 164 SubstitutionMatrix<C> temp = (SubstitutionMatrix<C>) SubstitutionMatrixHelper.getNuc4_4(); 165 subMatrix = temp; 166 167 } 168 ProfileProfileAlignerType pa = ProfileProfileAlignerType.GLOBAL; 169 for (Object o : settings) { 170 if (o instanceof PairwiseSequenceScorerType) { 171 ps = (PairwiseSequenceScorerType) o; 172 } else if (o instanceof GapPenalty) { 173 gapPenalty = (GapPenalty) o; 174 } else if (o instanceof SubstitutionMatrix<?>) { 175 if (cs != ((SubstitutionMatrix<?>) o).getCompoundSet()) { 176 throw new IllegalArgumentException( 177 "Compound sets of the sequences and substitution matrix must match."); 178 } 179 @SuppressWarnings("unchecked") // compound types must be equal since compound sets are equal 180 SubstitutionMatrix<C> temp = (SubstitutionMatrix<C>) o; 181 subMatrix = temp; 182 } else if (o instanceof ProfileProfileAlignerType) { 183 pa = (ProfileProfileAlignerType) o; 184 } 185 } 186 187 // stage 1: pairwise similarity calculation 188 List<PairwiseSequenceScorer<S, C>> scorers = getAllPairsScorers(sequences, ps, gapPenalty, subMatrix); 189 runPairwiseScorers(scorers); 190 191 // stage 2: hierarchical clustering into a guide tree 192 GuideTree<S, C> tree = new GuideTree<S, C>(sequences, scorers); 193 scorers = null; 194 195 // stage 3: progressive alignment 196 Profile<S, C> msa = getProgressiveAlignment(tree, pa, gapPenalty, subMatrix); 197 198 // TODO stage 4: refinement 199 return msa; 200 } 201 202 /** 203 * Factory method which computes a sequence alignment for the given {@link Sequence} pair. 204 * 205 * @param <S> each {@link Sequence} of the pair is of type S 206 * @param <C> each element of an {@link AlignedSequence} is a {@link Compound} of type C 207 * @param query the first {@link Sequence}s to align 208 * @param target the second {@link Sequence}s to align 209 * @param type chosen type from list of pairwise sequence alignment routines 210 * @param gapPenalty the gap penalties used during alignment 211 * @param subMatrix the set of substitution scores used during alignment 212 * @return sequence alignment pair 213 */ 214 public static <S extends Sequence<C>, C extends Compound> SequencePair<S, C> getPairwiseAlignment( 215 S query, S target, PairwiseSequenceAlignerType type, GapPenalty gapPenalty, 216 SubstitutionMatrix<C> subMatrix) { 217 return getPairwiseAligner(query, target, type, gapPenalty, subMatrix).getPair(); 218 } 219 220 // default access (package private) factory methods 221 222 /** 223 * Factory method which sets up a sequence alignment for all {@link Sequence} pairs in the given {@link List}. 224 * 225 * @param <S> each {@link Sequence} of an alignment pair is of type S 226 * @param <C> each element of an {@link AlignedSequence} is a {@link Compound} of type C 227 * @param sequences the {@link List} of {@link Sequence}s to align 228 * @param type chosen type from list of pairwise sequence alignment routines 229 * @param gapPenalty the gap penalties used during alignment 230 * @param subMatrix the set of substitution scores used during alignment 231 * @return list of pairwise sequence aligners 232 */ 233 static <S extends Sequence<C>, C extends Compound> List<PairwiseSequenceAligner<S, C>> getAllPairsAligners( 234 List<S> sequences, PairwiseSequenceAlignerType type, GapPenalty gapPenalty, 235 SubstitutionMatrix<C> subMatrix) { 236 List<PairwiseSequenceAligner<S, C>> allPairs = new ArrayList<PairwiseSequenceAligner<S, C>>(); 237 for (int i = 0; i < sequences.size(); i++) { 238 for (int j = i+1; j < sequences.size(); j++) { 239 allPairs.add(getPairwiseAligner(sequences.get(i), sequences.get(j), type, gapPenalty, subMatrix)); 240 } 241 } 242 return allPairs; 243 } 244 245 /** 246 * Factory method which sets up a sequence pair scorer for all {@link Sequence} pairs in the given {@link List}. 247 * 248 * @param <S> each {@link Sequence} of a pair is of type S 249 * @param <C> each element of a {@link Sequence} is a {@link Compound} of type C 250 * @param sequences the {@link List} of {@link Sequence}s to align 251 * @param type chosen type from list of pairwise sequence scoring routines 252 * @param gapPenalty the gap penalties used during alignment 253 * @param subMatrix the set of substitution scores used during alignment 254 * @return list of sequence pair scorers 255 */ 256 public static <S extends Sequence<C>, C extends Compound> List<PairwiseSequenceScorer<S, C>> getAllPairsScorers( 257 List<S> sequences, PairwiseSequenceScorerType type, GapPenalty gapPenalty, 258 SubstitutionMatrix<C> subMatrix) { 259 List<PairwiseSequenceScorer<S, C>> allPairs = new ArrayList<PairwiseSequenceScorer<S, C>>(); 260 for (int i = 0; i < sequences.size(); i++) { 261 for (int j = i+1; j < sequences.size(); j++) { 262 allPairs.add(getPairwiseScorer(sequences.get(i), sequences.get(j), type, gapPenalty, subMatrix)); 263 } 264 } 265 return allPairs; 266 } 267 268 /** 269 * Factory method which computes a sequence pair score for all {@link Sequence} pairs in the given {@link List}. 270 * This method runs the scorings in parallel by submitting all of the scorings to the shared thread pool of the 271 * {@link ConcurrencyTools} utility. 272 * 273 * @param <S> each {@link Sequence} of a pair is of type S 274 * @param <C> each element of a {@link Sequence} is a {@link Compound} of type C 275 * @param sequences the {@link List} of {@link Sequence}s to align 276 * @param type chosen type from list of pairwise sequence scoring routines 277 * @param gapPenalty the gap penalties used during alignment 278 * @param subMatrix the set of substitution scores used during alignment 279 * @return list of sequence pair scores 280 */ 281 public static <S extends Sequence<C>, C extends Compound> double[] getAllPairsScores( List<S> sequences, 282 PairwiseSequenceScorerType type, GapPenalty gapPenalty, SubstitutionMatrix<C> subMatrix) { 283 return runPairwiseScorers(getAllPairsScorers(sequences, type, gapPenalty, subMatrix)); 284 } 285 286 /** 287 * Factory method which retrieves calculated elements from a list of tasks on the concurrent execution queue. 288 * 289 * @param <E> each task calculates a value of type E 290 * @param futures list of tasks 291 * @return calculated elements 292 */ 293 static <E> List<E> getListFromFutures(List<Future<E>> futures) { 294 List<E> list = new ArrayList<E>(); 295 for (Future<E> f : futures) { 296 // TODO when added to ConcurrencyTools, log completions and exceptions instead of printing stack traces 297 try { 298 list.add(f.get()); 299 } catch (InterruptedException e) { 300 logger.error("Interrupted Exception: ", e); 301 } catch (ExecutionException e) { 302 logger.error("Execution Exception: ", e); 303 } 304 } 305 return list; 306 } 307 308 /** 309 * Factory method which constructs a pairwise sequence aligner. 310 * 311 * @param <S> each {@link Sequence} of an alignment pair is of type S 312 * @param <C> each element of an {@link AlignedSequence} is a {@link Compound} of type C 313 * @param query the first {@link Sequence} to align 314 * @param target the second {@link Sequence} to align 315 * @param type chosen type from list of pairwise sequence alignment routines 316 * @param gapPenalty the gap penalties used during alignment 317 * @param subMatrix the set of substitution scores used during alignment 318 * @return pairwise sequence aligner 319 */ 320 public static <S extends Sequence<C>, C extends Compound> PairwiseSequenceAligner<S, C> getPairwiseAligner( 321 S query, S target, PairwiseSequenceAlignerType type, GapPenalty gapPenalty, 322 SubstitutionMatrix<C> subMatrix) { 323 if (!query.getCompoundSet().equals(target.getCompoundSet())) { 324 throw new IllegalArgumentException("Sequence compound sets must be the same"); 325 } 326 switch (type) { 327 default: 328 case GLOBAL: 329 return new NeedlemanWunsch<S, C>(query, target, gapPenalty, subMatrix); 330 case LOCAL: 331 return new SmithWaterman<S, C>(query, target, gapPenalty, subMatrix); 332 case GLOBAL_LINEAR_SPACE: 333 case LOCAL_LINEAR_SPACE: 334 // TODO other alignment options (Myers-Miller, Thompson) 335 throw new UnsupportedOperationException(Alignments.class.getSimpleName() + " does not yet support " + 336 type + " alignment"); 337 } 338 } 339 340 /** 341 * Factory method which computes a similarity score for the given {@link Sequence} pair. 342 * 343 * @param <S> each {@link Sequence} of the pair is of type S 344 * @param <C> each element of a {@link Sequence} is a {@link Compound} of type C 345 * @param query the first {@link Sequence} to score 346 * @param target the second {@link Sequence} to score 347 * @param type chosen type from list of pairwise sequence scoring routines 348 * @param gapPenalty the gap penalties used during alignment 349 * @param subMatrix the set of substitution scores used during alignment 350 * @return sequence pair score 351 */ 352 static <S extends Sequence<C>, C extends Compound> double getPairwiseScore(S query, S target, 353 PairwiseSequenceScorerType type, GapPenalty gapPenalty, SubstitutionMatrix<C> subMatrix) { 354 return getPairwiseScorer(query, target, type, gapPenalty, subMatrix).getScore(); 355 } 356 357 /** 358 * Factory method which constructs a pairwise sequence scorer. 359 * 360 * @param <S> each {@link Sequence} of a pair is of type S 361 * @param <C> each element of a {@link Sequence} is a {@link Compound} of type C 362 * @param query the first {@link Sequence} to score 363 * @param target the second {@link Sequence} to score 364 * @param type chosen type from list of pairwise sequence scoring routines 365 * @param gapPenalty the gap penalties used during alignment 366 * @param subMatrix the set of substitution scores used during alignment 367 * @return sequence pair scorer 368 */ 369 static <S extends Sequence<C>, C extends Compound> PairwiseSequenceScorer<S, C> getPairwiseScorer( 370 S query, S target, PairwiseSequenceScorerType type, GapPenalty gapPenalty, 371 SubstitutionMatrix<C> subMatrix) { 372 switch (type) { 373 default: 374 case GLOBAL: 375 return getPairwiseAligner(query, target, PairwiseSequenceAlignerType.GLOBAL, gapPenalty, subMatrix); 376 case GLOBAL_IDENTITIES: 377 return new FractionalIdentityScorer<S, C>(getPairwiseAligner(query, target, 378 PairwiseSequenceAlignerType.GLOBAL, gapPenalty, subMatrix)); 379 case GLOBAL_SIMILARITIES: 380 return new FractionalSimilarityScorer<S, C>(getPairwiseAligner(query, target, 381 PairwiseSequenceAlignerType.GLOBAL, gapPenalty, subMatrix)); 382 case LOCAL: 383 return getPairwiseAligner(query, target, PairwiseSequenceAlignerType.LOCAL, gapPenalty, subMatrix); 384 case LOCAL_IDENTITIES: 385 return new FractionalIdentityScorer<S, C>(getPairwiseAligner(query, target, 386 PairwiseSequenceAlignerType.LOCAL, gapPenalty, subMatrix)); 387 case LOCAL_SIMILARITIES: 388 return new FractionalSimilarityScorer<S, C>(getPairwiseAligner(query, target, 389 PairwiseSequenceAlignerType.LOCAL, gapPenalty, subMatrix)); 390 case KMERS: 391 case WU_MANBER: 392 // TODO other scoring options 393 throw new UnsupportedOperationException(Alignments.class.getSimpleName() + " does not yet support " + 394 type + " scoring"); 395 } 396 } 397 398 /** 399 * Factory method which constructs a profile-profile aligner. 400 * 401 * @param <S> each {@link Sequence} of an alignment profile is of type S 402 * @param <C> each element of an {@link AlignedSequence} is a {@link Compound} of type C 403 * @param profile1 the first {@link Profile} to align 404 * @param profile2 the second {@link Profile} to align 405 * @param type chosen type from list of profile-profile alignment routines 406 * @param gapPenalty the gap penalties used during alignment 407 * @param subMatrix the set of substitution scores used during alignment 408 * @return profile-profile aligner 409 */ 410 static <S extends Sequence<C>, C extends Compound> ProfileProfileAligner<S, C> getProfileProfileAligner( 411 Profile<S, C> profile1, Profile<S, C> profile2, ProfileProfileAlignerType type, GapPenalty gapPenalty, 412 SubstitutionMatrix<C> subMatrix) { 413 switch (type) { 414 default: 415 case GLOBAL: 416 return new SimpleProfileProfileAligner<S, C>(profile1, profile2, gapPenalty, subMatrix); 417 case GLOBAL_LINEAR_SPACE: 418 case GLOBAL_CONSENSUS: 419 case LOCAL: 420 case LOCAL_LINEAR_SPACE: 421 case LOCAL_CONSENSUS: 422 // TODO other alignment options (Myers-Miller, consensus, local) 423 throw new UnsupportedOperationException(Alignments.class.getSimpleName() + " does not yet support " + 424 type + " alignment"); 425 } 426 } 427 428 /** 429 * Factory method which constructs a profile-profile aligner. 430 * 431 * @param <S> each {@link Sequence} of an alignment profile is of type S 432 * @param <C> each element of an {@link AlignedSequence} is a {@link Compound} of type C 433 * @param profile1 the first {@link Profile} to align 434 * @param profile2 the second {@link Profile} to align 435 * @param type chosen type from list of profile-profile alignment routines 436 * @param gapPenalty the gap penalties used during alignment 437 * @param subMatrix the set of substitution scores used during alignment 438 * @return profile-profile aligner 439 */ 440 static <S extends Sequence<C>, C extends Compound> ProfileProfileAligner<S, C> getProfileProfileAligner( 441 Future<ProfilePair<S, C>> profile1, Future<ProfilePair<S, C>> profile2, ProfileProfileAlignerType type, 442 GapPenalty gapPenalty, SubstitutionMatrix<C> subMatrix) { 443 switch (type) { 444 default: 445 case GLOBAL: 446 return new SimpleProfileProfileAligner<S, C>(profile1, profile2, gapPenalty, subMatrix); 447 case GLOBAL_LINEAR_SPACE: 448 case GLOBAL_CONSENSUS: 449 case LOCAL: 450 case LOCAL_LINEAR_SPACE: 451 case LOCAL_CONSENSUS: 452 // TODO other alignment options (Myers-Miller, consensus, local) 453 throw new UnsupportedOperationException(Alignments.class.getSimpleName() + " does not yet support " + 454 type + " alignment"); 455 } 456 } 457 458 /** 459 * Factory method which constructs a profile-profile aligner. 460 * 461 * @param <S> each {@link Sequence} of an alignment profile is of type S 462 * @param <C> each element of an {@link AlignedSequence} is a {@link Compound} of type C 463 * @param profile1 the first {@link Profile} to align 464 * @param profile2 the second {@link Profile} to align 465 * @param type chosen type from list of profile-profile alignment routines 466 * @param gapPenalty the gap penalties used during alignment 467 * @param subMatrix the set of substitution scores used during alignment 468 * @return profile-profile aligner 469 */ 470 static <S extends Sequence<C>, C extends Compound> ProfileProfileAligner<S, C> getProfileProfileAligner( 471 Profile<S, C> profile1, Future<ProfilePair<S, C>> profile2, ProfileProfileAlignerType type, 472 GapPenalty gapPenalty, SubstitutionMatrix<C> subMatrix) { 473 switch (type) { 474 default: 475 case GLOBAL: 476 return new SimpleProfileProfileAligner<S, C>(profile1, profile2, gapPenalty, subMatrix); 477 case GLOBAL_LINEAR_SPACE: 478 case GLOBAL_CONSENSUS: 479 case LOCAL: 480 case LOCAL_LINEAR_SPACE: 481 case LOCAL_CONSENSUS: 482 // TODO other alignment options (Myers-Miller, consensus, local) 483 throw new UnsupportedOperationException(Alignments.class.getSimpleName() + " does not yet support " + 484 type + " alignment"); 485 } 486 } 487 488 /** 489 * Factory method which constructs a profile-profile aligner. 490 * 491 * @param <S> each {@link Sequence} of an alignment profile is of type S 492 * @param <C> each element of an {@link AlignedSequence} is a {@link Compound} of type C 493 * @param profile1 the first {@link Profile} to align 494 * @param profile2 the second {@link Profile} to align 495 * @param type chosen type from list of profile-profile alignment routines 496 * @param gapPenalty the gap penalties used during alignment 497 * @param subMatrix the set of substitution scores used during alignment 498 * @return profile-profile aligner 499 */ 500 static <S extends Sequence<C>, C extends Compound> ProfileProfileAligner<S, C> getProfileProfileAligner( 501 Future<ProfilePair<S, C>> profile1, Profile<S, C> profile2, ProfileProfileAlignerType type, 502 GapPenalty gapPenalty, SubstitutionMatrix<C> subMatrix) { 503 switch (type) { 504 default: 505 case GLOBAL: 506 return new SimpleProfileProfileAligner<S, C>(profile1, profile2, gapPenalty, subMatrix); 507 case GLOBAL_LINEAR_SPACE: 508 case GLOBAL_CONSENSUS: 509 case LOCAL: 510 case LOCAL_LINEAR_SPACE: 511 case LOCAL_CONSENSUS: 512 // TODO other alignment options (Myers-Miller, consensus, local) 513 throw new UnsupportedOperationException(Alignments.class.getSimpleName() + " does not yet support " + 514 type + " alignment"); 515 } 516 } 517 518 /** 519 * Factory method which computes a profile alignment for the given {@link Profile} pair. 520 * 521 * @param <S> each {@link Sequence} of the {@link Profile} pair is of type S 522 * @param <C> each element of an {@link AlignedSequence} is a {@link Compound} of type C 523 * @param profile1 the first {@link Profile} to align 524 * @param profile2 the second {@link Profile} to align 525 * @param type chosen type from list of profile-profile alignment routines 526 * @param gapPenalty the gap penalties used during alignment 527 * @param subMatrix the set of substitution scores used during alignment 528 * @return alignment profile 529 */ 530 static <S extends Sequence<C>, C extends Compound> ProfilePair<S, C> getProfileProfileAlignment( 531 Profile<S, C> profile1, Profile<S, C> profile2, ProfileProfileAlignerType type, GapPenalty gapPenalty, 532 SubstitutionMatrix<C> subMatrix) { 533 return getProfileProfileAligner(profile1, profile2, type, gapPenalty, subMatrix).getPair(); 534 } 535 536 /** 537 * Factory method to run the profile-profile alignments of a progressive multiple sequence alignment concurrently. 538 * This method runs the alignments in parallel by submitting all of the alignment tasks to the shared thread pool 539 * of the {@link ConcurrencyTools} utility. 540 * 541 * @param <S> each {@link Sequence} of the {@link Profile} pair is of type S 542 * @param <C> each element of an {@link AlignedSequence} is a {@link Compound} of type C 543 * @param tree guide tree to follow aligning profiles from leaves to root 544 * @param type chosen type from list of profile-profile alignment routines 545 * @param gapPenalty the gap penalties used during alignment 546 * @param subMatrix the set of substitution scores used during alignment 547 * @return multiple sequence alignment 548 */ 549 public static <S extends Sequence<C>, C extends Compound> Profile<S, C> getProgressiveAlignment(GuideTree<S, C> tree, 550 ProfileProfileAlignerType type, GapPenalty gapPenalty, SubstitutionMatrix<C> subMatrix) { 551 552 // find inner nodes in post-order traversal of tree (each leaf node has a single sequence profile) 553 List<GuideTreeNode<S, C>> innerNodes = new ArrayList<GuideTreeNode<S, C>>(); 554 for (GuideTreeNode<S, C> n : tree) { 555 if (n.getProfile() == null) { 556 innerNodes.add(n); 557 } 558 } 559 560 // submit alignment tasks to the shared thread pool 561 int i = 1, all = innerNodes.size(); 562 for (GuideTreeNode<S, C> n : innerNodes) { 563 Profile<S, C> p1 = n.getChild1().getProfile(), p2 = n.getChild2().getProfile(); 564 Future<ProfilePair<S, C>> pf1 = n.getChild1().getProfileFuture(), pf2 = n.getChild2().getProfileFuture(); 565 ProfileProfileAligner<S, C> aligner = 566 (p1 != null) ? ((p2 != null) ? getProfileProfileAligner(p1, p2, type, gapPenalty, subMatrix) : 567 getProfileProfileAligner(p1, pf2, type, gapPenalty, subMatrix)) : 568 ((p2 != null) ? getProfileProfileAligner(pf1, p2, type, gapPenalty, subMatrix) : 569 getProfileProfileAligner(pf1, pf2, type, gapPenalty, subMatrix)); 570 n.setProfileFuture(ConcurrencyTools.submit(new CallableProfileProfileAligner<S, C>(aligner), String.format( 571 "Aligning pair %d of %d", i++, all))); 572 } 573 574 // retrieve the alignment results 575 for (GuideTreeNode<S, C> n : innerNodes) { 576 // TODO when added to ConcurrencyTools, log completions and exceptions instead of printing stack traces 577 try { 578 n.setProfile(n.getProfileFuture().get()); 579 } catch (InterruptedException e) { 580 logger.error("Interrupted Exception: ", e); 581 } catch (ExecutionException e) { 582 logger.error("Execution Exception: ", e); 583 } 584 } 585 586 // the alignment profile at the root of the tree is the full multiple sequence alignment 587 return tree.getRoot().getProfile(); 588 } 589 590 /** 591 * Factory method to run a list of alignments concurrently. This method runs the alignments in parallel by 592 * submitting all of the alignment tasks to the shared thread pool of the {@link ConcurrencyTools} utility. 593 * 594 * @param <S> each {@link Sequence} of an alignment pair is of type S 595 * @param <C> each element of an {@link AlignedSequence} is a {@link Compound} of type C 596 * @param aligners list of alignments to run 597 * @return list of {@link SequencePair} results from running alignments 598 */ 599 static <S extends Sequence<C>, C extends Compound> List<SequencePair<S, C>> 600 runPairwiseAligners(List<PairwiseSequenceAligner<S, C>> aligners) { 601 int n = 1, all = aligners.size(); 602 List<Future<SequencePair<S, C>>> futures = new ArrayList<Future<SequencePair<S, C>>>(); 603 for (PairwiseSequenceAligner<S, C> aligner : aligners) { 604 futures.add(ConcurrencyTools.submit(new CallablePairwiseSequenceAligner<S, C>(aligner), 605 String.format("Aligning pair %d of %d", n++, all))); 606 } 607 return getListFromFutures(futures); 608 } 609 610 /** 611 * Factory method to run a list of scorers concurrently. This method runs the scorers in parallel by submitting 612 * all of the scoring tasks to the shared thread pool of the {@link ConcurrencyTools} utility. 613 * 614 * @param <S> each {@link Sequence} of an alignment pair is of type S 615 * @param <C> each element of an {@link AlignedSequence} is a {@link Compound} of type C 616 * @param scorers list of scorers to run 617 * @return list of score results from running scorers 618 */ 619 public static <S extends Sequence<C>, C extends Compound> double[] runPairwiseScorers( 620 List<PairwiseSequenceScorer<S, C>> scorers) { 621 int n = 1, all = scorers.size(); 622 List<Future<Double>> futures = new ArrayList<Future<Double>>(); 623 for (PairwiseSequenceScorer<S, C> scorer : scorers) { 624 futures.add(ConcurrencyTools.submit(new CallablePairwiseSequenceScorer<S, C>(scorer), 625 String.format("Scoring pair %d of %d", n++, all))); 626 } 627 List<Double> results = getListFromFutures(futures); 628 double[] scores = new double[results.size()]; 629 for (int i = 0; i < scores.length; i++) { 630 scores[i] = results.get(i); 631 } 632 return scores; 633 } 634 635 /** 636 * Factory method to run a list of alignments concurrently. This method runs the alignments in parallel by 637 * submitting all of the alignment tasks to the shared thread pool of the {@link ConcurrencyTools} utility. 638 * 639 * @param <S> each {@link Sequence} of the {@link Profile} pair is of type S 640 * @param <C> each element of an {@link AlignedSequence} is a {@link Compound} of type C 641 * @param aligners list of alignments to run 642 * @return list of {@link ProfilePair} results from running alignments 643 */ 644 static <S extends Sequence<C>, C extends Compound> List<ProfilePair<S, C>> 645 runProfileAligners(List<ProfileProfileAligner<S, C>> aligners) { 646 int n = 1, all = aligners.size(); 647 List<Future<ProfilePair<S, C>>> futures = new ArrayList<Future<ProfilePair<S, C>>>(); 648 for (ProfileProfileAligner<S, C> aligner : aligners) { 649 futures.add(ConcurrencyTools.submit(new CallableProfileProfileAligner<S, C>(aligner), 650 String.format("Aligning pair %d of %d", n++, all))); 651 } 652 return getListFromFutures(futures); 653 } 654 655}