3D 도메인에서 특정 시퀀스의 끝 위치 (x, y, z)를 감지하는 방법

Question

단백질 3D Creo-EM 스캔을 사용합니다. 그 자체가 구부러지고 뒤틀리는 사슬을 포함하고 3 차원 공간에 있습니다 2 개의 체인 엔딩 (연속 로프와 같은). 나는 주어진 큐브 공간 내에서 (x, y, z) 위치를 2 개 또는 아마도 2 개의 엔딩의 승수로 검출 할 필요가있다. 스캔의 큐브 공간은 EM 현미경을 스캐닝하여 제공되는 각 보셀 (범위 0에서 1까지)의 밀도로 표시되며 "현존하는 물질"은 1에 가까운 값을 제공하고 "상관 없이"는 0에 가까운 밀도 값을 제공합니다. 가능한 "로프 결말"정의가 얽힌 방향으로 연속성이없는 것입니다. 직관적으로, 적어도 두 가지 방법이있을 수 있다고 생각합니다. 1) 그래프 이론의 특정 방법 (구체적으로 설명 할 수는 없습니다. 정확하게 - 당신이 알고 있다면 - 이름을 말하고 설명하십시오 2) 분석 대수학의 파생물 - 그러나 다시는 구체적인 태도를 지정할 수 없습니다 - 그래서 이름을 지정하거나 설명하십시오. 제안 된 방법의 계산 복잡성을 지정하십시오. 내 프로젝트는 파이썬으로 구현된다. 도와주세요. 미리 감사드립니다.

Answer 1

한 가지 방법, 임계 밀도를 선택 1 0과 그 위의 모든이 임계 값 아래의 모든 복셀로 변환 한 다음 최단 경로 1 복셀의 쌍의 모든 쌍 중 가장 긴 을 찾아하는 것 1 복셀. 이 두 개의 복셀은 로프가 취하는 정확한 모양과 상관없이 가장 긴 "로프"의 끝 부분에 있어야합니다.

각 1- 복셀에 대한 정점과 각 1- 복셀과 6 개 (또는 가능하면 14 개) 이웃 사이의 모서리가있는 그래프를 정의 할 수 있습니다. 너는 너비가있는 첫 번째 검색을 사용하여 O (| V |) 시간과 공간에서 주어진 정점 u와 다른 모든 정점 사이의 최단 경로의 길이를 계산할 수 있습니다 (우리는 모든 가장자리에 가중치가 있기 때문에 Dijkstra 또는 Floyd-Warshall이 필요 없습니다). 1). 가능한 각 시작 버텍스 u에 대해이를 반복하면 O (| V |^2) 시간 알고리즘이 제공됩니다. 이렇게 할 때, 지금까지 가장 먼 쌍을 추적하십시오.

voxel 공간에 w * h * d 셀이있는 경우 그래프에 w * h * d 개의 꼭지점이있을 수 있습니다 (모든 단일 보셀이 1 개의 보셀 인 경우). 그러면 O (w^2 * h^2 * d^2) 시간은 최악의 경우입니다. 다행히 당신이 약간 부정확 한 답을 줄 수있는 경우에이 속도를하는 방법에는 여러 가지가 있습니다 :

• 만 경계에있는 시작 정점에서 최단 경로를 계산 -이 그 정점을 즉 미만 6 (14) 이웃. (나는 이것이 최적의 솔루션을 희생하지 않을 것이라고 생각합니다.) 또는 다른 방법으로는 그래프를 분리하지 않는 모든 경계 꼭지점을 반복적으로 제거하여 그래프를 "골격화"하십시오.
• 시작점을 선택하는 좋은 순서는 먼저 모든 꼭지점을 선택한 다음 마지막 점과 가능한 최대 거리에있는 (그리고 아직 시도하지 않은) 꼭지점을 선택하는 것입니다. 이것은 단지 3 번의 반복 후에 가장 긴 최단 경로에 대한 아주 좋은 근사값을 얻을 것입니다. 시작 꼭지점에서 가장 먼 꼭지점은 두 개의 로프 끝 중 하나 근처에 있고, 의 가장 먼 꼭지점은 꼭지점이 다른 쪽 끝에 있습니다. !

참고 :이 때문에, 가장 짧은 경로 것 "단락을"굽힘에 서로 가까이 로프 먼 지점 사이에 전체 복셀 격차는 이러한 잘못된 연결을 통해없고 아마도 정확도가 떨어질 경우 . 임계 값을 높임으로써이를 개선 할 수 있습니다. OTOH, 임계 값이 너무 높으면 로프가 분리 될 수 있습니다. 나는 오직 하나의 연결된 구성 요소로 귀착되는 가장 높은 임계 값을 선택하기를 기대합니다.

Answer 2

각 연속 경로를 예를 들어, 각 위치에 대한 기본 깊이 우선 검색을 적용 할 수있는 당신을 스캔하여 3D로 (함으로써 각 경로의 끝을 획득) 열거하려면 다음

//applied at some voxel 
dfs(...) 
    for each surrounding voxel 
     dfs(...) 

또는 자세히 :

class coordinate{ 
    x 
    y 
    z 
    visited 
} 

initialize pathList 
initialize coords 

add all coordinates which contain "matter" to coords 

dfs(coordinate,path) 
    coordinate.visited = TRUE 
    isEnd = TRUE 
    FOR each coordinate 
     //check each of the 26 possible locations (total 26 conditionals) 
     IF coordinate.get(x-1,y-1,z+1) IN coords AND 
      NOT coordinate.get(x-1,y-1,z+1).visited THEN 
      isEnd = FALSE 
      path += coordinate.get(x-1,y-1,z+1) 
      dfs(coordinate.get(x-1,y-1,z+1),path) 
     ... 
     IF coordinate.get(x+1,y+1,z-1) IN coords AND 
      NOT coordinate.get(x+1,y+1,z-1).visited THEN 
      isEnd = FALSE 
      path += coordinate.get(x+1,y+1,z-1) 
      dfs(coordinate.get(x+1,y+1,z-1),path) 
    IF isEnd THEN 
     add path to pathList 
    remove coordinate from coords 

WHILE coords isn't empty 
    dfs(coords.get(0),"") 

일반적인 절차 (DFS)은 다른 사이트의 수십에 잘 설명되어 있지만, 당신이 그것을 테스트하려는 경우 여기에 몇 가지 원유 자바 (I 파이썬 너무 익숙하지 않다) 그 거울이다 위에 무엇입니까 :

public class C { 

    ArrayList<Coordinate> coords = new ArrayList<>(); 
    ArrayList<String> paths = new ArrayList<>(); 



    static class Coordinate { 
     int x, y, z; 
     boolean visited; 
     Coordinate(int x,int y,int z){ 
      this.x = x; 
      this.y = y; 
      this.z = z; 
      visited = false; 
     } 

     public String toString() { 
      return "("+x+","+y+","+z+")"; 
     } 
    } 



    void dfs(Coordinate c,String path) { 
     c.visited=true; 
     path+=c.toString(); 
     boolean isEnd = true; 
     //apply dfs to 26 possible neighbors 
     for(int x = c.x-1; x <= c.x+1; x++) { 
      for (int y = c.y-1; y <= c.y+1; y++) { 
       for (int z = c.z+1; z >= c.z-1; z--) { 
        Coordinate coord = getCoordinate(x,y,z); 
        //if coord exists and it's not been visited 
        if(coord!=null && !coord.visited && !coord.equals(c)) { 
         isEnd = false; 
         dfs(coord, path); 
        } 
       } 
      } 
     } 
     if(isEnd) paths.add(path); 

     coords.remove(c); 
    } 

    Coordinate getCoordinate(int x,int y,int z){ 
     for(Coordinate b: coords){ 
      if(x==b.x && y==b.y && z==b.z) return b; 
     } 
     return null; 
    } 


    void search(){ 
     //while there are points in 3d space extend a path from one 
     while(!coords.isEmpty()){ 
      dfs(coords.get(0),""); 
     } 
    } 




    public static void main(String[] args) { 

     C coord = new C(); 

     //for each place where there exists matter 
     //create a coordinate object and add to coords 
     // for example: 
     coord.coords.add(new Coordinate(0,0,0)); 
     coord.coords.add(new Coordinate(-1,1,1)); 
     coord.coords.add(new Coordinate(1,1,1)); 
     coord.coords.add(new Coordinate(-1,2,2)); 
     coord.coords.add(new Coordinate(-1,0,2)); 
     coord.coords.add(new Coordinate(1,2,2)); 
     coord.coords.add(new Coordinate(1,0,2)); 

     coord.search(); 
     //print out each path on separate line, 
     //the path endings can easily be obtained from this 
     for(String s:coord.paths) System.out.println(s); 

    } 
}