Coverage for binette/bin_manager.py: 97%
260 statements
« prev ^ index » next coverage.py v7.17.3, created at 2026-11-17 13:33 +0000
« prev ^ index » next coverage.py v7.17.3, created at 2026-11-17 13:33 +0000
1import itertools
2import logging
3from collections import Counter, defaultdict
4from collections.abc import Iterable
5from functools import cached_property
6from pathlib import Path
7from typing import Any
9import networkx as nx
10import numpy as np
11import pyfastx
12from pyroaring import BitMap
13from rich.progress import Progress
15logger = logging.getLogger(__name__)
18class Bin:
19 CHECKM2_MODELS = (
20 "Neural Network (Specific Model)",
21 "Gradient Boost (General Model)",
22 )
24 def __init__(
25 self,
26 contigs: BitMap,
27 origin: set[str] | None = None,
28 name: str | None = None,
29 is_original: bool = False,
30 ) -> None:
31 """
32 Initialize a Bin object.
34 :param contigs: Iterable of contig names belonging to the bin.
35 :param origin: Origin/source of the bin.
36 :param name: Name of the bin.
37 """
39 if not isinstance(contigs, BitMap):
40 raise TypeError("Contigs should be a BitMap object.")
42 if origin is None:
43 self.origin = set()
44 else:
45 self.origin = {origin}
47 self.name = name
49 self.is_original = is_original
51 self.contigs = contigs
53 self.length = None
54 self.N50 = None
56 self.completeness = None
57 self.contamination = None
58 self.score = None
59 self.coding_density = None
60 self.original_name = None
61 self._checkm2_model_index = None
63 @cached_property
64 def contigs_key(self):
65 """
66 Serialize the contigs for easier comparison.
67 """
68 return self.contigs.serialize()
70 def __eq__(self, other: "Bin") -> bool:
71 """
72 Compare the Bin object with another object for equality.
74 :param other: The object to compare with.
75 :return: True if the objects are equal, False otherwise.
76 """
77 return self.contigs_key == other.contigs_key
79 def __str__(self) -> str:
80 """
81 Return a string representation of the Bin object.
83 :return: The string representation of the Bin object.
84 """
85 return f"Bin {self.name} from {';'.join(self.origin)} ({len(self.contigs)} contigs)"
87 def overlaps_with(self, other: "Bin") -> set[str]:
88 """
89 Find the contigs that overlap between this bin and another bin.
91 :param other: The other Bin object.
92 :return: A set of contig names that overlap between the bins.
93 """
94 return self.contigs & other.contigs
96 def add_length(self, length: int) -> None:
97 """
98 Add the length attribute to the Bin object if the provided length is a positive integer.
100 :param length: The length value to add.
101 :return: None
102 """
103 if isinstance(length, int) and length > 0:
104 self.length = length
105 else:
106 raise ValueError("Length should be a positive integer.")
108 def add_N50(self, n50: int) -> None:
109 """
110 Add the N50 attribute to the Bin object.
112 :param n50: The N50 value to add.
113 :return: None
114 """
115 if isinstance(n50, int) and n50 >= 0:
116 self.N50 = n50
117 else:
118 raise ValueError("N50 should be a positive integer.")
120 def add_quality(
121 self, completeness: float, contamination: float, contamination_weight: float
122 ) -> None:
123 """
124 Set the quality attributes of the bin.
126 :param completeness: The completeness value.
127 :param contamination: The contamination value.
128 :param contamination_weight: The weight assigned to contamination in the score calculation.
129 """
130 self.completeness = completeness
131 self.contamination = contamination
132 self.score = completeness - contamination_weight * contamination
134 def add_model(self, model: str) -> None:
135 """
136 Add a CheckM2 model to the bin.
138 :param model: The model name to add.
139 :raises ValueError: If the model name is not recognized.
140 """
142 try:
143 self._checkm2_model_index = self.CHECKM2_MODELS.index(model)
144 except ValueError as exc:
145 raise ValueError(
146 f"Unknown model '{model}' attempted to be added to bin '{self.name}'. "
147 f"Valid models are: {', '.join(self.CHECKM2_MODELS)}"
148 ) from exc
150 @cached_property
151 def checkm2_model(self):
152 """
153 Get the CheckM2 model for the bin.
154 """
155 if self._checkm2_model_index is not None:
156 return self.CHECKM2_MODELS[self._checkm2_model_index]
157 return None
159 def contig_intersection(self, *others: "Bin") -> BitMap:
160 """
161 Compute the intersection of the bin with other bins.
163 :param others: Other bins to compute the intersection with.
164 """
165 return self.contigs.intersection(*(o.contigs for o in others))
167 def contig_difference(self, *others: "Bin") -> BitMap:
168 """
169 Compute the difference between the bin and other bins.
171 :param others: Other bins to compute the difference with.
172 """
173 return self.contigs.difference(*(o.contigs for o in others))
175 def contig_union(self, *others: "Bin") -> BitMap:
176 """
177 Compute the union of the bin with other bins.
179 :param others: Other bins to compute the union with.
180 """
181 return self.contigs.union(*(o.contigs for o in others))
183 def is_high_quality(
184 self, min_completeness: float, max_contamination: float
185 ) -> bool:
186 """
187 Determine if a bin is considered high quality based on completeness and contamination thresholds.
189 :param min_completeness: The minimum completeness required for a bin to be considered high quality.
190 :param max_contamination: The maximum allowed contamination for a bin to be considered high quality.
192 :raises ValueError: If either completeness or contamination has not been set (is None).
194 :return: True if the bin meets the high quality criteria; False otherwise.
195 """
196 if self.completeness is None or self.contamination is None:
197 raise ValueError(
198 f"The bin '{self.name}' with ID '{self.name}' has not been evaluated for completeness or contamination, "
199 "and therefore cannot be assessed for high quality."
200 )
202 return (
203 self.completeness >= min_completeness
204 and self.contamination <= max_contamination
205 )
207 def add_coding_density(
208 self, contig_to_coding_length: dict[int, int]
209 ) -> float | None:
210 """
211 Calculate the coding density of the bin.
213 :param contig_to_coding_length: A dictionary mapping contig IDs to their total coding lengths.
215 :return: The coding density of the bin, or None if the length is not set or is zero.
216 """
217 if self.length is None or self.length == 0:
218 return None
220 total_coding = sum(
221 contig_to_coding_length.get(contig_id, 0) for contig_id in self.contigs
222 )
224 self.coding_density = total_coding / self.length
227def make_bins_from_bins_info(
228 bin_set_name_to_bins_info: dict[str, list[dict[str, Any]]],
229 contig_to_index: dict[str, int],
230 are_original_bins: bool,
231):
232 """
233 Create Bin objects from the provided bin information.
235 :param bin_set_name_to_bins_info: A dictionary mapping bin set names to their bin information.
236 :param contig_to_index: A mapping of contig names to their indices.
237 :param are_original_bins: A boolean indicating whether the bins are original.
239 :return: A dictionary mapping serialized contig bitmaps to their corresponding Bin objects.
240 """
242 contig_key_to_bin: dict[bytes, Bin] = {}
244 for set_name, bins_info in bin_set_name_to_bins_info.items():
245 for bin_info in bins_info:
246 bitmap_contigs = BitMap(
247 contig_to_index[contig] for contig in bin_info["contigs"]
248 )
250 bin_obj = Bin(
251 contigs=bitmap_contigs,
252 origin=set_name,
253 name=bin_info["bin_name"],
254 is_original=are_original_bins,
255 )
256 if bin_obj.contigs_key not in contig_key_to_bin:
257 contig_key_to_bin[bin_obj.contigs_key] = bin_obj
258 else:
259 # Same contigs as a bin already seen: keep that bin and record
260 # that this bin set also produced it.
261 contig_key_to_bin[bin_obj.contigs_key].origin.add(set_name)
263 return contig_key_to_bin
266def get_bins_from_directory(
267 bin_dir: Path, set_name: str, fasta_extensions: set[str]
268) -> list[Bin]:
269 """
270 Retrieves a list of Bin objects from a directory containing bin FASTA files.
272 :param bin_dir: The directory path containing bin FASTA files.
273 :param set_name: The name of the set the bins belong to.
274 :fasta_extensions: Possible fasta extensions to look for in the bin directory.
276 :return: A list of Bin objects created from the bin FASTA files.
277 """
278 bins = []
279 fasta_extensions |= {
280 f".{ext}" for ext in fasta_extensions if not ext.startswith(".")
281 } # adding a dot in case given extension are lacking one
282 bin_fasta_files = (
283 fasta_file
284 for fasta_file in bin_dir.glob("*")
285 if set(fasta_file.suffixes) & fasta_extensions
286 )
288 for bin_fasta_path in bin_fasta_files:
289 bin_name = bin_fasta_path.with_suffix("").name
291 contigs = {name for name, _ in pyfastx.Fastx(str(bin_fasta_path))}
293 bin_dict = {"contigs": contigs, "set_name": set_name, "bin_name": bin_name}
295 bins.append(bin_dict)
297 return bins
300def parse_bin_directories(
301 bin_name_to_bin_dir: dict[str, Path], fasta_extensions: set[str]
302) -> dict[str, list[dict[str, Any]]]:
303 """
304 Parses multiple bin directories and returns a dictionary mapping bin set names to a list of bin info dicts.
306 Bins with identical contigs are merged later, in make_bins_from_bins_info.
308 :param bin_name_to_bin_dir: A dictionary mapping bin names to their respective bin directories.
309 :fasta_extensions: Possible fasta extensions to look for in the bin directory.
311 :return: A dictionary mapping bin names to a list of dict created from the bin directories.
312 """
313 bin_set_name_to_bins_info = {}
315 for name, bin_dir in sorted(bin_name_to_bin_dir.items()):
316 bins = get_bins_from_directory(bin_dir, name, fasta_extensions)
317 bin_set_name_to_bins_info[name] = bins
319 return bin_set_name_to_bins_info
322def parse_contig2bin_tables(
323 bin_name_to_bin_tables: dict[str, Path],
324) -> dict[str, list[dict[str, Any]]]:
325 """
326 Parses multiple contig-to-bin tables and returns a dictionary mapping bin set names to a list of bin info dicts.
328 Bins with identical contigs are merged later, in make_bins_from_bins_info.
330 :param bin_name_to_bin_tables: A dictionary where keys are bin set names and values are file paths or identifiers
331 for contig-to-bin tables.
333 :return: A dictionary mapping bin set names to a list of dict created from the contig-to-bin tables.
334 """
335 bin_set_name_to_bins_info = {}
337 for name, contig2bin_table in sorted(bin_name_to_bin_tables.items()):
338 bins = get_bins_from_contig2bin_table(contig2bin_table, name)
339 bin_set_name_to_bins_info[name] = bins
341 return bin_set_name_to_bins_info
344def get_bins_from_contig2bin_table(
345 contig2bin_table: Path, set_name: str
346) -> list[dict[str, Any]]:
347 """
348 Retrieves a list of Bin objects from a contig-to-bin table.
350 :param contig2bin_table: The path to the contig-to-bin table.
351 :param set_name: The name of the set the bins belong to.
353 :return: A list of Bin info in dict created from the contig-to-bin table.
354 """
355 bin_name2contigs = defaultdict(set)
356 with open(contig2bin_table) as fl:
357 for line in fl:
358 if line.startswith("#") or line.startswith("@"):
359 logger.debug(f"Ignoring a line from {contig2bin_table}: {line}")
360 continue
361 contig_name = line.strip().split()[0]
362 bin_name = line.strip().split("\t")[1]
363 bin_name2contigs[bin_name].add(contig_name)
365 bins = []
366 for bin_name, contigs in bin_name2contigs.items():
367 bin_dict = {"contigs": contigs, "set_name": set_name, "bin_name": bin_name}
368 bins.append(bin_dict)
369 return bins
372def from_bins_to_bin_graph(bins: Iterable[Bin]) -> nx.Graph:
373 """
374 Creates a bin graph made of overlapping gram a set of bins.
376 :param bins: a set of bins
378 :return: A networkx Graph representing the bin graph of overlapping bins.
379 """
380 G = nx.Graph()
382 for bin1, bin2 in itertools.combinations(bins, 2):
383 if bin1.overlaps_with(bin2):
384 G.add_edge(bin1.contigs_key, bin2.contigs_key)
385 return G
388def get_all_possible_combinations(clique: list) -> Iterable[tuple]:
389 """
390 Generates all possible combinations of elements from a given clique.
392 :param clique: An iterable representing a clique.
394 :return: An iterable of tuples representing all possible combinations of elements from the clique.
395 """
396 return (
397 c for r in range(2, len(clique) + 1) for c in itertools.combinations(clique, r)
398 )
401def build_contig_index(bins_dict: dict[bytes, Bin]) -> dict[int, set[bytes]]:
402 """
403 Build an inverted index: contig_id -> set of contigs_key of bins containing it.
404 :param bins_dict: Mapping from contigs_key -> Bin.
405 :return: Inverted index (contig_id -> set of contigs_key).
406 """
407 contig_to_bins = defaultdict(set)
408 for key, bin_obj in bins_dict.items():
409 for contig in bin_obj.contigs:
410 contig_to_bins[contig].add(key)
411 return contig_to_bins
414def remove_bins_from_index(
415 bin_keys: set[bytes],
416 bins_dict: dict[bytes, Bin],
417 contig_to_bins: dict[int, set[bytes]],
418) -> None:
419 """
420 Remove a set of bins from the inverted index.
422 :param bin_keys: The contig_keys of bins to remove.
423 :param bins_dict: Mapping from contig_key -> Bin.
424 :param contig_to_bins: Inverted index (contig_id -> set of contig_keys).
425 """
426 for key in bin_keys:
427 ob = bins_dict.get(key)
428 if ob is not None:
429 for c in ob.contigs:
430 contig_to_bins[c].discard(key)
433def select_best_bins(
434 bins_dict: dict[bytes, Bin],
435 min_completeness: float,
436 max_contamination: float,
437 prefix: str = "binette",
438) -> list[Bin]:
439 """
440 Select the best non-overlapping bins based on score, N50, and ID.
442 :param bins_dict: Mapping from contig_key -> Bin.
443 :param min_completeness: Minimum completeness threshold for a bin to be considered.
444 :param max_contamination: Maximum contamination threshold for a bin to be considered.
445 :param prefix: Prefix to use for naming selected bins.
447 """
448 logger.info("Selecting best bins")
450 logger.info(
451 f"Filtering bins: only bins with completeness >= {min_completeness} "
452 f"and contamination <= {max_contamination}"
453 )
454 good_enough_bins = {
455 k: b
456 for k, b in bins_dict.items()
457 if b.completeness >= min_completeness and b.contamination <= max_contamination
458 }
460 logger.info("Sorting bins")
461 sorted_bin_keys = sorted(
462 good_enough_bins,
463 key=lambda k: (
464 -good_enough_bins[k].score,
465 -good_enough_bins[k].N50,
466 -good_enough_bins[k].is_original,
467 k, # contigs_key itself is sortable (bytes)
468 ),
469 )
471 logger.info("Building contig index")
472 contig_to_bin_keys = build_contig_index(good_enough_bins)
474 logger.info("Selecting bins")
475 selected_bins = []
476 discarded_keys = set()
478 for bin_key in sorted_bin_keys:
479 if bin_key in discarded_keys:
480 continue
482 bin_obj = good_enough_bins[bin_key]
483 selected_bins.append(bin_obj)
485 # Gather overlapping bins via inverted index
486 overlapping_bin_keys = set()
487 for contig in bin_obj.contigs:
488 overlapping_bin_keys |= contig_to_bin_keys[contig]
490 # Discard them
491 discarded_keys |= overlapping_bin_keys
493 # Remove discarded bins from index to shrink future lookups
494 remove_bins_from_index(
495 overlapping_bin_keys, good_enough_bins, contig_to_bin_keys
496 )
498 logger.info(f"Selected {len(selected_bins)} bins")
500 for i, selected_bin in enumerate(selected_bins, start=1):
501 if not selected_bin.origin:
502 selected_bin.origin = {"binette"}
503 if selected_bin.name is not None:
504 selected_bin.original_name = selected_bin.name
505 selected_bin.name = f"{prefix}_bin{i}"
506 return selected_bins
509def get_contigs_in_bin_sets(bin_set_name_to_bins: dict[str, set[Bin]]) -> list[str]:
510 """
511 Processes bin sets to check for duplicated contigs and logs detailed information about each bin set.
513 :param bin_set_name_to_bins: A dictionary where keys are bin set names and values are sets of Bin objects.
515 :return: A set of contig names found in bin sets
516 """
517 # To track all unique contigs across bin sets
518 all_contigs_in_bins = set()
520 for bin_set_name, bins_info in bin_set_name_to_bins.items():
521 list_contigs_in_bin_sets = [
522 contig for bin_info in bins_info for contig in bin_info["contigs"]
523 ]
525 contig_counts = Counter(list_contigs_in_bin_sets)
526 duplicated_contigs = {
527 contig: count for contig, count in contig_counts.items() if count > 1
528 }
530 if duplicated_contigs:
531 logger.warning(
532 f"Bin set '{bin_set_name}' contains {len(duplicated_contigs)} duplicated contigs. "
533 "Details: "
534 + ", ".join(
535 f"{contig} (found {count} times)"
536 for contig, count in duplicated_contigs.items()
537 )
538 )
540 # Unique contigs in current bin set
541 unique_contigs_in_bin_set = set(list_contigs_in_bin_sets)
543 # Update global contig tracker
544 all_contigs_in_bins |= unique_contigs_in_bin_set
546 # Log summary for the current bin set
547 logger.debug(
548 f"Bin set '{bin_set_name}': {len(bins_info)} bins, {len(unique_contigs_in_bin_set)} unique contigs."
549 )
551 return list(all_contigs_in_bins)
554def sum_contig_lengths(
555 bm_contigs: BitMap,
556 contig_lengths: np.ndarray,
557 cache: dict[bytes, int] | None = None,
558 key: bytes | None = None,
559):
560 if cache is None:
561 cache = {}
562 if key is None:
563 key = bm_contigs.serialize()
564 if key not in cache:
565 cache[key] = int(contig_lengths[np.fromiter(bm_contigs, dtype=np.int32)].sum())
566 return cache[key]
569def create_intermediate_bins(
570 contig_key_to_initial_bin: dict[bytes, Bin],
571 contig_lengths: np.ndarray,
572 min_comp: float,
573 max_conta: float,
574 min_len: int,
575 max_len: int,
576 disable_progress_bar: bool = False,
577) -> dict[bytes, Bin]:
578 """
579 Creates intermediate bins from a dictionary of bin sets.
581 :param original_bins: Set of input bins.
583 :return: A set of intermediate bins created from intersections, differences, and unions.
584 """
585 bin_length_cache = {}
587 logger.info("Making bin graph")
588 connected_bins_graph = from_bins_to_bin_graph(contig_key_to_initial_bin.values())
590 cliques_of_bins = sorted(
591 [sorted(clique) for clique in nx.clique.find_cliques(connected_bins_graph)]
592 )
594 logger.info("Creating union, difference, and intersection bins")
595 logger.debug(f"{min_comp} min completeness for intersection and difference bins")
596 logger.debug(f"{max_conta} max contamination for intersection and difference bins")
597 logger.debug(f"{min_len} min length for intersection and difference bins")
598 logger.debug(f"{max_len} max length for intersection and difference bins")
599 logger.info(
600 f"Intermediate bins filtered by minimum length of {min_len} and maximum length of {max_len}."
601 )
602 intersec_count = 0
603 union_count = 0
604 diff_count = 0
606 intersec_size_discarded_count = 0
607 diff_size_discarded_count = 0
608 union_size_discarded_count = 0
610 contig_key_to_new_contigs_set = {}
611 discarded_contig_set_keys = set()
612 with Progress(disable=disable_progress_bar) as progress:
613 task = progress.add_task(
614 f"Processing {len(cliques_of_bins)} cliques of bins",
615 total=len(cliques_of_bins),
616 )
617 for clique in cliques_of_bins:
618 progress.update(task, advance=1)
619 bins_combinations = get_all_possible_combinations(clique)
621 for bin_contig_keys in bins_combinations:
622 bins = [contig_key_to_initial_bin[ck] for ck in bin_contig_keys]
624 if all(
625 b.completeness >= min_comp and b.length >= min_len for b in bins
626 ):
627 intersec_contigs = bins[0].contig_intersection(*bins[1:])
629 if intersec_contigs:
630 contig_key = intersec_contigs.serialize()
632 if (
633 contig_key not in contig_key_to_initial_bin
634 and contig_key not in contig_key_to_new_contigs_set
635 and contig_key not in discarded_contig_set_keys
636 ):
637 contigs_length = sum_contig_lengths(
638 intersec_contigs,
639 contig_lengths,
640 cache=bin_length_cache,
641 key=contig_key,
642 )
644 if contigs_length >= min_len and contigs_length <= max_len:
645 contig_key_to_new_contigs_set[contig_key] = (
646 intersec_contigs
647 )
648 intersec_count += 1
649 else:
650 discarded_contig_set_keys.add(contig_key)
651 intersec_size_discarded_count += 1
653 for bin_a in bins:
654 if bin_a.completeness >= min_comp and bin_a.length >= min_len:
655 diff_contigs = bin_a.contig_difference(
656 *(b for b in bins if b != bin_a)
657 )
659 if diff_contigs:
660 contig_key = diff_contigs.serialize()
662 if (
663 contig_key not in contig_key_to_initial_bin
664 and contig_key not in contig_key_to_new_contigs_set
665 and contig_key not in discarded_contig_set_keys
666 ):
667 contigs_length = sum_contig_lengths(
668 diff_contigs,
669 contig_lengths,
670 cache=bin_length_cache,
671 key=contig_key,
672 )
674 if (
675 contigs_length >= min_len
676 and contigs_length <= max_len
677 ):
678 contig_key_to_new_contigs_set[contig_key] = (
679 diff_contigs
680 )
681 diff_count += 1
682 else:
683 discarded_contig_set_keys.add(contig_key)
684 diff_size_discarded_count += 1
686 if all(
687 b.contamination <= max_conta and b.length <= max_len for b in bins
688 ):
689 union_contigs = bins[0].contig_union(*bins[1:])
690 if union_contigs:
691 contig_key = union_contigs.serialize()
692 if (
693 contig_key not in contig_key_to_initial_bin
694 and contig_key not in contig_key_to_new_contigs_set
695 and contig_key not in discarded_contig_set_keys
696 ):
697 contigs_length = sum_contig_lengths(
698 union_contigs,
699 contig_lengths,
700 cache=bin_length_cache,
701 key=contig_key,
702 )
703 if contigs_length >= min_len and contigs_length <= max_len:
704 contig_key_to_new_contigs_set[contig_key] = (
705 union_contigs
706 )
707 union_count += 1
708 else:
709 discarded_contig_set_keys.add(contig_key)
710 union_size_discarded_count += 1
712 logger.info(
713 f"Intersection: {intersec_count} bins created, {intersec_size_discarded_count} discarded due to size constraints."
714 )
716 logger.info(
717 f"Symmetric Difference: {diff_count} bins created, {diff_size_discarded_count} discarded due to size constraints."
718 )
720 logger.info(
721 f"Union: {union_count} bins created, {union_size_discarded_count} discarded due to size constraints."
722 )
724 contig_key_to_new_bin: dict[bytes, Bin] = {
725 contig_key: Bin(contigs, is_original=False)
726 for contig_key, contigs in contig_key_to_new_contigs_set.items()
727 }
729 logger.info(
730 f"{len(contig_key_to_new_bin)} new bins created from {len(contig_key_to_initial_bin)} input bins."
731 )
733 return contig_key_to_new_bin